tag:gamedevelopment.tutsplus.com,2005:/categories/collision-detectionEnvato Tuts+ Game Development - Collision Detection2012-09-03T15:00:13Ztag:gamedevelopment.tutsplus.com,2005:PostPresenter/gamedev-374Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space<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><iframe data-src="https://www.youtube.com/embed/_viW2ZUMlvo#t=00m49s" width="600" height="450" frameborder="0"></iframe></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="" data-src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image1.png" height="150"></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="" data-src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image2.png" height="246"></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="" data-src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image3.png" height="246"></div>
<p>Each subnode can continue subdividing as more objects are added.</p>
<div><img width="246" alt="" data-src="https://cdn.tutsplus.com/gamedev/authors/legacy/Steven%20Lambert/2012/08/30/image4.png" height="246"></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[4];
}
}</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 < 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[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));
}</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() < 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) {
if (topQuadrant) {
index = 1;
}
else if (bottomQuadrant) {
index = 2;
}
}
// Object can completely fit within the right quadrants
else if (pRect.getX() > 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[0] != null) {
int index = getIndex(pRect);
if (index != -1) {
nodes[index].insert(pRect);
return;
}
}
objects.add(pRect);
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++;
}
}
}
}</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 && nodes[0] != 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 < 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 < allObjects.size(); i++) {
returnObjects.clear();
quad.retrieve(returnObjects, objects.get(i));
for (int x = 0; x < 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>2012-09-03T15:00:13.000Z2012-09-03T15:00:13.000ZSteven Lamberttag:gamedevelopment.tutsplus.com,2005:PostPresenter/gamedev-169Collision Detection Using the Separating Axis Theorem<p>The Separating Axis Theorem is often used to check for collisions between two simple polygons, or between a polygon and a circle. As with all algorithms, it has its strengths and its weaknesses. In this tutorial, we'll go over the math behind the theorem, and show how it can be used in game development with some sample code and demos.</p>
<p><em><strong>Note:</strong> Although the demos and sourcecode of this tutorial use Flash and AS3, you should be able to use the same techniques and concepts in almost any game development environment.</em></p>
<hr>
<h2>What the Theorem States</h2>
<p>The Separating Axis Theorem (SAT for short) essentially states if you are able to draw a line to separate two polygons, then they do not collide. It's that simple.</p>
<div><img alt="SAT collision detection" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/SAT.jpg"></div>
<p>In the diagram above, you can easily see collisions occurring in the second row. However you try to squeeze a line in between the shapes, you will fail. The first row is exactly the opposite. You can easily draw a line to separate the shapes -- and not just one line, but a lot of them:</p>
<div><img alt="Lines separating shapes" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/SAT2.jpg"></div>
<p>Okay, let's not overdo this; I think you get the point. The key argument here is that if you can draw such a line, then there must be a gap separating the shapes. So how do we check for this?</p>
<hr>
<h2>Projection Along an Arbitrary Axis</h2>
<div><img alt="basic idea of algorithm" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/basic_idea.jpg"></div>
<p>Let's assume for now that the polygons we refer to are squares: <code>box1</code> on the left and <code>box2</code> on the right. It's easy to see that these squares are horizontally separated. A straightforward approach to determine this in code is to calculate the horizontal distance between the two squares, then subtract the half-widths of <code>box1</code> and <code>box2</code>:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">//Pseudo code to evaluate the separation of box1 and box2
var length:Number = box2.x - box1.x;
var half_width_box1:Number = box1.width*0.5;
var half_width_box2:Number = box2.width*0.5;
var gap_between_boxes:Number = length - half_width_box1 - half_width_box2;
if(gap_between_boxes > 0) trace("It's a big gap between boxes")
else if(gap_between_boxes == 0) trace("Boxes are touching each other")
else if(gap_between_boxes < 0) trace("Boxes are penetrating each other")</pre>
<p>What if the boxes are not oriented nicely?</p>
<div><img alt="oriented boxes" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/algorithm.jpg"></div>
<p>Although the evaluation of the gap remains the same, we'll have to think of another approach to calculate the length between centers and the half-widths -- this time along the <code>P</code> axis. This is where vector math comes in handy. We'll project vectors A and B along P to get the half-widths.</p>
<p>Let's do some math revision.</p>
<hr>
<h2>Vector Math Revision</h2>
<p>We'll start by recapping the definition of the <a href="https://en.wikipedia.org/wiki/Dot_product">dot product</a> between two vectors <code>A</code> and <code>B</code>:</p>
<div><img alt="Dot product operation" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/dotProduct.jpg"></div>
<p>We can define the dot product using just the components of the two vectors:</p>
<p>\[<br>
\begin{bmatrix}A_x \\A_y\end{bmatrix}.<br>
\begin{bmatrix}B_x \\B_y\end{bmatrix}=<br>
(A_x)(B_x)+(A_y)(B_y)<br>
\]</p>
<p>Alternatively, we can understand the dot product using the magnitudes of the vectors and the angle between them:</p>
<p>\[<br>
\begin{bmatrix}A_x \\A_y\end{bmatrix}.<br>
\begin{bmatrix}B_x \\B_y\end{bmatrix}=<br>
A_{magnitude}*B_{magnitude}*cos(theta)<br>
\]</p>
<p> Now, let's try to to figure out the <em>projection</em> of vector <code>A</code> onto <code>P</code>.</p>
<div><img alt="description of image" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/projection.jpg"></div>
<p>Referring to the diagram above, we know that the projection value is \(A_{magnitude}*cos(theta)\) (where <code>theta</code> is the angle between A and P). Although we can go ahead and calculate this angle to obtain the projection, it's tricky. We need a more direct approach:</p>
<p>\[<br>
A. P=A_{magnitude}*P_{magnitude}*cos(theta)\\<br>
A.\frac{P}{P_{magnitude}}=A_{magnitude}*cos(theta)\\<br>
\begin{bmatrix}A_x \\A_y\end{bmatrix}.<br>
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=<br>
A_{magnitude}*cos(theta)<br>
\]</p>
<p>Note that \(\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}\) is actually the unit vector of P.</p>
<p>Now, instead of using the right side of the equation, as we were, we can opt for the left side and still arrive at the same result.</p>
<hr>
<h2>Application to a Scenario</h2>
<p>Before we proceed, i'd like to clarify the naming convention used to denote the four corners of both boxes. This will be reflected in the code later:</p>
<div><img alt="naming conventions of points" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/conventions.jpg"></div>
<p>Our scenario is as below:</p>
<div><img alt="projection of various lengths" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/projection2.jpg"></div>
<p> Let's say both boxes are oriented 45° from the horizontal axis. We must calculate the following lengths in order to determine the gap between the boxes.</p>
<ul>
<li>Projection of A on axis P</li>
<li>Projection of B on axis P</li>
<li>Projection of C on axis P</li>
</ul>
<p>Take special note of the arrows' directions. While projection of A and C onto P will give a positive value, projection of B onto P will actually produce a <em>negative</em> value as the vectors are pointing in opposite directions. This is covered in line 98 of the AS3 implementation below:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">var dot10:Point = box1.getDot(0);
var dot11:Point = box1.getDot(1);
var dot20:Point = box2.getDot(0);
var dot24:Point = box2.getDot(4);
//Actual calculations
var axis:Vector2d = new Vector2d(1, -1).unitVector;
var C:Vector2d = new Vector2d(
dot20.x - dot10.x,
dot20.y - dot10.y
)
var A:Vector2d = new Vector2d(
dot11.x - dot10.x,
dot11.y - dot10.y
)
var B:Vector2d = new Vector2d(
dot24.x - dot20.x,
dot24.y - dot20.y
)
var projC:Number = C.dotProduct(axis)
var projA:Number = A.dotProduct(axis);
var projB:Number = B.dotProduct(axis);
var gap:Number = projC - projA + projB; //projB is expected to be a negative value
if (gap > 0) t.text = "There's a gap between both boxes"
else if (gap > 0) t.text = "Boxes are touching each other"
else t.text = "Penetration had happened."</pre>
<p>Here's a demo using the above code. Click and drag the red middle dot of both boxes and see the interactive feedback.</p>
<div>
</div>
<p>For the full source, check out <code>DemoSAT1.as</code> in the <a href="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/SeparatingAxisTheorem.zip">source download</a>.</p>
<hr>
<h2>The Flaws</h2>
<p>Well, we can go with the above implementation. But there are a few problems -- let me point them out:</p>
<p>First, vectors A and B are fixed. So when you swap the positions of <code>box1</code> and <code>box2</code>, the collision detection fails.</p>
<div><img alt="wrong vector selected" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/direction.jpg"></div>
<p>Second, we only evaluate the gap along one axis, so situations like the one below will not be evaluated correctly:</p>
<div><img alt="only one axis evaluated" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/axis.jpg"></div>
<p>Although the previous demo is flawed, we did learn from it the concept of projection. Next, let's improve on it.</p>
<hr>
<h2>Solving the First Flaw</h2>
<p>So first of all, we'll need to get the minimum and maximum projections of corners (specifically the vectors from the origin to the boxes' corners) onto P.</p>
<div><img alt="projection of minimum and maximum of two boxes" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/min_max1.jpg"></div>
<p>The diagram above shows the projection of the minimum and maximum corners onto P when the boxes are oriented nicely along P.</p>
<p>But what if <code>box1</code> and <code>box2</code> are not oriented accordingly?</p>
<div><img alt="projection if boxes are not oriented accordingly" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/min_max2.jpg"></div>
<p>The diagram above shows boxes which are not neatly oriented along P, and their corresponding min-max projections. In this situation, we'll have to loop through each corner of each box and select the correct ones as appropriate.</p>
<p>Now that we have the min-max projections, we'll evaluate whether the boxes are colliding with each other. How?</p>
<div><img alt="Checking for collision" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/collision_check.jpg"></div>
<p>By observing the diagram above, we can clearly see the geometrical representation for projection of <code>box1.max</code> and <code>box2.min</code> onto axis P.</p>
<p>As you can see, when the's a gap between the two boxes, <code>box2.min-box1.max</code> will be more than zero -- or in other words, <code>box2.min > box1.max</code>. When the position of the boxes are swapped, then <code>box1.min > box2.max</code> implies there's a gap between them.</p>
<p>Translating this conclusion into code, we get:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">//SAT: Pseudocode to evaluate the separation of box1 and box2
if(box2.min>box1.max || box1.min>box2.max){
trace("collision along axis P happened")
}
else{
trace("no collision along axis P")
}</pre>
<hr>
<h2>Initial Code</h2>
<p>Let's look at some more detailed code for figuring this out. Note that the AS3 code here is not optimised. Although it's long and descriptive, the advantage is that you can see how the math behind it works.</p>
<p>First of all, we need to prepare the vectors:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">//preparing the vectors from origin to points
//since origin is (0,0), we can conveniently take the coordinates
//to form vectors
var axis:Vector2d = new Vector2d(1, -1).unitVector;
var vecs_box1:Vector.<Vector2d> = new Vector.<Vector2d>;
var vecs_box2:Vector.<Vector2d> = new Vector.<Vector2d>;
for (var i:int = 0; i < 5; i++) {
var corner_box1:Point = box1.getDot(i)
var corner_box2:Point = box2.getDot(i)
vecs_box1.push(new Vector2d(corner_box1.x, corner_box1.y));
vecs_box2.push(new Vector2d(corner_box2.x, corner_box2.y));
}</pre>
<p>Next, we obtain the min-max projection on <code>box1</code>. You can see a similar approach used on <code>box2</code>:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">//setting min max for box1
var min_proj_box1:Number = vecs_box1[1].dotProduct(axis);
var min_dot_box1:int = 1;
var max_proj_box1:Number = vecs_box1[1].dotProduct(axis);
var max_dot_box1:int = 1;
for (var j:int = 2; j < vecs_box1.length; j++)
{
var curr_proj1:Number = vecs_box1[j].dotProduct(axis)
//select the maximum projection on axis to corresponding box corners
if (min_proj_box1 > curr_proj1) {
min_proj_box1 = curr_proj1
min_dot_box1 = j
}
//select the minimum projection on axis to corresponding box corners
if (curr_proj1> max_proj_box1) {
max_proj_box1 = curr_proj1
max_dot_box1 = j
}
}</pre>
<p>Finally, we evaluate whether there's a collision on that specific axis, P:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">var isSeparated:Boolean = max_proj_box2 < min_proj_box1 || max_proj_box1 < min_proj_box2
if (isSeparated) t.text = "There's a gap between both boxes"
else t.text = "No gap calculated."</pre>
<p>Here's a demo of the implementation above: </p>
<div>
</div>
<p>You may drag either box around via its middle point, and rotate it with the R and T keys. The red dot indicates the maximum corner for a box, while yellow indicates the minimum. If a box is aligned with P, you may find that these dots flicker as you drag, as those two corners share the same characteristics.</p>
<p>Check out the full source in <code>DemoSAT2.as</code> in the <a href="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/SeparatingAxisTheorem.zip">source download</a>.</p>
<hr>
<h2>Optimisation</h2>
<p>If you'd like to speed up the process, there's no need to calculate for the unit vector of P. You can therefore skip quite a number of expensive Pythagoras's theorem calculations which involve <code>Math.sqrt()</code>:</p>
<p>\[ \begin{bmatrix}A_x \\A_y\end{bmatrix}.<br>
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=<br>
A_{magnitude}*cos(theta)<br>
\]</p>
<div><img alt="optimisation" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/optimise.jpg"></div>
<p>The reasoning is as follows (refer to diagram above for some visual guidance on variables):</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">/*
Let:
P_unit be the unit vector for P,
P_mag be P's magnitude,
v1_mag be v1's magnitude,
v2_mag be v2's magnitude,
theta_1 be the angle between v1 and P,
theta_2 be the angle between v2 and P,
Then:
box1.max < box2.min
=> v1.dotProduct(P_unit) < v2.dotProduct(P_unit)
=> v1_mag*cos(theta_1) < v2_mag*cos(theta_2)
*/</pre>
<p>Now, mathematically, the sign of inequality remains the same if both sides of the inequality are multiplied by the same number, A:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">/*
So:
A*v1_mag*cos(theta_1) < A*v2_mag*cos(theta_2)
If A is P_mag, then:
P_mag*v1_mag*cos(theta_1) < P_mag*v2_mag*cos(theta_2)
...which is equivalent to saying:
v1.dotProduct(P) < v2.dotProduct(P)
*/</pre>
<p>So whether it's a unit vector or not doesn't actually matter -- the result is the same.</p>
<p>Do bear in mind that this approach is useful if you are checking for overlap only. To find the exact penetration length of <code>box1</code> and <code>box2</code> (which for most games you'll probably need to), you still need to calculate the unit vector of P.</p>
<hr>
<h2>Solving the Second Flaw</h2>
<p>So we solved the issue for one axis, but that's not the end of it. We still need to tackle other axes -- but which? </p>
<div><img alt="overlappings on axes" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/on_axes.jpg"></div>
<p>The analysis for boxes is quite straightforward: we compare two axes P and Q. In order to confirm a collision, overlapping on <em>all</em> axes has to be true -- if there's any axis without an overlap, we can conclude that there's no collision.</p>
<p>What if the boxes are oriented differently?</p>
<div>
</div>
<p>Click the green button to turn to another page. So of the P, Q, R, and S axes, there's only one axis that shows no overlapping between boxes, and our conclusion is that there's no collision between the boxes.</p>
<p>But the question is, how do we decide which axes to check for overlapping? Well, we take the <em>normals</em> of the polygons.</p>
<div><img alt="normals of boxes" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/normals.jpg"></div>
<p>In a generalised form, with two boxes, we'll have to check along eight axes: <code>n0</code>, <code>n1</code>, <code>n2</code> and <code>n3</code> for each of <code>box1</code> and <code>box2</code>. However, we can see that the following lie on the same axes:</p>
<ul>
<li>
<code>n0</code> and <code>n2</code> of <code>box1</code>
</li>
<li>
<code>n1</code> and <code>n3</code> of <code>box1</code>
</li>
<li>
<code>n0</code> and <code>n2</code> of <code>box2</code>
</li>
<li>
<code>n1</code> and <code>n3</code> of <code>box2</code>
</li>
</ul>
<p>So we don't need to go through all eight; just four will do. And if <code>box1</code> and <code>box2</code> share the same orientation, we can further reduce to only evaluate two axes.</p>
<p>What about for other polygons?</p>
<div><img alt="normals of triangles and pentagons" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/normals2.jpg"></div>
<p>Unfortunately, for the triangle and pentagon above there's no such shortcut, so we'll have to run checks along all normals.</p>
<hr>
<h2>Calculating Normals</h2>
<p>Each surface has two normals:</p>
<div><img alt="calculating normals" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/normals3.jpg"></div>
<p>The diagram above shows the left and right normal of P. Note the switched components of the vector and the sign for each.</p>
<div><img alt="left normals used" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/normals4.jpg"></div>
<p>For my implementation, I'm using a clockwise convention, so I use the <em>left</em> normals. Below is an extract of <code>SimpleSquare.as</code> demonstrating this.</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">public function getNorm():Vector.<Vector2d> {
var normals:Vector.<Vector2d> = new Vector.<Vector2d>
for (var i:int = 1; i < dots.length-1; i++)
{
var currentNormal:Vector2d = new Vector2d(
dots[i + 1].x - dots[i].x,
dots[i + 1].y - dots[i].y
).normL //left normals
normals.push(currentNormal);
}
normals.push(
new Vector2d(
dots[1].x - dots[dots.length-1].x,
dots[1].y - dots[dots.length-1].y
).normL
)
return normals;
}</pre>
<hr>
<h2>New Implementation</h2>
<p>I'm sure you can find a way to optimise the following code. But just so that we all get a clear idea of what's happening, I've written everything out in full:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">//results of P, Q
var result_P1:Object = getMinMax(vecs_box1, normals_box1[1]);
var result_P2:Object = getMinMax(vecs_box2, normals_box1[1]);
var result_Q1:Object = getMinMax(vecs_box1, normals_box1[0]);
var result_Q2:Object = getMinMax(vecs_box2, normals_box1[0]);
//results of R, S
var result_R1:Object = getMinMax(vecs_box1, normals_box2[1]);
var result_R2:Object = getMinMax(vecs_box2, normals_box2[1]);
var result_S1:Object = getMinMax(vecs_box1, normals_box2[0]);
var result_S2:Object = getMinMax(vecs_box2, normals_box2[0]);
var separate_P:Boolean = result_P1.max_proj < result_P2.min_proj ||
result_P2.max_proj < result_P1.min_proj
var separate_Q:Boolean = result_Q1.max_proj < result_Q2.min_proj ||
result_Q2.max_proj < result_Q1.min_proj
var separate_R:Boolean = result_R1.max_proj < result_R2.min_proj ||
result_R2.max_proj < result_R1.min_proj
var separate_S:Boolean = result_S1.max_proj < result_S2.min_proj ||
result_S2.max_proj < result_S1.min_proj
//var isSeparated:Boolean = separate_p || separate_Q || separate_R || separate_S
if (isSeparated) t.text = "Separated boxes"
else t.text = "Collided boxes."</pre>
<p>You'll see that some of the variables aren't necessarily calculated to reach the result. If any one of <code>separate_P, separate_Q, separate_R</code> and <code>separate_S</code> is true, then they are separated and there's no need to even proceed.</p>
<p>This means we can save a fair amount of evaluation, just by checking each of those Booleans after they've been calculated. It would require rewriting the code, but I think you can work your way through it (or check out the commented block in <code>DemoSAT3.as</code>).</p>
<p>Here's a demo of the above implementation. Click and drag the boxes via their middle dots, and use the R and T keys to rotate the boxes:</p>
<div>
</div>
<hr>
<h2>Afterthoughts</h2>
<p>When this algorithm is run, it checks through the normal axes for overlappings. I have two observations here to point out:</p>
<ul>
<li>SAT is optimistic that there'll be no collision between polygons. The algorithm can exit and happily conclude "no collision" once <em>any axis</em> shows no overlapping. If there were any collision, SAT will have to run through <em>all</em> the axes to reach that conclusion -- thus, the more collisions there actually are, the worse the algorithm performs.</li>
<li>SAT uses the normal of each of the polygons' edges. So the more complex the polygons are, the more expensive SAT will become.</li>
</ul>
<hr>
<h2>Hexagon-Triangle Collision Detection</h2>
<p>Here's another sample code snippet to check for a collision between a hexagon and a triangle:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">private function refresh():void {
//prepare the normals
var normals_hex:Vector.<Vector2d> = hex.getNorm();
var normals_tri:Vector.<Vector2d> = tri.getNorm();
var vecs_hex:Vector.<Vector2d> = prepareVector(hex);
var vecs_tri:Vector.<Vector2d> = prepareVector(tri);
var isSeparated:Boolean = false;
//use hexagon's normals to evaluate
for (var i:int = 0; i < normals_hex.length; i++)
{
var result_box1:Object = getMinMax(vecs_hex, normals_hex[i]);
var result_box2:Object = getMinMax(vecs_tri, normals_hex[i]);
isSeparated = result_box1.max_proj < result_box2.min_proj || result_box2.max_proj < result_box1.min_proj
if (isSeparated) break;
}
//use triangle's normals to evaluate
if (!isSeparated) {
for (var j:int = 1; j < normals_tri.length; j++)
{
var result_P1:Object = getMinMax(vecs_hex, normals_tri[j]);
var result_P2:Object = getMinMax(vecs_tri, normals_tri[j]);
isSeparated = result_P1.max_proj < result_P2.min_proj || result_P2.max_proj < result_P1.min_proj
if (isSeparated) break;
}
}
if (isSeparated) t.text = "Separated boxes"
else t.text = "Collided boxes."
}</pre>
<p>For the full code, check out <code>DemoSAT4.as</code> in the <a href="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/SeparatingAxisTheorem.zip">source download</a>.</p>
<p>The demo is below. Interaction is the same as in previous demos: drag via the middle points, and use R and T to rotate.</p>
<div>
</div>
<hr>
<h2>Box-Circle Collision Detection</h2>
<div><img alt="collision with circle" data-src="https://cdn.tutsplus.com/gamedev/uploads/legacy/008_separatingAxisTheorem/assets/circle.jpg"></div>
<p>Collision with a circle may be one of the simpler ones. Because its projection is the same in all directions (it's simply the circle's radius), we can just do the following:</p>
<pre class="brush: actionscript3 noskimlinks noskimwords">private function refresh():void {
//prepare the vectors
var v:Vector2d;
var current_box_corner:Point;
var center_box:Point = box1.getDot(0);
var max:Number = Number.NEGATIVE_INFINITY;
var box2circle:Vector2d = new Vector2d(c.x - center_box.x, c.y - center_box.y)
var box2circle_normalised:Vector2d = box2circle.unitVector
//get the maximum
for (var i:int = 1; i < 5; i++)
{
current_box_corner = box1.getDot(i)
v = new Vector2d(
current_box_corner.x - center_box.x ,
current_box_corner.y - center_box.y);
var current_proj:Number = v.dotProduct(box2circle_normalised)
if (max < current_proj) max = current_proj;
}
if (box2circle.magnitude - max - c.radius > 0 && box2circle.magnitude > 0) t.text = "No Collision"
else t.text = "Collision"
}</pre>
<p>Check out the full source in <code>DemoSAT5.as</code>. Drag either the circle or box to see them collide.</p>
<div>
</div>
<hr>
<h2>Conclusion</h2>
<p>Well, that's it for now. Thanks for reading and do leave your feedback with a comment or question. See you next tutorial!</p>2012-08-06T17:30:32.000Z2012-08-06T17:30:32.000ZKah Shiu Chong