tag:gamedevelopment.tutsplus.com,2005:/categories/data-structures Envato Tuts+ Game Development - Data Structures 2012-09-03T15:00:13Z tag:gamedevelopment.tutsplus.com,2005:PostPresenter/gamedev-374 Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space <div class="content-block-wysi" content-block-type="Wysi"> <p>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.</p> <p></p> <p><strong><em>Note:</em></strong> <em>Although this tutorial is written using Java, you should be able to use the same techniques and concepts in almost any game development environment.</em></p> <hr> <h2>Introduction</h2> <p><a href="https://en.wikipedia.org/wiki/Collision_detection">Collision detection</a> 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:</p> <p><figure class="embedded-video" data-video-embed="true" data-original-url="https://www.youtube.com/watch?v=_viW2ZUMlvo#t=00m49s"> <iframe data-src="//www.youtube.com/embed/_viW2ZUMlvo#t=00m49s?rel=0" frameborder="0" allowfullscreen="allowfullscreen" webkitallowfullscreen="webkitallowfullscreen" mozallowfullscreen="mozallowfullscreen" loading="lazy"></iframe> <div class="video-preview-image youtube" style="cursor:pointer;position: absolute;width: 100%;height: 100%;background-size:cover;"> <img loading="lazy" src="https://i.ytimg.com/vi/_viW2ZUMlvo#t=00m49s/hqdefault.jpg" style="width: 100%;padding: 0px;height: 100%;"> <svg height="100%" version="1.1" viewbox="0 0 68 48" width="68px" xmlns="http://www.w3.org/2000/svg" style="position: absolute;top: 0;left: calc(50% - 34px);"> <path class="play-button-bg" d="M66.52,7.74c-0.78-2.93-2.49-5.41-5.42-6.19C55.79,.13,34,0,34,0S12.21,.13,6.9,1.55 C3.97,2.33,2.27,4.81,1.48,7.74C0.06,13.05,0,24,0,24s0.06,10.95,1.48,16.26c0.78,2.93,2.49,5.41,5.42,6.19 C12.21,47.87,34,48,34,48s21.79-0.13,27.1-1.55c2.93-0.78,4.64-3.26,5.42-6.19C67.94,34.95,68,24,68,24S67.94,13.05,66.52,7.74z" fill="#212121"></path> <path d="M 45,24 27,14 27,34" fill="#fff"></path> </svg> </div> </figure></p> <p>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!</p> <p>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.</p> <hr> <h2>What Is a Quadtree?</h2> <p>A <a href="http://en.wikipedia.org/wiki/Quadtree">quadtree</a> is a data structure used to divide a 2D region into more manageable parts. It's an extended <a href="http://en.wikipedia.org/wiki/Binary_tree">binary tree</a>, but instead of two child nodes it has four.</p> <p>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:</p> <div><img width="150" alt="" src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image1.png" height="150" loading="lazy"></div> <p>A quadtree starts as a single node. Objects added to the quadtree are added to the single node.</p> <div><img width="246" alt="" src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image2.png" height="246" loading="lazy"></div> <p>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.</p> <div><img width="246" alt="" src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image3.png" height="246" loading="lazy"></div> <p>Each subnode can continue subdividing as more objects are added.</p> <div><img width="246" alt="" src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image4.png" height="246" loading="lazy"></div> <p>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.</p> <p><a href="http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/">Take a look at this JavaScript example</a> to see a quadtree in action.</p> <hr> <h2>Implementing a Quadtree</h2> <p>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.</p> <p>We’ll start off by creating the main Quadtree class. Below is the code for <code>Quadtree.java.</code></p> <pre class="brush: java noskimlinks noskimwords">public class Quadtree { private int MAX_OBJECTS = 10; private int MAX_LEVELS = 5; private int level; private List objects; private Rectangle bounds; private Quadtree[] nodes; /* * Constructor */ public Quadtree(int pLevel, Rectangle pBounds) { level = pLevel; objects = new ArrayList(); bounds = pBounds; nodes = new Quadtree; } }</pre> <p>The <code>Quadtree</code> class is straightforward. <code>MAX_OBJECTS</code> defines how many objects a node can hold before it splits and <code>MAX_LEVELS</code> defines the deepest level subnode. <code>Level</code> is the current node level (0 being the topmost node), <code>bounds</code> represents the 2D space that the node occupies, and <code>nodes</code> are the four subnodes.</p> <p>In this example, the objects the quadtree will hold are <code>Rectangles</code>, but for your own quadtree it can be whatever you want.</p> <p>Next, we’ll implement the five methods of a quadtree: <code>clear</code>, <code>split</code>, <code>getIndex</code>, <code>insert</code>, and <code>retrieve</code>.</p> <pre class="brush: java noskimlinks noskimwords">/* * Clears the quadtree */ public void clear() { objects.clear(); for (int i = 0; i &lt; nodes.length; i++) { if (nodes[i] != null) { nodes[i].clear(); nodes[i] = null; } } }</pre> <p>The <code>clear</code> method clears the quadtree by recursively clearing all objects from all nodes.</p> <pre class="brush: java noskimlinks noskimwords">/* * 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 = new Quadtree(level+1, new Rectangle(x + subWidth, y, subWidth, subHeight)); nodes = new Quadtree(level+1, new Rectangle(x, y, subWidth, subHeight)); nodes = new Quadtree(level+1, new Rectangle(x, y + subHeight, subWidth, subHeight)); nodes = new Quadtree(level+1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight)); }</pre> <p>The <code>split</code> method splits the node into four subnodes by dividing the node into four equal parts and initializing the four subnodes with the new bounds.</p> <pre class="brush: java noskimlinks noskimwords">/* * 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() &lt; horizontalMidpoint &amp;&amp; pRect.getY() + pRect.getHeight() &lt; horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() &gt; horizontalMidpoint); // Object can completely fit within the left quadrants if (pRect.getX() &lt; verticalMidpoint &amp;&amp; pRect.getX() + pRect.getWidth() &lt; verticalMidpoint) { if (topQuadrant) { index = 1; } else if (bottomQuadrant) { index = 2; } } // Object can completely fit within the right quadrants else if (pRect.getX() &gt; verticalMidpoint) { if (topQuadrant) { index = 0; } else if (bottomQuadrant) { index = 3; } } return index; }</pre> <p>The <code>getIndex</code> 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.</p> <pre class="brush: java noskimlinks noskimwords">/* * 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 != null) { int index = getIndex(pRect); if (index != -1) { nodes[index].insert(pRect); return; } } objects.add(pRect); if (objects.size() &gt; MAX_OBJECTS &amp;&amp; level &lt; MAX_LEVELS) { if (nodes == null) { split(); } int i = 0; while (i &lt; objects.size()) { int index = getIndex(objects.get(i)); if (index != -1) { nodes[index].insert(objects.remove(i)); } else { i++; } } } }</pre> <p>The <code>insert</code> 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.</p> <p>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.</p> <pre class="brush: java noskimlinks noskimwords">/* * Return all objects that could collide with the given object */ public List retrieve(List returnObjects, Rectangle pRect) { int index = getIndex(pRect); if (index != -1 &amp;&amp; nodes != null) { nodes[index].retrieve(returnObjects, pRect); } returnObjects.addAll(objects); return returnObjects; }</pre> <p>The final method of the quadtree is the <code>retrieve</code> 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.</p> <hr> <h2>Using This for 2D Collision Detection</h2> <p>Now that we have a fully functional quadtree, it’s time to use it to help reduce the checks needed for collision detection.</p> <p>In a typical game, you’ll start by creating the quadtree and passing the bounds of the screen.</p> <pre class="brush: java noskimlinks noskimwords">Quadtree quad = new Quadtree(0, new Rectangle(0,0,600,600));</pre> <p>At every frame, you’ll insert all objects into the quadtree by first clearing the quadtree then using the <code>insert</code> method for every object.</p> <pre class="brush: java noskimlinks noskimwords">quad.clear(); for (int i = 0; i &lt; allObjects.size(); i++) { quad.insert(allObjects.get(i)); }</pre> <p>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.</p> <pre class="brush: java noskimlinks noskimwords">List returnObjects = new ArrayList(); for (int i = 0; i &lt; allObjects.size(); i++) { returnObjects.clear(); quad.retrieve(returnObjects, objects.get(i)); for (int x = 0; x &lt; returnObjects.size(); x++) { // Run collision detection algorithm between objects } }</pre> <p><strong>Note:</strong> Collision detection algorithms are beyond the scope of this tutorial. <a href="https://gamedev.tutsplus.com/tutorials/implementation/collision-detection-with-the-separating-axis-theorem/">See this article</a> for an example.</p> <hr> <h2>Conclusion</h2> <p>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.</p> <div> <strong>Related Posts</strong><p></p> <ul> <li><a href="https://gamedev.tutsplus.com/tutorials/implementation/make-your-game-pop-with-particle-effects-and-quadtrees/">Make Your Game Pop With Particle Effects and Quadtrees</a></li> </ul> </div> </div> 2012-09-03T15:00:13.000Z 2012-09-03T15:00:13.000Z Steven Lambert