[gameprogrammer] Re: Since we are on the topic of optomized data structures (:
- From: Madison McGaffin <greyhill@xxxxxxxxx>
- To: gameprogrammer@xxxxxxxxxxxxx
- Date: Fri, 13 Jul 2007 17:44:51 -0400
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@xxxxxxxxxxx> 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@xxxxxxxxxxx
>
> ---------------------
> To unsubscribe go to
> http://gameprogrammer.com/mailinglist.html
>
>
>
Other related posts:
