Game - Map data structures

[Innocence]

Hi

I've been considering how to optimize map data structures for a tile
based Python game. However, since I'm a Python newbie I lack
experience with Pythons 'exotic' data types like lists and tuples, and
thus I'm unsure whether such types could solve my problem.

My basic thought is this: If my world map consists of 80% water and
20% land, then why reserve full data-structures for all the water
tiles?

I'm looking for a way to do the following:

My World Map object should likely be a standard (x,y) array of Tiles
(unless there's a better way?)
Each Tile has a boolean/one-bit value: 0 or False for Water, 1 or True
for Land.
Each Tile has an object (class), but the type of object depends on
whether it's a Water or Land Tile:
- A Land object needs data structures for each of the six hex corners
(ie. does a given hex-side contain a Coastline, a Mountain, a Bridge
etc.) + data for buildings (Castle, Harbour etc.). Finally it needs
links to which armies reside on the Tile.

- A Water object need only links to which armies reside on the Tile
(ie. sailing armies/fleets).

So it seems to me I could save not only a fair deal of memory but also
processor power on 80% of the Tiles drawn: With each Land Tile I have
to check Hex Side values and building lists to draw special features.
All this is totally unnecessary with Water Tiles.

If anyone here could tell me how to make such a data-set, where each
Tile/element might be one of two object types, I'd really appreciate
it

0 Innocence

 

[Dennis Lee Bieber]

My World Map object should likely be a standard (x,y) array of Tiles
(unless there's a better way?)
Each Tile has a boolean/one-bit value: 0 or False for Water, 1 or True
for Land.
Each Tile has an object (class), but the type of object depends on
whether it's a Water or Land Tile:

Well, either you are using two similar classes, one for land and
one for water -- in which case you don't need the boolean at all, just a
means to obtain the class from the instance. Or you use one class which
is initiated differently for the two types of tiles.

- A Land object needs data structures for each of the six hex corners
(ie. does a given hex-side contain a Coastline, a Mountain, a Bridge
etc.) + data for buildings (Castle, Harbour etc.). Finally it needs
links to which armies reside on the Tile.

class Tile: # I know, old-style class...
def __init__(Land= False):
self.Land = Land
if Land:
self.Side = [None] * 6 #sides undefined
self.Buildings = [] #empty list
self.Armies = [] #land or water both
def SetSide(side, terrain):
try:
self.Side[side] = terrain
except:
print "Can not set terrain for water hex"
....

Unlike C++, and other static languages, where one has to
predeclare all possible data members (or subclass from virtuals and add
members), Python instances do not have to contain identical data -- the
data members are added by member functions.

--

 

[=?iso-8859-15?Q?Pierre-Fr=E9d=E9ric_Caillaud?=]

Save memory by having all the water tiles pointing to the same water
instance.

water = WaterTile()

.... build your tiles :

if tile should be water:
tile[x][y] = water # doesn't instanciate
else:
tile[x][y] = GroundTile() # instanciate new object

 

[Sam Holden]

Save memory by having all the water tiles pointing to the same water
instance.

water = WaterTile()

... build your tiles :

if tile should be water:
tile[x][y] = water # doesn't instanciate
else:
tile[x][y] = GroundTile() # instanciate new object

That's going to make it really hard to determine which boats are on a
given water tile.

 

[Erik Max Francis]

That's going to make it really hard to determine which boats are on a
given water tile.

Surely if you're dealing with populating a grid of things with objects,
you're not going to do so by holding objects in each slot. You'll
implement some sort of sparse array, instead.

 

[Sam Holden]

Surely if you're dealing with populating a grid of things with objects,
you're not going to do so by holding objects in each slot. You'll
implement some sort of sparse array, instead.

I'm not doing it and hence don't care enough to think about how I would
do it, the OP did however state:

- A Water object need only links to which armies reside on the Tile
(ie. sailing armies/fleets).

Which imples to me that the water object has an armies list or something
hanging of it.

 

[Dan Bishop]

Hi

I've been considering how to optimize map data structures for a tile
based Python game. However, since I'm a Python newbie I lack
experience with Pythons 'exotic' data types like lists and tuples, and
thus I'm unsure whether such types could solve my problem.

My basic thought is this: If my world map consists of 80% water and
20% land, then why reserve full data-structures for all the water
tiles?

I'm looking for a way to do the following:

My World Map object should likely be a standard (x,y) array of Tiles
(unless there's a better way?)
Each Tile has a boolean/one-bit value: 0 or False for Water, 1 or True
for Land.

A better way is to have the class hierarchy like

class Tile(object):
def __init__(self, ...):
# data that any Tile can contain
self.armies = ...
...

class WaterTile(Tile):
pass

class LandTile(Tile):
def __init__(self, ...):
Tile.__init__(self, ...)
# data specific to land tiles
self.building = ...

 

[Innocence]

Which imples to me that the water object has an armies list or something
hanging of it.

Of course there's an army-list containing all the army objects in the
game, but the plan was to make indexed links to this list from each
tile containing one or more armies. That way, if a player clicks a
tile the game knows which armies exists on that tile.

If I didn't have such links, I'd have to search through the entire
army list every time a tile is selected.

I know this makes for redundant data, but it's the only way I could
figure out how to avoid potiential performance issues when selecting
tiles. However, if there's a better way to do this I'd be happy to
know

Thanks

0 Innocence

 

[phil hunt]

A better way is to have the class hierarchy like

class Tile(object):
def __init__(self, ...):
# data that any Tile can contain
self.armies = ...
...

class WaterTile(Tile):
pass

class LandTile(Tile):
def __init__(self, ...):
Tile.__init__(self, ...)
# data specific to land tiles
self.building = ...

I think you are confusing two separate concepts here: the concept of
a terrain type, and the concept of a location.

A terrain type is something like "water", or "hill", or perhaps
"hill with coal resource". You can ask a terrain type questions like
"how many movement points does it costto move onto / off of a square
of this terrain type?"

A location is something like "grid reference (x=20, y=32) on the
map". You can ask a location things like "what armies are on this
location?", or "return a reference to the location to the north of
this one".

 

[Mitja]

Of course there's an army-list containing all the army objects in the
game, but the plan was to make indexed links to this list from each
tile containing one or more armies. That way, if a player clicks a
tile the game knows which armies exists on that tile.

If I didn't have such links, I'd have to search through the entire
army list every time a tile is selected.

I know this makes for redundant data, but it's the only way I could
figure out how to avoid potiential performance issues when selecting
tiles. However, if there's a better way to do this I'd be happy to
know

If the number of armies is small enough (say 1000, to be on the safe side),
don't worry about performance.

 

[Dennis Lee Bieber]

Of course there's an army-list containing all the army objects in the
game, but the plan was to make indexed links to this list from each

Why? (indexed links, that is)

Since Python "variables" aren't storage spaces, but references
/to/ the storage, it doesn't cause any problem for each tile to just use
a list of armies, and add the "army" to the list as needed.

tile containing one or more armies. That way, if a player clicks a
tile the game knows which armies exists on that tile.

anArmy = "First Army"
anotherArmy = "Second Army"
MasterArmyList = [anArmy, anotherArmy]
class Tile:

.... def __init__(self):
.... self.ArmyList = []
....

tile1 = Tile()
tile2 = Tile()
tile1.ArmyList.append(anArmy)
tile2.ArmyList.append(anotherArmy)
tile1

tile1.ArmyList ['First Army']
MasterArmyList ['First Army', 'Second Army']
#move an army
#assumes you "know" which army it is
tile1.ArmyList.append(anotherArmy)
tile1.ArmyList ['First Army', 'Second Army']
tile2.ArmyList.remove(anotherArmy)
tile2.ArmyList []

If I didn't have such links, I'd have to search through the entire
army list every time a tile is selected.

Don't even have to reference the master army list (you might not
even need such, if armies are created in known (home base) tiles. Only
reference the list of armies in the tiles.

The only reason for a master army list (perhaps one list for
each "player", is to create a selection menu -- and maybe have a
reference to the current tile in the Army... Beware, you'll have to
break the cycles to do clean-up.

class Army:
def __init__(self, name, tile):
self.Tile = tile
self.Name = name

#using the above tile1 and tile2
army1 = Army("First Army", tile1)
tile1.ArmyList.append(army1)
player1.ArmyList.append(army1) #assuming a class defined for players
....
#similar for army2

#move an army
army2.Tile.ArmyList.remove(army2)
tile1.ArmyList.append(army2)
army2.Tile = tile1 #should make a method to do the
#entire move


--

 

[Innocence]

Why? (indexed links, that is)

Hmm, good point . Thanks for the advice, I'll certainly consider
this approach instead of my original one

0 Innocence