470,591 Members | 2,202 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,591 developers. It's quick & easy.

Game - Map data structures

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
Jul 18 '05 #1
11 2530
On Fri, 18 Jun 2004 15:58:36 +0200, Innocence <innocence(a)klog(dot)dk>
declaimed the following in comp.lang.python:

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.

-- ================================================== ============ <
wl*****@ix.netcom.com | Wulfraed Dennis Lee Bieber KD6MOG <
wu******@dm.net | Bestiaria Support Staff <
================================================== ============ <
Home Page: <http://www.dm.net/~wulfraed/> <
Overflow Page: <http://wlfraed.home.netcom.com/> <

Jul 18 '05 #2

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
Jul 18 '05 #3
On Fri, 18 Jun 2004 22:58:45 +0200,
Pierre-Frédéric Caillaud <pe****@free.fr> wrote:

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.

--
Sam Holden
Jul 18 '05 #4
Sam Holden wrote:
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.

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
\__/ We must use time as a tool, not as a crutch.
-- John F. Kennedy
Jul 18 '05 #5
On Fri, 18 Jun 2004 18:48:03 -0700, Erik Max Francis <ma*@alcyone.com> wrote:
Sam Holden wrote:
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.


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.

--
Sam Holden
Jul 18 '05 #6
Innocence <innocence(a)klog(dot)dk> wrote in message news:<lt********************************@4ax.com>. ..
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 = ...
Jul 18 '05 #7
On 19 Jun 2004 02:43:06 GMT, sh*****@flexal.cs.usyd.edu.au (Sam
Holden) wrote:
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
Jul 18 '05 #8
On 18 Jun 2004 23:08:27 -0700, Dan Bishop <da*****@yahoo.com> wrote:
Innocence <innocence(a)klog(dot)dk> wrote in message news:<lt********************************@4ax.com>. ..
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 = ...


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".

--
"It's easier to find people online who openly support the KKK than
people who openly support the RIAA" -- comment on Wikipedia
(Email: zen19725 at zen dot co dot uk)
Jul 18 '05 #9
Innocence <innocence(a)klog(dot)dk>
(news:b2********************************@4ax.com) wrote:
On 19 Jun 2004 02:43:06 GMT, sh*****@flexal.cs.usyd.edu.au (Sam
Holden) wrote:
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 :)


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

Thanks :)

0:) Innocence

Jul 18 '05 #10
On Sat, 19 Jun 2004 17:55:19 +0200, Innocence <innocence(a)klog(dot)dk>
declaimed the following in comp.lang.python:

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 <__main__.Tile instance at 0x0119DCB0> 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
-- ================================================== ============ <
wl*****@ix.netcom.com | Wulfraed Dennis Lee Bieber KD6MOG <
wu******@dm.net | Bestiaria Support Staff <
================================================== ============ <
Home Page: <http://www.dm.net/~wulfraed/> <
Overflow Page: <http://wlfraed.home.netcom.com/> <

Jul 18 '05 #11
On Tue, 22 Jun 2004 05:26:55 GMT, Dennis Lee Bieber
<wl*****@ix.netcom.com> wrote:
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
Jul 18 '05 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by hzy_104 | last post: by
1 post views Thread by Amit | last post: by
5 posts views Thread by el_roachmeister | last post: by
4 posts views Thread by Thomas Paul Diffenbach | last post: by
5 posts views Thread by utab | last post: by
3 posts views Thread by osp | last post: by
29 posts views Thread by Mik0b0 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.