Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Map Storage For Game

by dooberwah (Pilgrim)
on Oct 24, 2001 at 01:36 UTC ( #120927=perlmeditation: print w/replies, xml ) Need Help??

I'm helping make a game (written in Perl (that's why I posted it here)) and I'm trying to figure out how to store our map files. Our maps are a large coordinate plane and we'd like it to be able to have different kinds of terrain. One of our first ideas was to store all of our data in a large color-coded bitmap.

We'd like it to be able to tell us what the terrain for any coordinate, say (50, 72). If it helps at all, we are using the MySQL database to store most of our data. Mostly I'm looking for efficient ways to do lookup on our terrain so it doesn't take so much time.

Thanks so much.

-Ben Jacobs (dooberwah)
Homepage: http://dooberwah.perlmonk.org
PGP Public Key: http://dooberwah.perlmonk.org/mykey
"one thing i can tell you is you got to be free"

Replies are listed 'Best First'.
Re: Map Storage For Game
by dragonchild (Archbishop) on Oct 24, 2001 at 01:49 UTC
    1. Identify the smallest granularity in your data set ... the atomic unit, so to speak.
    2. Identify what needs to be known about each atom.
    3. Build and store it as a AoAoH.
    4. Optimize from there.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

      I'm not familiar with the term AoAoH. From the context I think this is some sort of database thing that I havn't covered yet (Like a 1 to Many relationship?). If anyone could explain a bit I'd be grateful.

      -Ben Jacobs (dooberwah)
      Homepage: http://dooberwah.perlmonk.org
      PGP Public Key: http://dooberwah.perlmonk.org/mykey
      "one thing i can tell you is you got to be free"

        Heh.

        Array of Arrays of Hashes. :-)

        The idea I was trying to get across was that you should try to use the most basic data structure and see how it works. If you need to optimize, then do so. But, don't optimize if you don't have to.

        Premature Optimization is the Root of All Evil

        ------
        We are the carpenters and bricklayers of the Information Age.

        Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Re: Map Storage For Game
by boo_radley (Parson) on Oct 24, 2001 at 04:05 UTC
    when I was making tile based games, 'twas all the rage to read in simple text files composed of single characters which determined terrain type.

    for instance,

    Key

    1. mountain
    2. forest
    3. swamp
    4. impassable ocean
    and then have the file look like (for a 5x5 map)
    ddddd
    dbaad
    dcabd
    dabbd
    ddddd
    that tells you which bitmap to place where, see? this doesn't work for most 3d games, of course.
      I've actually toyed with a game system using two values per tile. One is the elevation, and the other the type of ground cover.

      0-9 elevations

      r=rocky, f=forest, g=grassy, w=water, etc.

      This allows for a slightly more complex computation for movement, as movement is normally slower uphill than down, and a game engine could even use the map to figure trajectory differences for missile weapons to nearby tiles and things like that.

      As for using a DB instead of a flat file of keeping it all in memory, I was planning on putting regions encoded like the above into the database, and pulling entire regions from the database into memory when needed, so say you could have a 16-by-16 or 32-by-32 region that gets pulled out when someone is within a certain number of tiles from it, or when someone actually enters it if the game doesn't allow multi-tile vision (depends on style of game and granularity of land areas depicted by the tiles).

      I've worked quite a bit in this area, and I'm always happy to talk about it. I may even be interested in joining a project if that's an option. Perl is a good language for this type of game because of the ease of manipulating the data structures in different ways.

Re: Map Storage For Game
by jackdied (Monk) on Oct 24, 2001 at 03:57 UTC
    It really depends, if the map can fit in memory, use Dragonchild's suggestion.

    If it can't, then use a memory cached version with a backend using DBI or DB_File. Store the most recent requests in the above mentioned style. You'll need some way to expire LRU entries, try a search on CPAN (Tie::Cache::LRU looks handy.)

    -jackdied

Re: Map Storage For Game
by FoxtrotUniform (Prior) on Oct 24, 2001 at 20:25 UTC

    Fast pixel lookup is fairly straightforward, and other people have covered it fairly well, so I'll do something else: spatial lookup.

    You'll probably find yourself wanting to quickly find objects on your map depending on spatial relations (like, "what enemies are within foo units of the player?"). Searching through all the objects for these queries is O(n) (i.e. slow). So, you can subdivide the map into a hierarchy of nodes, stopping when you hit one object per node (or whatever). This lets you do O(log n) lookups. There are many ways of doing this, but the two that you'll probably find most useful for a 2-d plane are quadtrees and kD-trees.

    That didn't make much sense, so here's a quick diagram:

    level 0 +-------+ (4 objects in the node, recurse) |* * * | | | |* | +-------+ level 1 +---+---+ (2 objects in NW node, recurse) |* *| * | +---+---+ |* | | +---+---+ level 2 +-+-+---+ (1 object in each node, stop recursing) |*|*| * | +-+-+---+ |* | | +---+---+

    (Well, the NW node in level 2 should be split into 4, not 2, but you get the idea.) So what we're doing is considering each node, if the node has more than one objects in it, we split it into four child nodes and recurse on each of those.

    This obviously works best for static objects, like map features. Have a look at http://www.tulrich.com/geekstuff/partitioning.html for an adaptation (based on octrees, which are the same thing in 3d). Quadtrees and kD-trees should be covered in any decent graphics book (and if you're a game programmer you have one or two of those, right? :-), but also here: http://www.google.com/search?hl=en&q=quadtree

    Update: how you'd use one of these

    Okay, so what do you do with one of these? Say you want to find all the objects in the quadtree within N units of the player, our original problem. Recurse through the quadtree.

    * If a node's bounding box is outside the N-unit circle, stop. * Otherwise, if the node's a leaf node, check all of the objects inside it and stop. * Otherwise (intersects and isn't a leaf node), recurse on the node's four children.

    Obviously, this is a lot of effort for little gain if you only have a few objects. But if you have hundreds (or thousands, or millions) of objects fairly evenly distributed over the map, discarding huge chunks of them at a time can make a big difference -- and does! This process is O(log n) instead of O(n).

    --
    :wq

Re: Map Storage For Game
by dragonchild (Archbishop) on Oct 24, 2001 at 17:24 UTC
    If you're using DBI, you can also create a table with three rows:
    • XCOORD
    • YCOORD
    • TERRAINTYPE
    Then, you don't have to worry about memory problems - MySQL does it for you. However, you do have the speed-hit from using DBI for simple queries.

    A possible solution to that would be to cache a NxN area around your intrepid explorers and grab that whenever they leave it.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Re: Map Storage For Game
by shotgunefx (Parson) on Oct 25, 2001 at 09:29 UTC
    Does one unit represent a grid (nxn dimension) or a point in space?

    What is the unit of movement? Can objects only move gridsize units at a time or do you need partial movement, where an object could potential be in four "tiles" at once?

    Knowing a bit more about the requirements and limitations can let you do a lot of tricks to speed up things.

    I used to work at a game company years ago and did alot in these areas. If I can help, I'd be glad to give you some advice if it's something I've got experience with. Then again, our target machines where 386SX's so it was mostly done in ASM and some C. Very over optimized. Haven't done any games in Perl yet but the concepts should all translate.

    -Lee

    "To be civilized is to deny one's nature."

      Though nothing is final yet, I think that it's likely that we will have units that can move less than a tile at a time. In Civilization (and FreeCiv) your units, and your cities all take up one tile. We're trying to steer away from this, because in actuality a group of units would be much smaller than a city. We might just fix this problem by having cities be more than a tile in size, but it would be nice to look at all the options before we settle on something.

      -Ben Jacobs (dooberwah)
      Homepage: http://dooberwah.perlmonk.org
      PGP Public Key: http://dooberwah.perlmonk.org/mykey
      "one thing i can tell you is you got to be free"

        It seems like it would make more sense to have your tiles be at the most granular level you can make it. This provides you with the ability to have a more detailed terrain, and keeps the complexity of trying to move a unit only a portion of the way through a tile out of your system. It also gives you larger flexibility with the design of your cities. Cities wouldn't need to be square, they could be oblong shapes if you so desired.
        Having objects move at abitrary rates also brings up problems with collision detection etc. What type of terrain is this? What type of objects? How are they shaped?

        I think making an arbitrary world model in Perl could be slow. It depends on what the criteria is though. How many frames per second do you need?

        -Lee

        "To be civilized is to deny one's nature."

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://120927]
Approved by root
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (6)
As of 2018-07-20 07:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    It has been suggested to rename Perl 6 in order to boost its marketing potential. Which name would you prefer?















    Results (426 votes). Check out past polls.

    Notices?