2D collision detection in Pistol Slut
For the last six months, I’ve been writing Pistol Slut, a 2D shoot-em-up in JavaScript. In this article, I’ll talk about how I solved some of the nastier problems with detecting collisions between 2D objects, specifically: bullets, grenades, exploding barrels, buildings and people.
You might find it helpful to play Pistol Slut before you read on, so you have a context for the things I talk about.
I will not be talking about per-pixel collision detection. And I will only be talking about objects whose shapes can be roughly approximated to a rectangle.
Most of the examples in this article will be conducted in pseudo-code. If you want to see the code I actually used, go and look at the repository for Pistol Slut. Both it, and the framework it is based on, The Render Engine, are open source under the MIT license. This means you can take the code and use it in any project, commercial or non-commercial, open source or not.
This article will begin with the general approach to collision detection. It will then go into special cases that solve some of the trickier problems.
Grids
Imagine the whole game world split up by a grid. If two objects are in the same square of the grid, we assume they are colliding, like these two red squares.
Whereas, these two red squares are not colliding:
So, to detect whether a particular object is colliding with another one in our simple little world, we can use this code:
// Make a structure to hold all the grid squares | |
For each grid square | |
Make a grid square container | |
// Put all the objects in the right grid square container | |
For each object in the world | |
Get the x and y coordinates of the object's top left corner | |
Determine which grid square the coordinates fall into | |
Add the object to that grid square container | |
// Get all the objects that a certain object is colliding with | |
Get the grid square container the object is in | |
Return all the other objects in that grid square container |
What if the world looks like this?
Uh-oh.
An object might exist in more than one grid square. How about we get the coordinates of all four corners of each object and add the object to the grid square containers into which the coordinates of those corners fall? No, that’s not going to fly, either, because the world might look like this:
There are two solutions. Solution one, use bounding boxes, the subject of the next section. But we don’t really want to do that, because the grid is supposed to be a super-quick triage that dramatically cuts down the number of collisions we have to test further. Solution two, assume that an object will never be bigger than a grid square and, therefore, we can just add it to the grid square container into which its top left corner falls, and the containers of the eight surrounding squares. To make this happen, we can modify the second block in the previous code, giving us:
// Make a structure to hold all the grid squares | |
For each grid square | |
Make a grid square container | |
// Put all the objects in the right grid square container | |
For each object in the world | |
Get the x and y coordinates of the object's top left corner | |
Determine which grid square the coordinates fall into | |
Add the object to that grid square container | |
For each of the eight surrounding grid square containers | |
Add the object to the container | |
// Get all the objects that a certain object is colliding with | |
Get the grid square container the object is in | |
Return all the other objects in that grid square container |
One last thing: what happens if an object moves? It might have moved to a new grid square. It’s no big deal:
If an object moves | |
Remove the object from all grid square containers | |
Get the x and y coordinates of the object's top left corner | |
Determine which grid square the coordinates fall into | |
Add the object to that grid square container | |
For each of the eight surrounding grid square containers | |
Add the object to the container |
Bounding boxes
We can now get a list of all the objects that a particular object is colliding with. But that’s kind of lies, isn’t it? Though the two red squares in the first diagram are occupying the same grid square, they aren’t actually colliding. Grid square co-habitation is only the first step. The next is to find out whether an object is actually overlapping another object, like these two love-birds:
We do this with bounding boxes. A bounding box is a square that is as tight a fit as possible around the actual boundaries of an object. A bounding box is defined by the x and y coordinates of its top left corner and the x and y coordinates of its bottom right corner. If two objects’ bounding boxes overlap, those two objects are colliding. To calculate if two bounding boxes overlap, we run four tests that would confirm the boxes *don’t* overlap. If all four tests come back false, the boxes are overlapping:
// testing whether object a and b overlap | |
If a's bottom right x coordinate is less than b's top left x coordinate | |
There is no collision | |
If a's top left x is greater than b's bottom right x | |
There is no collision | |
If a's top left y is greater than b's bottom right y | |
There is no collision | |
If a's bottom right y is less than b's top left y | |
There is no collision |
To get all the objects that a particular object is colliding with:
For each other object B in the same grid square as object A | |
If object B's bounding box overlaps object A's | |
Add B to the list of colliding objects |
Putting it all together
For each tick of the clock | |
For every object in the game | |
Get all the other objects in the same grid square | |
For each other object in the same grid square | |
If object still wants to hear about square sharers in this tick | |
Tell the object there is a potential collision | |
If the object's bounding box overlaps the other's | |
Object reacts | |
Object indicates if it wants to hear about more square sharers |
The object’s reaction may depend on what type of object it has collided with. Its decision about whether it wants to hear about more objects in its grid square in this tick might depend on whether its reaction involved it being destroyed. If it is destroyed, it will probably remove itself permanently from the pool of objects in the grid.
Special cases
This is the tougher stuff. I’ll talk about how to deal with fast-moving objects, objects that can stand on top of others, objects that can push others and objects that bounce.
The root cause of most of the difficulties is the fact that objects can move several pixels per tick. Thus, you do not always hear about collisions until after one object is well inside another. Thus, it’s sometimes hard to tell at what coordinates the impact occurred. I’ll take some objects from Pistol Slut, explain the difficulties with each object, and the solutions.
Bullets
Problem one: in a tick, bullets can pass right through objects they should be colliding with. Solution: make sure they can’t ever move at a pixel speed higher than your narrowest object. You could do this by taking care to build objects that aren’t too narrow, or put a speed limit on bullets that is based on the width of your narrowest object.
Problem two: it’s hard to tell at what coordinates a bullet entered a dustbin, which makes it difficult to show the point of impact with a shower of sparks. Solution: extrapolate back through time. I have no idea what this technique is really called.
Here is a red dustbin with a red bullet being shot at it. It passes through positions A, B and C in that order.
Unfortunately, ticks only occur when the bullet is at positions A and C. Therefore, with the system outlined above, the bullet won’t know about a collision until it reaches position C. That will be fine for destroying the bullet to represent the fact that it has hit the dustbin, but it won’t be so great for doing the beautiful shower of sparks. If we drew those sparks at point C, the location of the bullet when we detected the collision, they would look like this:
Lame.
We need to find position B. That way, the sparks will originate from the point of impact. As a bonus, I will show you how to make the sparks go in the right direction.
For the first part, draw an imaginary green line between position C and position A. That is, a line between where the bullet is now and where the bullet was in the previous tick. Then, draw four more imaginary purple lines, one along each side of the bounding box of the dustbin.
The move is to find out which bounding box line the C to A line intersects, and where. Here are two JavaScript functions; the first tells you if a line between p1 and p2 and a line between p3 and p4 are intersecting and the second tells you where.
lineLineCollision: function(p1, p2, p3, p4) { | |
var d = ((p4.y - p3.y) * (p2.x - p1.x)) - ((p4.x - p3.x) * (p2.y - p1.y)); | |
var n1 = ((p4.x - p3.x) * (p1.y - p3.y)) - ((p4.y - p3.y) * (p1.x - p3.x)); | |
var n2 = ((p2.x - p1.x) * (p1.y - p3.y)) - ((p2.y - p1.y) * (p1.x - p3.x)); | |
if ( d == 0.0 ) | |
{ | |
if ( n1 == 0.0 && n2 == 0.0 ) | |
{ | |
return false; //COINCIDENT; | |
} | |
return false; // PARALLEL; | |
} | |
var ua = n1 / d; | |
var ub = n2 / d; | |
return (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0); | |
}, | |
lineLineCollisionPoint: function(p1, p2, p3, p4) { | |
var d = ((p4.y - p3.y) * (p2.x - p1.x)) - ((p4.x - p3.x) * (p2.y - p1.y)); | |
var n1 = ((p4.x - p3.x) * (p1.y - p3.y)) - ((p4.y - p3.y) * (p1.x - p3.x)); | |
var n2 = ((p2.x - p1.x) * (p1.y - p3.y)) - ((p2.y - p1.y) * (p1.x - p3.x)); | |
if ( d == 0.0 ) | |
{ | |
if ( n1 == 0.0 && n2 == 0.0 ) | |
{ | |
return false; //COINCIDENT; | |
} | |
return false; // PARALLEL; | |
} | |
var ua = n1 / d; | |
var ub = n2 / d; | |
x = p1.x + ua * (p2.x - p1.x); | |
y = p1.y + ua * (p2.y - p1.y); | |
return Point2D.create(x, y); | |
}, |
So, with the power of maths in our hands, we can now figure out where position B is:
If line C to A is intersecting with the line defining the left side of the object | |
Return "left" and the point of intersection between C to A and the left line | |
If line C to A is intersecting with the line defining the right side of the object | |
Return "right" the point of intersection between C to A and the right line | |
If line C to A is intersecting with the line defining the bottom side of the object | |
Return "bottom" and the point of intersection between C to A and the bottom line | |
If line C to A is intersecting with the line defining the top side of the object | |
Return "top" and the point of intersection between C to A and the top line |
And, thus, emit the shower of sparks from that point.
But in which rough direction should the sparks go? Ack. Start crying: here comes some more maths.
// take moving object and return angle of movement in opposite direction | |
reverseAngle: function(movingObj, sideHit) { | |
var vector = movingObj.getVelocity().normalize(); | |
var surfaceNormal = this.getSurfaceNormal(sideHit); | |
var d = vector.angleBetween(surfaceNormal); | |
return this.adjustForSide(d, sideHit); | |
}, | |
getSurfaceNormal: function(side) { | |
if(side == "left") | |
return Vector2D.create(-1, 0); | |
else if(side == "right") | |
return Vector2D.create(1, 0); | |
else if(side == "top") | |
return Vector2D.create(0, -1); | |
else if(side == "bottom") | |
return Vector2D.create(0, 1); | |
}, | |
adjustForSide: function(angleBetween, sideHit) { | |
if(sideHit == "left") | |
return angleBetween + 90; | |
else if(sideHit == "right") | |
return angleBetween - 90; | |
else if(sideHit == "top") | |
return angleBetween + 180; | |
else if(sideHit == "bottom") | |
return angleBetween; | |
}, |
reverseAngle()
is the key function, here. It gets the normal to the side of the dustbin that the bullet hit. That is, it gets the outward-facing line that is perpendicular. It gets the angle between the normal and the bullet’s vector and then spins that angle around to adjust it to the direction appropriate for the side that was hit. The result is the angle the sparks should go along.
Grenades
Problem one: grenades bounce. Solution: use the code from the Bullets section to get the point of impact of the grenade and then reflect the angle of impact and send the grenade off in this new direction. And maybe reduce the grenade’s velocity a little to account for friction and the fact that grenades aren’t exactly like super balls when it comes to bouncing. Easy.
Problem two: solution one was a bit of a lie. The reflect direction stuff we used for bullets will still work great with grenades, but the stuff with using the grenade’s current and previous positions to get its trajectory and, thus, where it hit the dustbin, can be problematic. It’ll work most of the time, but not all. I’ll explain why.
When we drew the imaginary line between the current and previous positions of the bullet, we drew it between the top right hand corners of the two positions. This is fine, because the bullet actually IS only a single point. It’s drawn as a single pixel. But grenades are bigger than that. So, something like this might happen:
The first time we hear about a collision with the red dustbin will be when the red grenade is at position C. However, though the lower right portion of the grenade is intersecting with the dustbin at position C, the line we draw between the top left corners of each position does not, and will never, intersect with the dustbin. There is no position B. Thus, we will not get a point of impact and, thus, we won’t know where to bounce the grenade from.
But, fear not. We can solve this problem. We could draw lines between each corner of the previous and next positions: top left to top left, top right to top right, and so forth. However, there is a more elegant, more general solution: sweeping.
This solution has two cases. In the first case, at a particular tick, the red grenade is intersecting the side of the red dustbin:
In this case, the code to get the angle to bounce the grenade is straightforward:
If this grenade is colliding with an object | |
If grenade bounding box overlapping line defining left side of object | |
Run reverseAngle() function, passing "left" for sideHit | |
If grenade bounding box overlapping line defining right side of object | |
Run reverseAngle() function, passing "right" for sideHit | |
If grenade bounding box overlapping line defining bottom side of object | |
Run reverseAngle() function, passing "bottom" for sideHit | |
If grenade bounding box overlapping line defining top side of object | |
Run reverseAngle() function, passing "top" for sideHit |
To determine whether a line intersects a box, make a rectangle of the line and then see if that rectangle overlaps the box rectangle. To make a rectangle from a horizontal or vertical line between p1 and p2:
x: p1.x | |
y: p1.y | |
width: p2.x - p1.x | |
height: p2.y - p1.y |
In the second case, the red grenade is already fully inside the dustbin:
To deal with this, we use a technique called sweeping. The idea is to move the grenade back along its trajectory in small increments, testing at each position to see if it is overlapping any of the sides of the dustbin. Like this:
The initial collision is detected when the grenade is at position A. We then sweep its position back incrementally to positions B, C and D, testing to see if it collides with any of the edges of the red dustbin. We finally get a hit at position E.
To handle both this case and the previous case, we can write this code:
If this grenade is colliding with an object | |
If grenade bounding box overlapping line defining left side of object | |
Run reverseAngle() function, passing "left" for sideHit | |
If grenade bounding box overlapping line defining right side of object | |
Run reverseAngle() function, passing "right" for sideHit | |
If grenade bounding box overlapping line defining bottom side of object | |
Run reverseAngle() function, passing "bottom" for sideHit | |
If grenade bounding box overlapping line defining top side of object | |
Run reverseAngle() function, passing "top" for sideHit | |
No overlaps, so sweep the object: | |
Reverse velocity | |
Divide velocity by some number, like 5, so we don't jump over a side | |
Move grenade by divided and reversed velocity | |
Test for collision again (return to the top) |
People
What is special about people? They can bump into and stand on top of things. To handle these scenarios, we can write this code:
If girl colliding with a dustbin | |
If she is falling through the dustbin | |
Move her vertically so the soles of her feet are on the top of the dustbin | |
Set her vertical velocity to 0 | |
If she is rising up through the dustbin | |
Move her vertically so the top of her head touching the bottom of the dustbin | |
Set her vertical velocity to 0 | |
If she is moving through the right side of the dustbin | |
Move her horizontally so her right side is touching the left of the dustbin | |
If she is moving through the left side of the dustbin | |
Move her horizontally so her left side is touching the right of the dustbin |
And to figure out whether the girl is falling or rising or walking through the dustbin, we can write this code:
If girl is falling | |
If her feet are lower than the top of the bin | |
If her feet are higher than the top of the bin + maximum speed | |
The girl is falling through the bin | |
If the girl is rising | |
If her head is higher than the bottom of the bin | |
If her head is lower than the bottom of the bin - maximum speed | |
The girl is bumping against the bottom of the bin | |
If the girl's right side is past the bin's left side | |
If her left side is not past the bin's left side | |
If she is not on top of the bin | |
She is bumping against the left side of the bin | |
If the girl's left side is past the bin's right side | |
If her right side is not past the bin's right side | |
If she is not on top of the bin | |
She is bumping against the right side of the bin |
Exploding barrels
Exploding barrels are not so notable for their explodeyness as for the fact that they can be pushed. Using the code we are already using for the girl, we can handle this:
If dustbin is colliding with a girl | |
If she is moving through the left side of the dustbin | |
Move the dustbin horizontally so its left side is touching the girl's right | |
If she is moving through the right side of the dustbin | |
Move the dustbin horizontally so its right side is touching the girl's left |
Artificial intelligence
That’s it for the collision detection in Pistol Slut. Well done. My next article will be about artificial intelligence with state machines.
Subscribe to my newsletter to hear about my latest work