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 | 