Implementing a Quadtree Collision System

Quadtree Collision System

You’re working hard on a new game. You have many ideas and many items on screen at once that all need to be tested for collisions with each other. Unfortunately, your computer isn’t powerful enough to check for a collision between every object on screen without a severe drop in frame rate. At this point you could just decide to limit your game to less items, but that is the cheap way out and your game will never get anywhere like that! Instead you should use a quadtree collision system! In this article I will discuss what a quadtree is, and how to implement it in Python to improve the efficiency of a particle simulator. Although this tutorial uses Python for a particle simulator, the code is easy to understand and is useful in many other programming languages and applications!

Using the quadtree system I improved my Particle-Simulator on Github to handle about 2000 particles.

Before we get started, it is important to see how beneficial the quadtree collision system is! While I was working through Peter’s excellent Pygame Physics Tutorial I tried to maximize the amount of balls on screen at once. However, my computer was only able to handle about 200 balls on screen and I became determined to increase this number for a more fun physics engine like that used in Angry Birds. To see the issue for yourself, first download this particle simulator that uses the brute force, every particle checks every particle for collisions, system and run it with about 10 - 50 particles. It should work pretty well with no frame rate issues (if not you might want to do this tutorial on a different computer)! Now try increasing the number of particles to about 500… The frame rate drop is staggering and the problem with the brute force collision check system becomes apparent. Now download this particle simulator with quadtree collisions and run it to see the improvement. This tutorial will bridge the gap from the brute force particle simulator to the quadtree particle simulator! For a tutorial on the physics of this particle simulator check out Peter’s Pygame Physics Tutorial.

Download 'ParticleGame.py' and 'ParticleGameQuadtree.py' from Github.

The Quadtree Data Structure.

A quadtree is a type of data structure that initially starts out as a single entity and subdivides into four entities until a certain condition is met. The tree analogy for the quadtree is how I best understand it. Essentially the quadtree starts out as a single box (the trunk) and then checks if the box contains more than a maximum number of particles. If the box does contain more than this number of particles, it splits into four smaller boxes (branches) that each do the same thing as the larger box but for a smaller area. Each of these boxes subdivides if the particle count exceeds the maximum number of particles per box and this cycle continues until either boxes do not contain more than the maximum number of particles or the limit of subdivisions is reached. If the limit of subdivisions is 5 then a maximum of five levels of subdivisions can occur originating from the big box.

The following example demonstrates a quadtree data structure:

Limit of subdivisions: 2

Maximum number of particles per box: 4

This is a frame of 24 particles on a small surface. The quadtree begins as one box that encompasses the entire display surface. Because the number of particles in the box is greater than four and the level of subdivision has not been reached, the box subdivides.

The quadtree subdivides into four branches which each perform the same as the original "trunk." The top left, top right, and bottom left boxes all have more than four particles so they each subdivide. The bottom right box does not have more than four particles so it now checks for collisions between all four particles in the box. Notice that, for any particle that is on a line of subdivision, the particle is included in tests for every box it is partially in.

The three boxes have now each subdivided into four smaller boxes, and now the limit of subdivision of 2 has been reached. Each smaller box now tests for collisions between every particle wholly or partially contained in the box. Observe that some of the boxes still contain more than the maximum number of particles, but they do not subdivide any further because the maximum limit of subdivision has been reached.

More information about the data structure can be found on the Wikipedia page.

This basic data structure has a wide range of applications beyond collision testing including spatial indexing and storing polygons. The efficiency of this data structure makes it very appealing to high performance software that seeks to save computing power and memory.

Python, Pygame, and a Quadtree Collision System.

We will begin with the the brute force particle simulator and bridge our way to the quadtree collisions system. Open ‘ParticleGame.py’ and follow along.

The first thing we need to do is create the quadtree class. Copy the code bellow to create the Quadtree class definition and __init__ method:

(9 lines) codebit 1

class Quadtree(object):
    def __init__(self, level, rect, particles=[], color = (0,0,0)):
        self.maxlevel = 4
        self.level = level
        self.maxparticles = 3
        self.rect = rect
        self.particles = particles
        self.color = color
        self.branches = []

This initialize method has four parameters. The first parameter, level, is required and represents the level of subdivision the quadtree was created on. For the “trunk” or orginal box of the quadtree the level is zero. When the quadtree recursively subdivides, each branch’s level is the quadtree’s level plus one.

The second parameter, rect, is a Pygame Rect object that represents the area that the box contains. Particles wholly or partially contained in this Rect are added to the self.particles list for continued subdivision or collision testing.

The third parameter, particles, is a list of all the particles in the quadtree. This parameter is only used for the quadtree initialized in the game loop that includes all of the particles. We will define an add_particle method later that is used for recursively adding particles to branches of the quadtree.

The final parameter is just the RGB color value for the quadtree if the boxes are displayed. Usually the quadtree is not displayed.

The class variables include maxlevel, maxparticles, and branches. self.maxlevel is the maximum number of subdivisions for the quadtree. self.maxparticles is the minimum number of particles required for a subdivision. If the branch contains equal to or less than maxparticles it does not subdivide and instead tests for collisions. self.branches is a list of the four branches created if the quadtree subdivides.

Next we will create the get_rect, subdivide, and add_particles methods:

(10 lines) codebit 2

def get_rect(self):
    return self.rect

def subdivide(self):
    for rect in rect_quad_split(self.rect):
        branch = Quadtree(self.level+1, rect, [], (self.color[0]+30,self.color[1],self.color[2]))
        self.branches.append(branch)

def add_particle(self, particle):
    self.particles.append(particle)

The get_rect method returns the Pygame Rect object of the quadtree.

The subdivide method takes the current quadtree level's Rect and subdivides it into four smaller rects. To do this we need to add a function called rect_quad_split that accompanies this method.

Add this function above the Quadtree class definition:

(9 lines) codebit 3

def rect_quad_split(rect):
    w=rect.width/2.0
    h=rect.height/2.0
    rl=[]
    rl.append(pygame.Rect(rect.left, rect.top, w, h))
    rl.append(pygame.Rect(rect.left+w, rect.top, w, h))
    rl.append(pygame.Rect(rect.left, rect.top+h, w, h))
    rl.append(pygame.Rect(rect.left+w, rect.top+h, w, h))
    return rl

This function simply takes a single Rect object and returns four equally sized smaller Rect objects subdivided from the original Rect object.

The four smaller rects are returned and the subdivide method then creates four new Quadtree instances that are the branches of the current quadtree level.

The add_particle method is used to add particles to the self.particles list which represents every particle contained in the box.

Now add the following subdivide_particles, render, and test_collisions methods:

(13 lines) codebit 4

def subdivide_particles(self):
    for particle in self.particles:
        for branch in self.branches:
            if branch.get_rect().colliderect(particle.get_rect()):
                branch.add_particle(particle)

def render(self, display):
    pygame.draw.rect(display, self.color, self.rect)

def test_collisions(self):
    for i, particle in enumerate(self.particles):
        for particle2 in self.particles[i+1:]:
            collide(particle, particle2)

The subdivide_particles method is used to distribute every particle in the current quadtree level to the appropriate branches based on the particle locations. Each particle is tested for collision with each of the four branches using the Rect.colliderect method. You may already realize that this requires each particle to have a rect as well. Don't worry, we will implement particle rects soon.

The render method is used if we want to display each box on the screen during the particle simulation. This method draws a rect that represents a branch of the quadtree. This method has one parameter, display, that is the Pygame display Surface object that the box will be displayed on.

You may expect the collision testing method to be something more complicated or extravagant in order to have a high efficiency improvement, but in fact it is exactly the same as the brute force collision test. We iterate through every particle in the self.particles list and test for collisions with every other particle in that list. What makes the difference (and makes this entire tutorial worth reading) is that the lists are much smaller since the particles are divided up into many quadtree branch lists that only contain nearby particles.

Lastly, we need to add the update method that is called to begin the recursive quadtree process.

Add this update method:

(10 lines) codebit 5

def update(self, display):
    if len(self.particles) > self.maxparticles and self.level <= self.maxlevel:
        self.subdivide()
        self.subdivide_particles()
        for branch in self.branches:
            branch.update(display)
    else:
        self.test_collisions()
        if displayTree:
            self.render(display)

The update method has one parameter which is the Pygame display Surface passed to the render method. The update method first checks to see if the number of particles in the box exceeds the maximum and if the maximum level of subdivision has not been reached. If both are true, the box subdivides and then distributes the particles among the four subdivisions. Then each branches’ update method is called and the recursive process continues until one of the tests in the if statement is false. If false, the test_collisions method is called and the quadtree is displayed if displayTree is set to true.

Add the displayTree variable underneath the number_of_particles variable at the top of the script so it is easily accessible.

(1 line) codebit 6

displayTree = False

Set displayTree to true for a visual representation of the quadtree system!

That is all there is to the quadtree class! This is a very simple quadtree setup that has a lot of room to be built upon (In a later article).

Particle Rect and Final Touches

Like I mentioned earlier, we need to add a Rect to each particle. This rect is not used to test collisions between other particles, but instead to test for collisions with the quadtree branches. This is efficient because the particles can still collide like balls but only have to test for collisions within the Rect (or Rects) they are colliding with.

Add the following two methods to the Particle class:

(5 lines) codebit 7

def get_rect(self):
    return self.rect

def set_rect(self):
    self.rect = pygame.Rect(self.x-self.radius, self.y-self.radius, self.radius*2, self.radius*2)

The get_rect method returns the Pygame Rect object of the Particle.

The set_rect method creates the particles Rect with a side length of two times the radius around the circle with that radius. This needs to be called every frame of the game because when the particle moves, its rect changes.

Call this function in the __init__ method of the particle so the particle has a rect as soon as it's created. Add this:

(1 line) codebit 8

self.set_rect()

The final step is to fix the game loop to initialize the base “trunk” of the particle tree, call the update method to start the recursive quadtree collision testing, and use the particle rect system.

Right below DISPLAYSURF.fill(BGCOLOR) add the following:

(2 lines) codebit 9

tree = Quadtree(0, pygame.Rect(0,0,DISPLAYWIDTH,DISPLAYHEIGHT), my_particles)
tree.update(DISPLAYSURF)

These two lines accomplish initialization and recursion. Now we just need to replace the old collision for loop with a new particle rect setting loop!

Replace the entire for i, particle in enumerate(my_particles) loop with the following:

(5 lines) codebit 10

for particle in my_particles:
    particle.display()
    particle.move()
    particle.bounce()
    particle.set_rect()

Increase the number of particles to a point that caused frame rate drops using the brute force system and run the script to see the magic of the quadtree collision system! (try 1000 on the old collision system and then on the quadtree)

Dont forget to set DisplayTree to true to see how the quadtree system works!

I highly encourage playing around with the quadtree system to find maximum efficiency! Try adjusting the size of the display, max level of recursion, max particles in a branch, and number of particles to find what works best!

This system has more benefits and flaws that I hope to address in a future article.

Here are some books that dive deeper into advanced collision detection, efficient algorithms for gaming, and Python:
• 2D Game Collision Detection: An introduction to clashing geometry in games
• Game Collision Detection: A Practical Introduction
• Algorithms & Data Structures in Python
• Python: Learn Python in One Day and Learn It Well. Python for Beginners with Hands-on Project. (Learn Coding Fast with Hands-On Project Book 1)