Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Comment on

( #3333=superdoc: 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:

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


In reply to Re: Map Storage For Game by FoxtrotUniform
in thread Map Storage For Game by dooberwah

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others having an uproarious good time at the Monastery: (4)
    As of 2018-10-17 04:51 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      When I need money for a bigger acquisition, I usually ...














      Results (90 votes). Check out past polls.

      Notices?