I’ve been working on different approaches to speed up the collision detection stage for some while now (mainly for the motor engine and some games). This includes a Quadtree which I started working on last year, but just recently got around to pick it up again. I’m still fine-tuning the code, so I can’t share it at the moment. But, because I added some visualization stuff to help fix some bugs, I thought I could put together a little demo showing the Quadtree in action :).

I’m also thinking of creating another package (like the data structures) which would include some highly optimized broadphase collision detection algorithms, but this depends how much spare time I have – which is very limited at the moment.

But what exactly is a Quadtree ? Generally speaking, it’s a tree structure using a principle called ‘spatial locality’ to speed up the process of finding all possible collisions. Because objects can only hit things close to them, testing against distant objects should be avoided.

The easiest way to quickly compute a collisions set is to divide the collision space (e.g. your game area) into a uniform grid and register each object with all intersecting grid cells. That’s also called spatial hashing. One disadvantage is that it doesn’t cope well with objects of varying sizes. If the grid cells are too big, many unnecessary collision checks are done, and if they are too small, you end up searching many registered cells containing the same object.

The quad tree tries to overcome this weakness by recursively splitting the collision space into smaller subregions, similar to the RDC algorithm, with the difference that every region is divided exactly into 4 smaller regions of the same size, so you end up having multiple grids with different resolutions, where the number of cells in a region goes go up by a power of two every time the resolution is increased. So every object resides in the cell (called quad node or quadrant) with the highest (finest) possible resolution. A search is made by starting at the object’s node and ‘bubbling’ up to the root node. Wikipedia has a nice explanation, and there exist many variations.

The quad tree in the demo contains 1000 objects. I’m not sure if the quad tree is faster than a regular grid, but I’ll compare both versions soon. And don’t be afraid of the memory usage, it needs tons of memory because I’m storing all tree nodes for drawing them on the screen.

A Quadtree containing 1000 objects. (9 levels, leaf size 8x8px)

## 41 thoughts on “Quadtree demonstration”

1. This is great! I actually looked into Quadtrees last night and find the subject really interesting.

Also probably good to note that Octtrees are implementations of the same concept in 3D coordinate spaces.

2. When are you publishing a book? Very cool and quality demos always.

3. Hristo Dachev says:

4. Your work is indeed astonishing and I have full confidence that this engine, once out, will be a revolution.. however you must keep in mind one thing that both APE and Fysix failed, in my mind.

What both these engines attempted to do was to become a game engine in itself. Which is wrong.

When getting a physics engine I’m not looking for a complete game codebase – most likely I already have my own architecture – my own logging, resource management, memory tracking, profiling all in place. As well as, of course, the actual game engine. However my concept of a game engine may differ, for any number of reasons – starting with optimizations for a particular game, diving objects into more than one update groups, and so on.

As such I am incorporating the physics engine into my game engine, having a good idea of what my engine should do. I expect the physics engine to handle just that, physics.

The question is how much should a physics engine do. I would narrow it down to narrow-phase collision testing and response. Sometimes I don’t even need testing and response, just collision testing. Ideally, from my perspective, a physics engine would posess an abstract physical class containing the virtual world X,Y, rotation, mass ect ect.. Ideally I would call such a function if I deemed it appropriate:

myMotor.collisionAndResponse(Array of physicalobjects)

then each physicalobjects X,Y,rotation ect would be properly updated and my engine would then copy the data over to stage X and Y, handling the sccrolling, hidden surface exclusion, ect.

I guess it’s tempting to, after coding so much physical simulations, code the easy stuff like an update engine that makes a hello world application 10 lines long. But in the process you would be taking away power, and let’s face it, physics are no simple thing and whoever wants to use stuff like that must be able to at least write a simple, physics-less game engine.

To sum up, stick to the physics let the end coders handle the rest.

Again I admire your work and would be delighted to take a peek at the current build.

5. hey archont, thanks for your thoughts. don’t worry, the physics will only do what its meant for..physics :) there is only a very basic vector renderer included, mainly used for demo/debugging purposes and which can be disabled globally. what you get in the end is a bunch of objects containing the physical data, an event model (so you can listen to collision events needed for game logic) and methods to add/remove objects/forces/constraints whatever.

6. Glad to hear from you. The interface you’re describing seems to be quite fine, though I’d have to see it to give my word on it :)

I’m sure you hate those kinds of questions but curiosity got the better of me – are you currently planning some general release date? Or do you want to implement a specific set of features with a release date of “when it’s done”?

And most importantly, what about the license? I’m into making flash games commercially however I’m not exactly making a fortune off those ( I’m blaming that on living in the country directly east of you :P) so having a free license would definitely be a blessing.

7. I’m designing a set of three (commercial) games right now and boy, would I use a physics engine.

Due to time constraints on the borderline of absurd I am afraid coding a physics engine for those projects may well be left in the realm of fantasy.

8. Astonishing! Absolutely excellent! i can’t wait to build things with this! Please keep up the great work!

Very impressive !
I’m curious about the method you use for fps calculation. I have 85-96 fps on your demo under firefox. But on all my tests (AS3) I can’t get more than 64 fps under firefox. Even with a empty project which only compute fps I can’t get more.
Can you give me an hint about how you achieve this ?

10. I think it’s because I’m embedding the swf with the wmode parameter set to ‘transparent’. it allows the swf to run inside the browser with almost the same performance as the standalone player.

11. Mike says:

I just wanted to let you know I thought this was a very cool demo, and I was wondering if you’d mind posting the files for it? Thanks for the demos!

12. the quad tree is now included in motor2, you can get it from the repository.

13. Good post. You make some great points that most people do not fully understand.

“The easiest way to quickly compute a collisions set is to divide the collision space (e.g. your game area) into a uniform grid and register each object with all intersecting grid cells. ThatÃ¢â‚¬â„¢s also called spatial hashing. One disadvantage is that it doesnÃ¢â‚¬â„¢t cope well with objects of varying sizes. If the grid cells are too big, many unnecessary collision checks are done, and if they are too small, you end up searching many registered cells containing the same object.”

I like how you explained that. Very helpful. Thanks.

14. Alex says:

Hi Michael, I see you have included the quad tree sources in motor2, as someone else requested. However, would it be possible to upload this specific project?

15. I was also wondering if you could post the source for this specific example as well?

16. OZI says:

hi…am a GIS student n wuld really appreciate it if anyone out there could give me a reasonable link on where i can find some useeful resources that discuss ‘the principle and application of the quadtree data model’explicitly. tanx

17. Great article and demo.

Does the demo have a memory leak? Its constantly using more memory…

1. maybe the rendering causes a memory leak, but in general the garbage collector in flash is very lazy so I’m sure about that.

18. Hi, I’m just starting with physics, so maybe my question will seem utterly stupid, but I am wondering..

If you divide your level into 4 equal leaves, and those into 4 leaves as well etc. When you need to determine the leaf in which an object is, and it is intersecting two small leaves, you will look at their parent or their parent’s parent, until you find a leaf in which the object will be fully inside, right?

If I understand correctly, this will mean that if even a small object is overlapping the exact center of the level, that is, an objects bounding box contains the crossing point of the four biggest leaves, the object is at that moment effectively interacting with all other objects in the game, because the object is only fully within in the top leaf, which is the entire level.

I hope I misunderstood something, because if I am right, this might result in weird results, like a sudden drop in framerate at certain positions in the level.

Or do you have optimizations to overcome this, like a grid dividing the level in quite large sections and quad-tree for dividing it further? Or do you allow objects to be in multiple (at most 4) leaves after all?

1. you are right, in the worst case a very small object can reside in the root node if it’s exactly in the middle BUT as an object gets smaller this happens the less and less often so it’s not really an issue. Otherwise you would have to register an object with all overlapping nodes which is more expensive.

19. Hi,

that’s really cool I think, good work.
I’m trying to implement quadtrees in AS3 too, but I’m not sure if I’m doing right.
Probably you could send me the source code of your project? That would be very cool!

thanks,
Hubert

20. Hi

I had a quick question, maybe you can help me.
I’m trying to figure out the basics of quadtrees and I was wondering the following:
Do you update the quadtree everytime the objects move? Or do you simply create a new one?

Joran

21. I looked trough your code and I allready found the answer! Sorry for bothering you. :)

22. Jonathan says:

Just wanted to mention the shortcomings of quatrees on modern machines and make sure you didn’t miss the article in games programming gems 2: Determining the Tree Level.

Also for the demo you showed here there is the possibility of merely using a 2D array to speed things up.

23. alphachap says:

Your demo is amazing, specially going so fast.
I might try to implement this in Processing (Java).

24. Dubue says:

Great demo. I have one question thought: how to delete object from Quad tree? I can see insert methods in quad tree but no delete or remove methods, am I missing something?

1. which class are you referring to? in motor2 quadtree, there is createProxy() and removeProxy()

25. The strangest thing: when I run the demo on this page, flashdevelop picks up trace output in its output panel, without any apparent connection between the browser page and flashdevelop.
I got:
/**********************************************************
* depth = 9
* unscaled tree size = 128px
* quad node x-scale = 0.125
* quad node y-scale = 0.125
* root node = 1024x1024px
* leaf node = 8x8px
*********************************************************/
start
stop
start
stop

It only does it with your swf, and only since I updated chrome’s flash player to 10.2.154.18.

Do you know how the trace text is being output?

1. Seems I forgot to remove some trace calls. It uses FlashConnect that sends the trace calls through a socket connection to FlashDevelop – so nothing special about it.

26. phillip profitt says:

How do you store overlaps and how do you decide your smallest size?

27. I still haven’t learned how to set up and implement one of these into my game yet, but this example reminds me all the time that it’s something I absolutely need to grasp.