[gameprogrammer] Re: Since we are on the topic of optomized data structures (:

[Madison McGaffin <greyhill@gmail.com>]

On Fri, 2007-07-13 at 13:36 -0700, Alan Wolfe wrote:
> So would you say that doing bounding box collision tests on a culled
> tree would in generally be faster than unique ID tests on an unculled
> tree?
>  
> Just thinking about a 2d bounding box test vs a simple comparison. and
> the culled tree vs the unculled tree
> 
If you wanted to go nuts (and don't care too much about memory or
complexity), you could keep the IDs in a hashtable/map like we were
talking about before and do a really fast lookup using the UID.  AFAIK
what's really great about quadtrees isn't their ability to find a
specific element in a two dimensional collection but a range of
elements.

By the numbers, the 2d bounding box test would run in something like
O(log_4(n)) time, while a hashtable / binary tree would be O(1) or
O(log_2(n))

> On 7/13/07, Matthew Weigel <unique@idempot.net> wrote: 
>         Alan Wolfe wrote:
>         > Heya,
>         >
>         > I have a quad tree which stores objects in it from a 2d
>         world. 
>         >
>         > I was wondering, in general if i wanted to find a node in a
>         quad tree
>         > where i had both the bounding box and a unique id#, would it
>         be more
>         > efficient to just recursively search the tree for the
>         id#?  Or would it 
>         > be more efficient to do the bounding box search to "cull
>         some branches"
>         > of the recursive ID search?
>         
>         Quad trees excel at improving the performance of "finding
>         things in a
>         bounding box."  It doesn't really matter what it is, as long
>         as you have 
>         the bounding box and the individual nodes possess the data you
>         are
>         looking for.  If the tree were ordered with respect to id#s,
>         that would
>         be different, though.
>         --
>         Matthew Weigel
>         hacker
>         unique@idempot.net
>         
>         ---------------------
>         To unsubscribe go to
>         http://gameprogrammer.com/mailinglist.html
>         
>         
>

Attachment: signature.asc
Description: This is a digitally signed message part