Game - Map data structures

Discussion in 'Python' started by Innocence, Jun 18, 2004.

  1. Innocence

    Innocence Guest

    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
     
    Innocence, Jun 18, 2004
    #1
    1. Advertising

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

    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Home Page: <http://www.dm.net/~wulfraed/> <
    > Overflow Page: <http://wlfraed.home.netcom.com/> <
     
    Dennis Lee Bieber, Jun 18, 2004
    #2
    1. Advertising

  3. 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
     
    =?iso-8859-15?Q?Pierre-Fr=E9d=E9ric_Caillaud?=, Jun 18, 2004
    #3
  4. Innocence

    Sam Holden Guest

    On Fri, 18 Jun 2004 22:58:45 +0200,
    Pierre-Frédéric Caillaud <> 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
     
    Sam Holden, Jun 19, 2004
    #4
  5. 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 && && 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
     
    Erik Max Francis, Jun 19, 2004
    #5
  6. Innocence

    Sam Holden Guest

    On Fri, 18 Jun 2004 18:48:03 -0700, Erik Max Francis <> 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
     
    Sam Holden, Jun 19, 2004
    #6
  7. Innocence

    Dan Bishop Guest

    Innocence <innocence(a)klog(dot)dk> wrote in message news:<>...
    > 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 = ...
     
    Dan Bishop, Jun 19, 2004
    #7
  8. Innocence

    Innocence Guest

    On 19 Jun 2004 02:43:06 GMT, (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
     
    Innocence, Jun 19, 2004
    #8
  9. Innocence

    phil hunt Guest

    On 18 Jun 2004 23:08:27 -0700, Dan Bishop <> wrote:
    >Innocence <innocence(a)klog(dot)dk> wrote in message news:<>...
    >> 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)
     
    phil hunt, Jun 20, 2004
    #9
  10. Innocence

    Mitja Guest

    Innocence <innocence(a)klog(dot)dk>
    (news:) wrote:
    > On 19 Jun 2004 02:43:06 GMT, (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
     
    Mitja, Jun 21, 2004
    #10
  11. 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


    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Home Page: <http://www.dm.net/~wulfraed/> <
    > Overflow Page: <http://wlfraed.home.netcom.com/> <
     
    Dennis Lee Bieber, Jun 22, 2004
    #11
  12. Innocence

    Innocence Guest

    On Tue, 22 Jun 2004 05:26:55 GMT, Dennis Lee Bieber
    <> 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
     
    Innocence, Jun 22, 2004
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. BlackHawke
    Replies:
    12
    Views:
    1,623
    Andrew Thompson
    Jan 26, 2004
  2. judith
    Replies:
    0
    Views:
    1,820
    judith
    Nov 1, 2006
  3. Alfonso Morra
    Replies:
    11
    Views:
    754
    Emmanuel Delahaye
    Sep 24, 2005
  4. Max Kubierschky
    Replies:
    10
    Views:
    1,907
    pabloreda
    Mar 31, 2007
  5. Advertiser for `2D Games Development Central`

    {Game Development} 2D Game Development Central

    Advertiser for `2D Games Development Central`, May 7, 2008, in forum: Java
    Replies:
    2
    Views:
    435
    RedGrittyBrick
    May 8, 2008
Loading...

Share This Page