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.

for instance,

Key

1. mountain
2. forest
3. swamp
4. impassable ocean

ddddd
dbaad
dcabd
dabbd
ddddd

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.

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

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)
         |*|*| * |
         +-+-+---+
         |*  |   |
         +---+---+
[download]

(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.
[download]

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

• XCOORD
• YCOORD
• TERRAINTYPE

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.

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