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