Sign in to follow this  
maxam

Adaptive QuadTree Finished!

Recommended Posts

I finally completed the first version of my quadtree. There are probably still optimizations but im just happy its finished. It has basic object support now but I still have not decided on how to intergrate the Spatial partitioning, Scene manager, scenegraph, blah, blah, blah yet. If you could try it out and tell me if it works, it would help me out, thanks. Nomad QuadTree Test The mouse moves the object. Press escape to exit.

Share this post


Link to post
Share on other sites
It works, but to me it's rather pointless (no offense).
What's the point of you showing it to the community?
My guess is that you created an algorithm that's going to be used in a real life game and wanted some feedback on performance?
Hence I suggest that you make your test application more game like, i.e having more "objects" for starters (around the thousands), maybe letting the user add / remove objects.
Second I also suggest that you allow a good deal of the objects to move (automatically), say 10% of the total number of objects move in some pseudo random way.
Third the timing is just measured in fps, this does only give you an indication on how fast the test application is, not how fast your dynamic spatial system is.
I suggest that you include some timers for "system update" i.e the time it takes to move the objects around.
Furthermore you need to think about what queries your game want's to be able to perform, the most common beeing what objects are visible within this frustum (set of planes).
Maybe having a ray-casting query? Give me the N closest objects from point P?
Some of these tests should also be performed by the test application (and timed).
Doing some of the above will get you a better understanding of the scalability of your algorithm and frankly right now it's probably faster to rebuild the complete quadtree every frame (or even bruteforce the queries needed).
I'd also suggest that you used rectangles or circles instead of points, since for the most applications objects aren't points but rather have area/volume.

I find it nice that someone more than me has realized that having a good and fast dynamic spatial data structure is one of the most important systems for a game.. keep it up!

Share this post


Link to post
Share on other sites
I looked at the app, but it seems to be locked to the refresh rate of my screen (60Hz), so I can´t say anything about performance, but it worked.


Seems like I am at the right location to ask about something that has been bothering me for quite a while:
I´ve implemented a simple (and I mean _simple_) quad-tree for my game-engine, mostly for frustum culling of a static map, that is close to being planar. Now I have a problem with that: My maps aren´t going to be quadratic, most likely they´ll be much wider than they are high. Now this is a problem, since ideally I would like to have leaf nodes in my tree to be just as big as the tiles I use are (or a multiple of that). So I have the problem of partitioning a rectangle (the map) into quadratic leaf nodes and packing them together into parent nodes in an efficient manner. So any clues about something like that would be helpful.

Sry to abuse this thread, but it just seemed to fit perfectly.

Share this post


Link to post
Share on other sites
Quote:
Original post by matches81
I looked at the app, but it seems to be locked to the refresh rate of my screen (60Hz), so I can´t say anything about performance, but it worked.


Seems like I am at the right location to ask about something that has been bothering me for quite a while:
I´ve implemented a simple (and I mean _simple_) quad-tree for my game-engine, mostly for frustum culling of a static map, that is close to being planar. Now I have a problem with that: My maps aren´t going to be quadratic, most likely they´ll be much wider than they are high. Now this is a problem, since ideally I would like to have leaf nodes in my tree to be just as big as the tiles I use are (or a multiple of that). So I have the problem of partitioning a rectangle (the map) into quadratic leaf nodes and packing them together into parent nodes in an efficient manner. So any clues about something like that would be helpful.

Sry to abuse this thread, but it just seemed to fit perfectly.


Easy answer: make the quadtree "go off the bottom" of your map.

With the ability for nodes that are completey off the map to "stub out" (all of my children are off the map, therefore I have no children), your memory usage for your quad tree doesn't get crazy, even with a very skinny very long map.

(at worse, you have twice as many nodes as a quad-like-tree optimized for exactly your map shape, based off a 1 x K map using a duo-tree, the worst-case scenerio.)

Share this post


Link to post
Share on other sites
Quote:
Original post by matches81
I looked at the app, but it seems to be locked to the refresh rate of my screen (60Hz), so I can´t say anything about performance, but it worked.


Seems like I am at the right location to ask about something that has been bothering me for quite a while:
I´ve implemented a simple (and I mean _simple_) quad-tree for my game-engine, mostly for frustum culling of a static map, that is close to being planar. Now I have a problem with that: My maps aren´t going to be quadratic, most likely they´ll be much wider than they are high. Now this is a problem, since ideally I would like to have leaf nodes in my tree to be just as big as the tiles I use are (or a multiple of that). So I have the problem of partitioning a rectangle (the map) into quadratic leaf nodes and packing them together into parent nodes in an efficient manner. So any clues about something like that would be helpful.

Sry to abuse this thread, but it just seemed to fit perfectly.


Use a Portal System instead. (or Portal-like system)

How about some kind of hybrid system? on the topmost layer, treat the wide map as a row of square sectors, then within each sector do a normal square quadtree?



PS
I can see how a quadtree is usefull for frustum culling large areas with minimal checks

but for collision detection, is it all that great? wouldnt a Uniform Grid Space Partition be faster for that case? O(1) cell identification... as opposed to doing a tree transversal...

Share this post


Link to post
Share on other sites
Works a treat. I get 1800 FPS (probably more if it had a fullscreen mode). Mouse movement was slow. It took numerous traversals of the mouse over the mat to get the object to move across the grid. Other than that, good job. Hope to see you put it to good use soon. I would agree with the suggestions by Eq on really testing out your implementation.

F451

Share this post


Link to post
Share on other sites
Quote:
Now I have a problem with that: My maps aren´t going to be quadratic, most likely they´ll be much wider than they are high. Now this is a problem, since ideally I would like to have leaf nodes in my tree to be just as big as the tiles I use are (or a multiple of that). So I have the problem of partitioning a rectangle (the map) into quadratic leaf nodes and packing them together into parent nodes in an efficient manner. So any clues about something like that would be helpful.


Do you have Game Programming Gems book series on your shelf? In one of them (don't remember which exactly) there's a whole chapter about quadtrees, and there's explained how to deal with problems similar to the one you have. In short: deep inside quadtree subsystem, scale coordinate values of all points, so that point which lies max on the left has value 0, and the one which lies max on the right has value of ie. 256. Do it seperately for both axes, do it for all coordinates that user passess to you, and it should be enough. Hmmm, AFAIK it was sth like that ;-) you should read it by yourself.


Maxam: I didn't tried your demo, but it looks nice on the screen. Btw, are sources included? If yes, then I would have really good reason to download and see your demo ;-)

Quote:

I can see how a quadtree is usefull for frustum culling large areas with minimal checks

but for collision detection, is it all that great? wouldnt a Uniform Grid Space Partition be faster for that case? O(1) cell identification... as opposed to doing a tree transversal...


...and what about memory usage for very big levels? There would be 1000s of cells in grid, and only 1 quadtree node, in case of a level in which all objects are in one corner.

...and what to do when objects can be very big, when their size can reach ie. half the level size? In the simplest implementation, grid cells would need to also be that big (rendering them useless), but quadtree would adapt to that situation very easily.

Share this post


Link to post
Share on other sites
That's awesome! It's one of the things I need to work on in my engine soon, though I got sidetracked on the physics engine. Good to know it's possible.

One comment though, is what happens to objects that straddle across boundaries. I notice the objects are always at the bottom level, but if the object is big enough to straddle across two bottom level boundaries, shouldn't it belong to the parent node?

Great work!

Share this post


Link to post
Share on other sites
I hate to be negative, but isn't your quadtree working incorrectly? The upper-right quadrant doesn't need to be subdivided beyond the initial division. In every case, you've subdivided the space too far. You don't need to subdivide down to the maximum depth every time. It makes your queries run slower because you have to query more quads down further depths.

Share this post


Link to post
Share on other sites
Quote:
Original post by Koshmaar

Quote:

I can see how a quadtree is usefull for frustum culling large areas with minimal checks

but for collision detection, is it all that great? wouldnt a Uniform Grid Space Partition be faster for that case? O(1) cell identification... as opposed to doing a tree transversal...


...and what about memory usage for very big levels? There would be 1000s of cells in grid, and only 1 quadtree node, in case of a level in which all objects are in one corner.

...and what to do when objects can be very big, when their size can reach ie. half the level size? In the simplest implementation, grid cells would need to also be that big (rendering them useless), but quadtree would adapt to that situation very easily.


Those are both extreme cases, if I'm building a level/map where neither of those applies, would I be better off using the grid partition?

for the 'big object' problem btw... while i dont have that issue, could you solve it by allowing the giant object to reside in multiple cells at once and keep the cells the average size of most objects?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this