Perl: the Markov chain saw | |
PerlMonks |
Re: Map Storage For Gameby FoxtrotUniform (Prior) |
on Oct 24, 2001 at 20:25 UTC ( [id://121164]=note: print w/replies, xml ) | Need Help?? |
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:
(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.
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).
--
In Section
Meditations
|
|