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.

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!

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.

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.)

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...

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

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!

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.

You are negative Troll, but you are also right. =)