# Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

##### Tutorial Details
• Experience Level: Intermediate
• Platform Used: Java
• Estimated Completion Time: 15 minutes

Many games require the use of collision detection algorithms to determine when two objects have collided, but these algorithms are often expensive operations and can greatly slow down a game. In this article we’ll learn about quadtrees, and how we can use them to speed up collision detection by skipping pairs of objects that are too far apart to collide.

Note: Although this tutorial is written using Java, you should be able to use the same techniques and concepts in almost any game development environment.

## Introduction

Collision detection is an essential part of most video games. Both in 2D and 3D games, detecting when two objects have collided is important as poor collision detection can lead to some very interesting results:

However, collision detection is also a very expensive operation. Let’s say there are 100 objects that need to be checked for collision. Comparing each pair of objects requires 10,000 operations – that’s a lot of checks!

One way to speed things up is to reduce the number of checks that have to be made. Two objects that are at opposite ends of the screen can not possibly collide, so there is no need to check for a collision between them. This is where a quadtree comes into play.

A quadtree is a data structure used to divide a 2D region into more manageable parts. It’s an extended binary tree, but instead of two child nodes it has four.

In the images below, each image is a visual representation of the 2D space and the red squares represent objects. For the purposes of this article, subnodes will be labelled counter-clockwise as follows:

When more objects are added to the quadtree, it will eventually split into four subnodes. Each object will then be put into one of these subnodes according to where it lies in the 2D space. Any object that cannot fully fit inside a node’s boundary will be placed in the parent node.

Each subnode can continue subdividing as more objects are added.

As you can see, each node only contains a few objects. We know then that, for instance, the objects in the top-left node cannot be colliding with the objects in the bottom-right node, so we don’t need to run an expensive collision detection algorithm between such pairs.

Take a look at this JavaScript example to see a quadtree in action.

Implementing a quadtree is fairly simple. The following code is written in Java, but the same techniques can be used for most other programming languages. I’ll comment after each code snippet.

We’ll start off by creating the main Quadtree class. Below is the code for `Quadtree.java.`

```public class Quadtree {

private int MAX_OBJECTS = 10;
private int MAX_LEVELS = 5;

private int level;
private List objects;
private Rectangle bounds;

/*
* Constructor
*/
public Quadtree(int pLevel, Rectangle pBounds) {
level = pLevel;
objects = new ArrayList();
bounds = pBounds;
}
}
```

The `Quadtree` class is straightforward. `MAX_OBJECTS` defines how many objects a node can hold before it splits and `MAX_LEVELS` defines the deepest level subnode. `Level` is the current node level (0 being the topmost node), `bounds` represents the 2D space that the node occupies, and `nodes` are the four subnodes.

In this example, the objects the quadtree will hold are `Rectangles`, but for your own quadtree it can be whatever you want.

Next, we’ll implement the five methods of a quadtree: `clear`, `split`, `getIndex`, `insert`, and `retrieve`.

```/*
*/
public void clear() {
objects.clear();

for (int i = 0; i < nodes.length; i++) {
if (nodes[i] != null) {
nodes[i].clear();
nodes[i] = null;
}
}
}
```

The `clear` method clears the quadtree by recursively clearing all objects from all nodes.

```/*
* Splits the node into 4 subnodes
*/
private void split() {
int subWidth = (int)(bounds.getWidth() / 2);
int subHeight = (int)(bounds.getHeight() / 2);
int x = (int)bounds.getX();
int y = (int)bounds.getY();

nodes[0] = new Quadtree(level+1, new Rectangle(x + subWidth, y, subWidth, subHeight));
nodes[1] = new Quadtree(level+1, new Rectangle(x, y, subWidth, subHeight));
nodes[2] = new Quadtree(level+1, new Rectangle(x, y + subHeight, subWidth, subHeight));
nodes[3] = new Quadtree(level+1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
}
```

The `split` method splits the node into four subnodes by dividing the node into four equal parts and initializing the four subnodes with the new bounds.

```/*
* Determine which node the object belongs to. -1 means
* object cannot completely fit within a child node and is part
* of the parent node
*/
private int getIndex(Rectangle pRect) {
int index = -1;
double verticalMidpoint = bounds.getX() + (bounds.getWidth() / 2);
double horizontalMidpoint = bounds.getY() + (bounds.getHeight() / 2);

// Object can completely fit within the top quadrants
boolean topQuadrant = (pRect.getY() < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint);
// Object can completely fit within the bottom quadrants
boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint);

// Object can completely fit within the left quadrants
if (pRect.getX() < verticalMidpoint && pRect.getX() + pRect.getWidth() < verticalMidpoint) {
index = 1;
}
index = 2;
}
}
// Object can completely fit within the right quadrants
else if (pRect.getX() > verticalMidpoint) {
index = 0;
}
index = 3;
}
}

return index;
}
```

The `getIndex` method is a helper function of the quadtree. It determines where an object belongs in the quadtree by determining which node the object can fit into.

```/*
* Insert the object into the quadtree. If the node
* exceeds the capacity, it will split and add all
* objects to their corresponding nodes.
*/
public void insert(Rectangle pRect) {
if (nodes[0] != null) {
int index = getIndex(pRect);

if (index != -1) {
nodes[index].insert(pRect);

return;
}
}

if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
if (nodes[0] == null) {
split();
}

int i = 0;
while (i < objects.size()) {
int index = getIndex(objects.get(i));
if (index != -1) {
nodes[index].insert(objects.remove(i));
}
else {
i++;
}
}
}
}
```

The `insert` method is where everything comes together. The method first determines whether the node has any child nodes and tries to add the object there. If there are no child nodes or the object doesn’t fit in a child node, it adds the object to the parent node.

Once the object is added, it determines whether the node needs to split by checking if the current number of objects exceeds the max allowed objects. Splitting will cause the node to insert any object that can fit in a child node to be added to the child node; otherwise the object will stay in the parent node.

```/*
* Return all objects that could collide with the given object
*/
public List retrieve(List returnObjects, Rectangle pRect) {
int index = getIndex(pRect);
if (index != -1 && nodes[0] != null) {
nodes[index].retrieve(returnObjects, pRect);
}

return returnObjects;
}
```

The final method of the quadtree is the `retrieve` method. It returns all objects in all nodes that the given object could potentially collide with. This method is what helps to reduce the number of pairs to check collision against.

## Using This for 2D Collision Detection

Now that we have a fully functional quadtree, it’s time to use it to help reduce the checks needed for collision detection.

In a typical game, you’ll start by creating the quadtree and passing the bounds of the screen.

```Quadtree quad = new Quadtree(0, new Rectangle(0,0,600,600));
```

At every frame, you’ll insert all objects into the quadtree by first clearing the quadtree then using the `insert` method for every object.

```quad.clear();
for (int i = 0; i < allObjects.size(); i++) {
}
```

Once all objects have been inserted, you’ll go through each object and retrieve a list of objects it could possibly collide with. You’ll then check for collisions between each object in the list and the initial object, using a collision detection algorithm.

```List returnObjects = new ArrayList();
for (int i = 0; i < allObjects.size(); i++) {
returnObjects.clear();

for (int x = 0; x < returnObjects.size(); x++) {
// Run collision detection algorithm between objects
}
}
```

Note: Collision detection algorithms are beyond the scope of this tutorial. See this article for an example.

## Conclusion

Collision detection can be an expensive operation and can slow down the performance of your game. Quadtrees are one way you can help speed up collision detection and keep your game running at top speeds.

Note: Want to add some source code? Type <pre><code> before it and </code></pre> after it. Find out more
• http://www.gemfruit.com Porter

Talk about weird, I just emailed Michael a few hours ago requesting someone do a post on quad trees. I’m slightly concerned, and more so excited; thank you sir.

• http://blog.sklambert.com/ Steven Lambert

I’m glad I could help out. I hope you found what you were looking for and good luck!

• kah shiu

Hi, great tutorial. Some questions though. All objects will be classified into region 1~4 right? So what about those objects that lie on the border? (referring to the first quadtree image) If it’s left in the parent node, then collision will not be checked against objects in any of the quads, which could potentially omit a collision detection. Looking forward to your reply.

• http://blog.sklambert.com/ Steven Lambert

Hey kah shiu, good question.

You are correct in that objects that lie on a border will be put into the parent node. This happens because the object could potentially collide with objects in at least two subnodes as you pointed out. The retrieve method takes care of this issue by returning all objects in parent nodes as well as the objects in the subnode.

For example, if we look at the second image there is one object in the parent node (the one that crosses the border between nodes two and three), three in the first subnode, three in the second, two in the third, and two in the fourth. If we wanted the top left square, the retrieve object would return the one object in the parent node as well as the three objects in the second subnode, for a total of four objects. This ensures that no potential collision detection is omitted.

Because of this however, any objects in parent nodes will be checked against all four subnodes, leading to some extra checks. There isn’t a good way around it, but it still reduces the number of pair checks considerably.

I hope this answered your question, and I’m glad you liked the article. Please let me know if you have any other questions or if I can clarify anything more for you.

Steven

I figured out a nice optimization for collision detection the other day. Instead of checking distance between two objects every frame, you store the distance in memory and see when the next possible time that the two objects could collide is. For example, if object A is 100 units away from object B, and they both move at a rate of 5 units per second, you don’t have to perform another distance check until another 10 frames. The combined speed of the two objects is 10 units/s, so it’s not possible that they will collide before they have enough time to cover the gap between them. The only downside is the memory usage (n^2 integers), but it’s only a problem if you have a crazy amount of objects.

• Timo

Hi, thanks for the article, interesting read!

I implemented your methods into a javascript class, you can check it out here:
Demo: http://jsfiddle.net/2dchA/

I’m wondering about one thing: the retrieve-method in my implementation does not return the values that I expected, when the given rect overlaps the borders of a node.
You can see this in the JS-Fiddle Demo. As long as the green rect stays inside the bounds of a node, everything works fine. (You can move it with the mouse.)
But as soon as it overlaps any node borders, the method does not return objects inside the nodes nearby.

Is this behaviour “correct”? I don’t think so …

• Timo

Overthinking the retrieve function, I came to a solution that adresses that problem.
What I changed:

When getIndex in the retrieve function returns “-1″ (given pRect does not fit into a single subnode), you only add the objects that are directly in the parent node to returnObjects, but you don’t add all the objects in subnodes.

I added a for loop for that case, retrieving all objects of the current parents subnode.

Please take a look at line 154 and following and tell me what you think:

Git and JS-Fiddle is updated, I think it now behaves like it should.

• http://blog.sklambert.com/ Steven Lambert

Hey Timo,

I love the JS-Fiddle you created, that is an awesome visual demonstration of a quadtree and I’m glad to see the program taken beyond just Java.

As for the concern with the retrieve method, this isn’t really a problem at all depending on how you write the collision detection. It is true that the retrieve method will not return any subnode’s objects when the object crosses a node’s boundary. Thus using that object alone for testing collision detection will not work properly.

However collision detection involves at least two objects, so even though the object crossing a node’s boundary will not return proper collision with other objects in subnodes, the other objects (which would be in subnodes) will return correct collision since the retrieve method returns all objects in parent nodes. Therefore when you find collision, the algorithm should set both objects collision. This will ensure that all collision detection cases are found and handled, and doing so makes the quadtree perform faster and more efficient.

Adding a loop to get all subnode’s objects in the retrieve method would allow you to have proper collision detection for every object, so it just depends on how the collision detection works to say which way is better for your code.

Steven

• Timo

Hi Steven,

Guess you are right there! For the way I’m currently thinking of my collision detection, the subnode loop feels right.

Just for the record, this is the latest working fiddle: http://jsfiddle.net/2dchA/2/

• Zachary Higginbotham

I love the article, but i am running into a problem when implementing it. Whenever there are more than the MAX_OBJECTS cross a set of axis’s (aka they go in the parent node, I hope i am explaining this properly) it doesn’t add anything past that, so all it’s children are empty. I have been working on it all day and have not been able to fix it. If anyone knows what causes this i would love some help.

• Zachary Higginbotham

AHA! Figured it out right after i posted this. When the axis’s exceeded the max, a split() would happen, but when the axes had more than the MAX_OBJECTS, it would not get rid of any in that list, so next time one was inserted on the axis, it would re-split, which would override the previous split and all objects added. The solution was to change split() in insert into If(node[0] == null){split()}. This makes sure that nothing is overridden.

• Timo

Hi Zachary!
I had the same issue while implementing, and solved it the same way.

• http://blog.sklambert.com/ Steven Lambert

Good catch Zachary and Timo. I’ll get that fixed as soon as I can. Good job finding a solution for it!

Steven

• Greg

Nice article. I have also found an RTree to be a nice way to go for this sort of thing. It might work as well, depending on your needs. This link had a nice comparison chart:

This is a nice java implementation of an RTree that I have liked, it’s fairly easy to integrate, performs well, and has some decent tests around it:

http://jsi.sourceforge.net/

• http://blog.sklambert.com/ Steven Lambert

Glad you liked it. I hadn’t heard of RTrees before, thanks for the comment about them. The link was a great summary of when each tree would be good to use. Keep up the good work!

Great tutorial. I would like to implement it in my game engine. And a small doubt.

In your class, you implemented MAX_LEVELS. Why is this?

private int MAX_LEVELS = 5;

• http://gamedev.tutsplus.com Michael James Williams

I believe this defines how many times a box can be split into smaller boxes :)

• http://blog.sklambert.com/ Steven Lambert

The MAX_LEVELS variable’s main purpose is to prevent chain splitting of a node, and it keeps our quadtree manageable and easier to work with.

Lets say you have a node with enough objects in it to split (lets say 10). What would happen if all 10 objects were stacked on top of each other (or very close to one another) in a corner? The node would split and put all the objects into the same child node, which would then cause that node to split, putting all objects into its child node. This would continue until the last node was small enough to not encompass all 10 objects (which would be a lot of splits!). This reduces the effectiveness of the quadtree and makes it really big and unmanageable.

So the MAX_LEVELS is a stopping point of node splitting. Since each node is assigned a level when it’s created, MAX_LEVELS tells the node that if it’s level is the MAX_LEVEL, don’t split any further and allow objects to just accumulate in the node.

I hope that answered your question, and good luck with your game! Let me know if there’s anything else I can clarify.

• Russel Winder

I am not sure why the clear method traverses the tree. Why not:

public void clear() {

if ( level == 0 ) {
objects = null;
}
}

and just let the garbage collector clear things as unreachable?

The reason the clear method traverses the tree is because some languages do not have good garbage collection (such as C). So to ensure that the method would work well in most languages, the clear method allows for self cleaning. And I always like cleaning up after myself anyway.

In Java though, you would be fairly safe to let the garbage collector clean things up for you, though the if( level == 0 ) statement is unnecessary since you’ll only be calling clear() on the root node which is always level 0.

• Seige

My only complaint about this tutorial is that you say if there are 100 objects, in a brute-force collision test, you’re doing 10000 tests. This is false. Rather, you need to do 9900 tests, as there’s no point to testing for collision against itself. Minor error, but irked me a bit.

You are correct that the math isn’t completely correct. However, I simplified the math to stress the point that doing collision detection can be expensive.

Regardless, the number of checks is dependent on the algorithm used. A purely brute-force, non-optimized algorithm could take 10000 checks. A more efficient and optimized algorithm would take 4950 checks (a collision detection algorithm is equivalent to the handshaking problem, whose equation is n(n-1)/2, or nCr of 100C2. Please see http://answers.yahoo.com/question/index?qid=20080125074153AAeV9p0 for more information).

• Dpaz

I am a beginner when it comes to collision detection, and I want to thank you for putting together a practical example. That said, I do have a question.

Why are we clearing and inserting every object in the game at every frame? Is there a valid reason we would not maintain a list of objects which have actually moved or scaled, remove/insert them, and then run collision detection and/or “unsplitting” only in the relevant quadtree nodes?

Thanks again.

That’s a really good question Dpaz, thanks for bringing it up.

As you pointed out, having to clear the quadtree every frame only to repopulate it is a bit cumbersome. It would be a lot nicer if we could only remove those objects that have actually moved and leave the rest where they are in the tree. Although this sounds easy, it’s a bit complicated to perform and may or may not be better.

The main problem is that the quadtree does not keep track of individual objects, but groups of objects. It doesn’t make a distinction between the individual objects it holds. To be able to remove a specific object, you would have to develop a method for storing where the object is in the tree, as well as which object of the group of objects is the one you are looking for. One way to do this could be to find which subnode the object belongs to then loop over each object in that subnode until you find the one you are looking for. However, this adds a lot of time to the animation loop.

Because of the complexity of trying to remove an object and the added time required to do so, it becomes easier and more efficient just to clear the entire tree and add all the objects back into it after moving objects around.

I hope I was able to answer your question, and I’m glad you found the article helpful. Please let me know if there are any other questions you have.

Steven

• Poersch

Great article – it helped me to improve my quadtree code alot! I found a possible slowdown in the insert function:

Let us assume nodes[0] is not null, pRect lies in the centre of the quad, so index is -1, we add pRect to the object list.

We already know it is not possible that pRect fits within one of the nodes (index == -1), and we know that objects.size() has already exceeded MAX_OBJECTS once (because of nodes[0] != null), that means objects contains only Rectangles wich won’t fit within one of the nodes – still the while loop (possibly) gets executed.

I think the following code should do the trick (not tested):

public void insert(Rectangle pRect) {

if (nodes[0] != null) {

int index = getIndex(pRect);

if (index != -1) {

nodes[index].insert(pRect);

} else {

}

} else if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {

if (nodes[0] == null) {

split();

}

for(Iterator iterator = objects.iterator(); iterator.hasNext();) {

Rectangle cRect = iterator.next();

int index = getIndex(cRect);

if(index != -1) {

iterator.remove();

}

}

}

}

And I replaced the List.get() and List.remove() methods with an iterator (wich should be considerably faster).

I hope I did not totally miss the point. (And sorry for my bad english)

• Poersch

Sorry for the strange “” at the end… and the double post. :-)

• Poersch

Just tweaking the retrieve function a little to avoid some unwanted getIndex() calls in the leave nodes:

public List retrieve(List returnObjects, Rectangle pRect) {
if (nodes[0] != null) {
int index = getIndex(pRect);
if (index != -1) {
nodes[index].retrieve(returnObjects, pRect);
}
}
return returnObjects;
}

nodes[index].insert(objects.remove(i))
What in the hell is happening here? I’m implementing this into C#, but even in Java when using this method it only returns a boolean, so how are you sending it to a method that requires a Rectangle?

• StevenKLambert

Ya, in JavaScript the method returns the removed object, which allows you to insert it into the subnode. If you’re implementing it in C# or Java, you’ll have to add the object first to the subnode first, then remove it from the array. If you’re using an ArrayList for the objects, it would look something like this:

if (index != -1) {
nodes[index].insert(objects.get(i));
objects.removeAt(i);
}
else {
i++;
}

we only increment the variable `i` if we the object isn’t put into a subnode because the remove function will shift all the objects down 1 index for us.

Alright, I realized there was something else I didn’t understand. If our collision algorithm is ran on the list of returned objects (which is refreshed every frame mind you), how would it effect the actual objects in their actual arrays/lists?

• StevenKLambert

Since the quadtree only sets the `isColliding` variable of the objects, it doesn’t affect the objects in their actual arrays/lists. The actual arrays/lists remain unchanged throughout the entire process. All the quadtree does is organize the objects of those lists into pieces that can be used to access them quickly.

Ok, but then why are collision algorithms being ran on the returnObjects? Wouldn’t we want our collision code to be ran on the actual objects? Also, how would it set the isColliding variable of the original objects if the quad tree puts all of the objects into its own array list separate from the original?

I guess what (part of it at least) I’m trying to ask is where is the link? I’m not understanding how the objects in the quadtree’s return list communicate with their counterparts in the original list so you know which original objects to run the collision algorithm on.

• StevenKLambert

Sorry, I just realized that this tutorial did not go over anything such as an `isColliding` variable! My bad. I got my codes mixed up :P

List returnObjects = new ArrayList();
for (int i = 0; i < allObjects.size(); i++) {
returnObjects.clear();

for (int x = 0; x < returnObjects.size(); x++) {
// Run collision detection algorithm between objects
}
}

When you use the `retrieve()` method of the quadtree, you pass it an object (which you got from the original list of objects). The method returns another list of objects, with this list being the objects the original object shares nodes with. By looping over the returned objects and running a collision detection algorithm between the original object and each returned object in turn, you are able to know when the original object (from the original list) collides with any object, and therefore do whatever you need to do with the original object.

Thank you, that clears up a lot! I misread the final part of the tutorial so rereading that also clarified some of it as well. I’m wondering about when the object sent to the QuadTree’s retrieve method collides with a returned object how you would know which original object corresponds to the returned object that experienced a collision with the object sent to the QuadTree’s retrieve method? Sorry if that is confusing, I tried to word it as clearly as possible.

I’d like to the note that it seems to be working now in my game except for the enormous drop in performance which is almost certainly being caused by something I’ve done wrong in the code. I’m not exactly sure what could be causing it.

Nvm, I think I understand now. You have to pass it every original object you want to have an effect when colliding with something else, it just doesn’t have to be checked against everything.

Great tutorial, but Im running into a bit of an issue with the retrieve method. I’m building this code in C#.

From what I can tell by debugging everything in my list of three objects get inserted and indexed correctly. But when calling the retrieve method, it never returns any matches. All three objects are in the exact same place and I have confirmed they are indexed the same way.

Bellow are two gists to my Quadtree.cs class and the main class calling it.

TestBed.cs
https://gist.github.com/ismyhc/4747273

https://gist.github.com/ismyhc/4747262

Any help much appreciated!

Okay, so I actually figured out my problem. In my Retrieve method I was returning the empty list instead of the objects.

Ive updated the gists.

Everything seems to be working now except for on odd issue I am seeing. Im linking to a video that shows the behavour.

I change the color of the moving objects to red when they are returned from the Retrieve method as a possible collision. For whatever reason the object on the bottom quadrant apparent does one check everytime it crosses the into or out of the left and right bottom quadrants. Why is this?

One thing different about my setup is that 0,0 is the center of the screen. positive number to the right, and top.

Any ideas?

Thanks!

Well, I figured this out too. Def had to change up how I calculated which index the object belonged too.

Now, hopefully my final question. How do you handle when an object is in multiple quads? Say if the you object is intersecting two quads, or even four?

• StevenKLambert

Hey Jacob,

Nice work figuring out your own questions! Sorry I wasn’t available to answer them.

To answer your question about the object entering “possible collision” as it passed from one major quadrant to another is that the object gets placed into the root’s object array as it passes over multiple quadrants because it could belong to multiple quadrants at the same time. This causes the retrieve method to return it to ensure that it doesn’t collide with any other objects that belong to those subnodes.

As for the question with multiple quads. I’m not sure how that would work. I only know how 1 quadtree works and have not seen multiple quad trees in action at the same time. Sorry I couldn’t be of more help.

No prob! I always feel a sense of accomplishment when I end up figuring out my own questions!

What I am trying to do now is assign an object more than one index at a time if its spanning more than one index. For instance say the object is spanning the verticalMidpoint. Which index should it belong to? I would think it should be in both. Reason being that if I have assigned to one of the two possible then if another object was only in the index I didn’t assign it to then its very possible I could miss a collision.

What Im working on now is returning a list indexes instead of just one index. I think what Im working on is going to work, but you can never be to sure! Ill post some video if it does ;)

So I actually got this to work. Or its working in my test! I plan on implementing this into my iOS retro space shooter.

Below is a video of the quadtree returning multiple indexes when the rect overlaps the vertical midpoint, horizontal midpoint, or both!

Thanks again for the tutorial. It helped me alot!

• StevenKLambert

No problem, glad you were able to get this working!

I am curious though, what is your frame rate at with the additional overhead of adding the object to multiple subnodes of the quadtree? Do you constantly achieve 60FPS? If so, I’d like to know what you did haha.

Actually Im getting a pretty consistent 60FPS on my macbook pro. This is with 500 objects too!

Ive created a webplayer version of the test. It gets a consistent 59-58FPS. The number of objects is pretty extreme so I have to say Im pretty happy with it so far. My next step is to implement this into my current game.

Let me know what you think!

• StevenKLambert

That is pretty sweet! Awesome to see that it gets really good FPS. So what was the secret to add an object to multiple subnodes?

Well first off I modified the getIndex method to return a List. Inside of the the getIndex method I did calculations to find when an object was in both top and bottom quads. Then also calculated when the object was in both left and right quads. Once I determined that then I just simply added the indexes to the list. Then I had to modify the calls to the getIndex function to handle more than one index returning.

Probably easier just to show you the class ;)

There are probably room for improvements, but this is implementation I have so far.

https://gist.github.com/ismyhc/4747262

Improvement suggestions are welcome ;)

• Massimo

Probably an int[] would be more performant than a List. Since an object can be in 4 quadrants at time, an int[4] is all you need. Plus you can declare it as a field (and not a variable) and allocate it one time only.

• Yakobu

I implemented a Quadtree, inspiring myself from your tutorial, but for my current small 2D game project.

I would really appreciate though if you could check it to see if it is accurate.

https://gist.github.com/Yakobu/fb45c31d18e98c530a55

I have a file called QuadTree, being the QuadTree, should be accurate I think, but mind to see if it is really?

Also included in the file MainPanel the function I created, following your explanation, but mind to explain line 12 to 14? I am REALLY not sure if that’s what you meant, plus explain to me what does it do in more details even if it is accurate. As last, my detection algorithm just below,I have my doubt how it would work, if it does, if not, how to solve?

• http://sklambert.com/ Steven Lambert

Hey Yakobu,

Very nice implementation of the quadtree. I looked over what you asked me to, and here are my suggestions:

For the `hasCollision` function, lines 13 and 14 should be the outer for loop, and lines 17 to 21 should be an inner for loop. As it is currently written in your file, it doesn’t really do anything. It should be written as follows:

//Creates another list of rectangles that share nodes with the original list
ArrayList returnObj = new ArrayList();
for(int j = 0; j < list.size(); j++)
{
returnObj.clear();

//Loop that will check all colitions and return true if one occurs false otherwise
for(int k = 0; k < returnObj.size(); k++)
{
if(list.get(k).intersects(returnObj.get(k)))
{return true;}
}
}
return false;

This will loop over each object in the `list` array and check collision against them. It does this by first getting a list of objects from the quadtree that share a node with the `list.get(i)` element, then loops over each of those objects checking for collision.

Your quadtree looks good, very interesting use of a 2D array for your nodes. One thing I noticed though was in your `insert` function. On lines 95-104 (the switch statement), you should `return` after each case 1-4, but don’t return on the default case (of -1). If you don’t return on cases 1-4, the rectangle you are inserting will be inserted into the parent node as well as the subnode. This will cause some issues later on.

Another issue (which is mainly my fault), is again in the `insert` function on lines 122-134 (the other switch statement). The code in the article doesn’t work for Java (I should really get that updated…), it should be:

nodes[index].insert(objects.get(i));
objects.removeAt(i);

so you’re code should read as follows:

switch(index)//and add it to its corresponding position
{
case 1:
nodes[0][0].insert(element.get(i));elements.removeAt(i);break;
case 2:
nodes[0][1].insert(element.get(i));elements.removeAt(i);break;
case 3:
nodes[1][0].insert(element.get(i));elements.removeAt(i);break;
case 4:
nodes[1][1].insert(element.get(i));elements.removeAt(i);break;
default://if -1 in other words
i++; break;
}

Other than that, everything looks good. Let me know if you have any other questions.

• Yakobu

I corrected as suggested, didn’t see the inner and outer loop parts.
But then my function leads me to another question, what does it actually returns? if there is a collisions, but in general? how can I know what object has a collision and make it do a reaction according to my wish for the game?

• Yakobu

I have updated my hasCollision method, https://gist.github.com/Yakobu/fb45c31d18e98c530a55 but still need help please. When I try my method, it brings back nullpointerexeption right at the first line even though I check if the node is empty or not. If I ignore and put in comment, at the insert line too I have the same exception (at QuadTree.insert(QuadTree.java:102).

Also if I understand, it checks if there is a collision at all if yes, return true. But how could I know which of the objects (rectangles) has collided to code a reaction accordingly?

• http://sklambert.com/ Steven Lambert

Hey Yakobu, sorry it’s taken me a bit to get back to you.

I looked into your code and found the problem. The problem occurs in your `clear()` function in the `QuadTree` class. The first time you try to clear your QuadTree, the `nodes` array is empty. Thus, when you try to access the array, you access an empty array element and get the nullpointerexception. To fix this, you need to ensure in the `clear()` function that the current level has child levels that can be accessed before you loop through the `nodes` array.

As for how to know which objects have collided and react to them, take a look at this tutorial where I implemented this exact code:
http://blog.sklambert.com/html5-canvas-game-2d-collision-detection/

• Stew Reive

Steven, this is a really helpful tutorial! I have ported this quadtree to python/pygame for a small demo. I am now redoing it in C++ using OpenGL and GLUT APIs. Now, my goal is to squeeze out every ounce of performance. That said, I think there are two things about your implementation that could be changed to greatly improve the performance.

First and foremost, insert() should always store each object in the deepest possible node that it fits cleanly inside (level < MAX_LEVEL of course). This ensures that small objects will get buried deep into the quadtree and be tested for collision very infrequently. I cannot rigorously prove it, but I have a suspicion that this strategy minimizes the number of objects retrieve() will return for any given pRect. However, the trade-off is that this will require more memory than your current implementation as the tree splits more frequently.

Secondly, instead of rebuilding the tree every frame, you could have it update existing nodes starting from the leaves up to the root. I realize that you have already discussed this on here, but I just wanted to add to the discussion. By updating, you exploit temporal coherence (i.e. objects often stay in the same node in successive frames so update() will essentially do nothing for these). Of course, you also save the time used to free and rebuild the tree. However, this update() method is getting really, really tricky for me to implement, especially in C++ where memory management quickly turns into a nightmare. It's forcing me to modify insert() and getIndex() as well so I can have a case where an object doesn't fit at all into a node. I am very sure that it will ultimately increase my program's performance, but for now I am still just rebuilding the tree every frame :P Hopefully I'll finish this thing and post a link to my GitHub repository with the finished product!

Thanks again for the excellent tutorial! You rock!

• http://sklambert.com/ Steven Lambert

Hey Stew,

I’m also always interested in feedback to my implementation. I am curious to know what you mean when you say that an object should be stored in the deepest possible node that it fits cleanly inside. I am not sure how that is exactly different from the currently implementation of the `insert()` method.

I would love to see your current work for how you are trying to solve not recreating the tree each frame, and would be willing to help out to get it to work if possible. This would be a wonderful thing to have available to improve the performance.

• Stew Reive

Here’s more or less how I did the insert method: http://pastebin.com/EyyWUNr7
An example of it in action would look something like this (not my video): http://www.youtube.com/watch?v=5JGXjPnOcOw

Currently your implementation would put MAX_OBJECTS into the root node, and split only once you add the MAX_OBJECTS+1 item. In the video, you can see the tree split a bunch of times when the very first object was inserted (although I think this guy draws his tree one level too deep, but you get the point). You can see when this guy has 4 or 5 balls inserted, retrieve() probably won’t even return anything for each of the balls despite them being so close to each other! This is because they are stored as deeply as possible. Also, this implementation is shorter, doesn’t require the MAX_OBJECTS constant, and IMO looks cleaner and easier to understand. Plus it saves you from having to periodically insert/remove elements when you exceed capacity.

As far as not recreating the tree: I honestly don’t know if I can do it. Like you said earlier, it’s pretty freaking complicated. Here’s roughly what I’m doing. Keep in mind that I have a parent pointer and am using pseudo-java: http://pastebin.com/5Pc7qZaq

First, I go down recursively to the leaves. There I take each object and calculate its index. If it is out of bounds, I tell the parent to insert it and remove it from this node. My getIndex() returns -2 for out of bounds. Also, my insert has a -2 case in case it has to go all the way up! If index == -1, do nothing, we’re done. If index >= 0 you have to insert it deeper if possible and then delete it if inserted deeper. The hard part is that you have to get rid of empty nodes, otherwise you’ll just have a huge grid of empty nodes everywhere after a few frames! In theory it doesn’t sound too bad; it’s just the C++ implementation that’s killing me.

• Mannician

I definitely feel as though I have a better understanding because of your well thought out tutorial, but when I try to copy these concepts into my own java program, I run into one issue, and that is an IndexOutOfBoundsException, and it happens when I go to test my collisions. I think it has something to do with the way the inserting code works, but I cannot quite nail it down.

this is the chunk of code where the exception is being thrown from:

ArrayList possibleCollisions = new ArrayList();
for(int i=0; i<orbs.size(); i++)
{
possibleCollisions.clear();

for(int j=0; j<possibleCollisions.size(); j++)
{
Rectangle r = possibleCollisions.get(i).getBounds(); //This is where the exception is thrown.
}
}

Although I cannot quite figure out why it's doing this, I have determined the number of orbs that I can get on screen is directly influenced by the MAX_OBJECTS variable. As soon as the number of orbs I get on the screen passes that thresh hold, the program throws the exception, ultimately leading me to believe that It has something to do with the way the quad tree splits, but I have even been reduced to copying your code letter for letter, still to no avail. I am completely stuck.

• http://gamedev.tutsplus.com/ Michael James Williams

Formatted code:

` ArrayList possibleCollisions = new ArrayList(); for(int i=0; i<orbs.size(); i++) { possibleCollisions.clear(); quad.retrieve(possibleCollisions, orbs.get(i));`

` for(int j=0; j<possibleCollisions.size(); j++) { Rectangle r = possibleCollisions.get(i).getBounds(); //This is where the exception is thrown. } } `

Is it possibly just a typo? Try:

`Rectangle r = possibleCollisions.get(j).getBounds(); //get(j) instead of get(i)`

• http://sklambert.com/ Steven Lambert

Michael,

Thanks for formatting the code, that helped a lot.

Mannician,

By the looks of the code, I think Michael is correct. It should be `.get(j)` instead of `.get(i)` as `possibleCollisions.size` is less than `orbs.size()`.