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]

Re: Game - Map data structures

On Fri, 18 Jun 2004 15:58:36 +0200, Innocence <innocence(a)kl og(dot)dk>
declaimed the following in comp.lang.pytho n:
[color=blue]
>
> 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:[/color]

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.
[color=blue]
> - 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.[/color]

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.

--[color=blue]
> =============== =============== =============== =============== == <
> wlfraed@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
> wulfraed@dm.net | Bestiaria Support Staff <
> =============== =============== =============== =============== == <
> Home Page: <http://www.dm.net/~wulfraed/> <
> Overflow Page: <http://wlfraed.home.ne tcom.com/> <[/color]

[Pierre-Frédéric Caillaud]

Re: Game - Map data structures


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]

Re: Game - Map data structures

On Fri, 18 Jun 2004 22:58:45 +0200,
Pierre-Frédéric Caillaud <peufeu@free.fr > wrote:[color=blue]
>
> 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[/color]

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

--
Sam Holden

[Erik Max Francis]

Re: Game - Map data structures

Sam Holden wrote:
[color=blue]
> That's going to make it really hard to determine which boats are on a
> given water tile.[/color]

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 && max@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

[Sam Holden]

Re: Game - Map data structures

On Fri, 18 Jun 2004 18:48:03 -0700, Erik Max Francis <max@alcyone.co m> wrote:[color=blue]
> Sam Holden wrote:
>[color=green]
>> That's going to make it really hard to determine which boats are on a
>> given water tile.[/color]
>
> 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.[/color]

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

[Dan Bishop]

Re: Game - Map data structures

Innocence <innocence(a)kl og(dot)dk> wrote in message news:<lts5d0pi0 nhk02ri15pofo6k 7b52n1fi3r@4ax. com>...[color=blue]
> 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.[/color]

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__(s elf, ...)
# data specific to land tiles
self.building = ...

[Innocence]

Re: Game - Map data structures

On 19 Jun 2004 02:43:06 GMT, sholden@flexal. cs.usyd.edu.au (Sam
Holden) wrote:
[color=blue]
>Which imples to me that the water object has an armies list or something
>hanging of it.[/color]

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]

Re: Game - Map data structures

On 18 Jun 2004 23:08:27 -0700, Dan Bishop <danb_83@yahoo. com> wrote:[color=blue]
>Innocence <innocence(a)kl og(dot)dk> wrote in message news:<lts5d0pi0 nhk02ri15pofo6k 7b52n1fi3r@4ax. com>...[color=green]
>> 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.[/color]
>
>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__(s elf, ...)
> # data specific to land tiles
> self.building = ...[/color]

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)

[Mitja]

Re: Game - Map data structures

Innocence <innocence(a)kl og(dot)dk>
(news:b2o8d0t01 m8p1n7e20mv1g1f fb2lb6hbta@4ax. com) wrote:[color=blue]
> On 19 Jun 2004 02:43:06 GMT, sholden@flexal. cs.usyd.edu.au (Sam
> Holden) wrote:
>[color=green]
>> Which imples to me that the water object has an armies list or
>> something hanging of it.[/color]
>
> 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 :)[/color]

If the number of armies is small enough (say 1000, to be on the safe side),
don't worry about performance.
[color=blue]
>
> Thanks :)
>
> 0:) Innocence[/color]

[Dennis Lee Bieber]

Re: Game - Map data structures

On Sat, 19 Jun 2004 17:55:19 +0200, Innocence <innocence(a)kl og(dot)dk>
declaimed the following in comp.lang.pytho n:

[color=blue]
> 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[/color]

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.
[color=blue]
> tile containing one or more armies. That way, if a player clicks a
> tile the game knows which armies exists on that tile.
>[color=green][color=darkred]
>>> anArmy = "First Army"
>>> anotherArmy = "Second Army"
>>> MasterArmyList = [anArmy, anotherArmy]
>>> class Tile:[/color][/color][/color]
.... def __init__(self):
.... self.ArmyList = []
....[color=blue][color=green][color=darkred]
>>> tile1 = Tile()
>>> tile2 = Tile()
>>> tile1.ArmyList. append(anArmy)
>>> tile2.ArmyList. append(anotherA rmy)
>>> tile1[/color][/color][/color]
<__main__.Til e instance at 0x0119DCB0>[color=blue][color=green][color=darkred]
>>> tile1.ArmyList[/color][/color][/color]
['First Army'][color=blue][color=green][color=darkred]
>>> MasterArmyList[/color][/color][/color]
['First Army', 'Second Army'][color=blue][color=green][color=darkred]
>>> #move an army
>>> #assumes you "know" which army it is
>>> tile1.ArmyList. append(anotherA rmy)
>>> tile1.ArmyList[/color][/color][/color]
['First Army', 'Second Army'][color=blue][color=green][color=darkred]
>>> tile2.ArmyList. remove(anotherA rmy)
>>> tile2.ArmyList[/color][/color][/color]
[][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

[color=blue]
> If I didn't have such links, I'd have to search through the entire
> army list every time a tile is selected.
>[/color]
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.ArmyLis t.append(army1) #assuming a class defined for players
....
#similar for army2

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


--[color=blue]
> =============== =============== =============== =============== == <
> wlfraed@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
> wulfraed@dm.net | Bestiaria Support Staff <
> =============== =============== =============== =============== == <
> Home Page: <http://www.dm.net/~wulfraed/> <
> Overflow Page: <http://wlfraed.home.ne tcom.com/> <[/color]

[Innocence]

Re: Game - Map data structures

On Tue, 22 Jun 2004 05:26:55 GMT, Dennis Lee Bieber
<wlfraed@ix.net com.com> wrote:
[color=blue]
>Why? (indexed links, that is)[/color]

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

0:) Innocence