HTML5 Canvas Game: 2D Collision Detection
In the fourth tutorial of the Galaxian Style HTML5 game series, we’ll be learning about handling collision detection in 2D space and making the bullets hit and destroy ships.
Difficulty: Medium
Languages: HTML5, JavaScript
Code: https://github.com/straker/galaxian-canvas-game/tree/master/part4
Part 4
We’ll begin by seeing the final result of this tutorial. Make sure you click inside the game if the controls aren’t working.
Controls: Move – Arrow keys (←↑↓→)
Shoot – Spacebar
Hitting enemies now results in the enemy disappearing. For the purposes of this demonstration, your ship will not disappear when you get hit by an enemy bullet.
2D Collision Detection
To start out this tutorial, we’ll talk about how to handle 2D collision detection. There are many algorithms for detecting when two objects are touching in 2D space. For our simple game, we don’t have to implement a complex detection algorithm since video games just have to estimate it reasonably well. Thus, we’ll be using a bounding box test for our collision detection.
if (object1.x < object2.x + object2.width && object1.x + object1.width > object2.x &&
object1.y < object2.y + object2.height && object1.y + object1.height > object2.y) {
// The objects are touching
}
A bounding box collision detection algorithm takes two objects and checks to see if the bounds of the first object are within the bounds of the second object. It requires four checks, one for each edge of the bounding box.
To implement collision detection we could just put this algorithm in a loop and check each object against every other object. However, think about how many objects are present in our game. At any one time there could be 18 enemies, one player ship, up to 30 player bullets, and up to 50 enemy bullets. That’s almost 100 objects that could be on the screen at once.
If we were to run this algorithm in a loop as described above, the game would have to perform about 5,000 checks just to check if two objects collide. And since we have to run our collision detection algorithm every frame, it can really slow the game down. So what we need to do is help speed up collision detection.
Improving 2D Collision Detection
Just improving the bounding box algorithm won’t help us speed up collision detection because the main problem lies in how many checks the algorithm has to perform. Therefore, the best way to speed up collision detection is to reduce the number of checks the algorithm has to perform. For that, we will use a technique known as spatial partitioning.
Update from original post
This post has gotten a lot of attention recently with a lot of discussion of my use of spatial partitioning for such a simple game. I would like to address these topics as they had good points that I feel you should know.
It should be known that spatial partitioning is not the only way to speed up collision detection. There are a lot easier ways to do it. You could just grab all the enemy bullets and check each one against just the player ship, and then grab all the player bullets and check them against each enemy. This is just one example and it would achieve the same effect of reducing the number of collision checks.
The use of spatial partitioning for such a simple game is overkill, that I readily admit and agree with. Spatial partitioning is usually used in much larger scale games where the overhead of running collision detection is greater then the use of a quadtree (quadtrees add a lot of additional overhead to a game). The reason I decided to use spatial partitioning in this very simple example is two fold.
The first reason is that a friend and I were making a game that had a lot of bullets and enemies on the screen (well into the thousands). We ran into the issue where the game began to lag and slow down the more bullets and enemies we added. We discovered that the game was lagging due to performing a lot of collision detection with so many objects (we initially used the example given above). After a lot of research, we decided to use a quadtree and were then able to maintain 60FPS. Spatial partitioning and quadtrees were hard for us to understand when we started out, and it was basically just trail and error trying to get them to work for us. It would have been nice to have someone explain them to us and why and how they worked.
The second reason that I wanted to explain spatial partitioning is that this game was intended to be a springboard, and I want developers to take the code and expand upon it for their own games. I tend to develop code with the future in mind, so I decided that teaching developers about a method for collision detection that might save them time and a possible headache in the future was a good idea.
Thus, I use spatial partitioning for this tutorial. It is just one tool in a developers toolbox that I feel is worth knowing. Being a good developer means knowing when to properly use each tool. I hope you understand the drawbacks of using spatial partitioning, but also I hope you understand my reasoning for using it and teaching it in this tutorial. I will reiterate the fact that the use of quadtrees and spatial partitioning for small scale games is unnecessary, as you can achieve better solutions for less overhead. But hey, the game maintains 60FPS even with a quadtree implementation, so the overhead for such a small game isn’t hurting the performance of it :).
Thank you for discussing this article, it’s been great! I’m blown away at the amount of attention it’s received. Please feel free to leave a comment discussing the article and any concerns or improvements you have, or you could send me a tweet as well.
Now back to the tutorial…
Spatial Partitioning
Spatial partitioning takes a confined space (in this case our game) and subdivides it into multiple smaller spaces. By subdividing the space, we are able to quickly determine which objects belong to the same area and only have to run collision detection against those objects. Any object that doesn’t belong in the same space cannot collide, so we don’t have to waste a check on it.
By dividing up the space, we are able to reduce our collision detection checks from 5,000 to about 100 per frame – that’s a huge improvement! To implement this technique, we will use a data structure called a quadtree. You can read all about quadtrees in this article I wrote for Gamedevtuts+
/**
* QuadTree object.
*
* The quadrant indexes are numbered as below:
* |
* 1 | 0
* —-+—-
* 2 | 3
* |
*/
function QuadTree(boundBox, lvl) {
var maxObjects = 10;
this.bounds = boundBox || {
x: 0,
y: 0,
width: 0,
height: 0
};
var objects = [];
this.nodes = [];
var level = lvl || 0;
var maxLevels = 5;
/*
* Clears the quadTree and all nodes of objects
*/
this.clear = function() {
objects = [];
for (var i = 0; i < this.nodes.length; i++) {
this.nodes[i].clear();
}
this.nodes = [];
};
/*
* Get all objects in the quadTree
*/
this.getAllObjects = function(returnedObjects) {
for (var i = 0; i < this.nodes.length; i++) {
this.nodes[i].getAllObjects(returnedObjects);
}
for (var i = 0, len = objects.length; i < len; i++) {
returnedObjects.push(objects[i]);
}
return returnedObjects;
};
/*
* Return all objects that the object could collide with
*/
this.findObjects = function(returnedObjects, obj) {
if (typeof obj === "undefined") {
console.log("UNDEFINED OBJECT");
return;
}
var index = this.getIndex(obj);
if (index != -1 && this.nodes.length) {
this.nodes[index].findObjects(returnedObjects, obj);
}
for (var i = 0, len = objects.length; i < len; i++) {
returnedObjects.push(objects[i]);
}
return returnedObjects;
};
/*
* Insert the object into the quadTree. If the tree
* excedes the capacity, it will split and add all
* objects to their corresponding nodes.
*/
this.insert = function(obj) {
if (typeof obj === "undefined") {
return;
}
if (obj instanceof Array) {
for (var i = 0, len = obj.length; i < len; i++) {
this.insert(obj[i]);
}
return;
}
if (this.nodes.length) {
var index = this.getIndex(obj);
// Only add the object to a subnode if it can fit completely
// within one
if (index != -1) {
this.nodes[index].insert(obj);
return;
}
}
objects.push(obj);
// Prevent infinite splitting
if (objects.length > maxObjects && level < maxLevels) {
if (this.nodes[0] == null) {
this.split();
}
var i = 0;
while (i < objects.length) {
var index = this.getIndex(objects[i]);
if (index != -1) {
this.nodes[index].insert((objects.splice(i,1))[0]);
}
else {
i++;
}
}
}
};
/*
* Determine which node the object belongs to. -1 means
* object cannot completely fit within a node and is part
* of the current node
*/
this.getIndex = function(obj) {
var index = -1;
var verticalMidpoint = this.bounds.x + this.bounds.width / 2;
var horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
// Object can fit completely within the top quadrant
var topQuadrant = (obj.y < horizontalMidpoint && obj.y + obj.height < horizontalMidpoint);
// Object can fit completely within the bottom quandrant
var bottomQuadrant = (obj.y > horizontalMidpoint);
// Object can fit completely within the left quadrants
if (obj.x < verticalMidpoint &&
obj.x + obj.width < verticalMidpoint) {
if (topQuadrant) {
index = 1;
}
else if (bottomQuadrant) {
index = 2;
}
}
// Object can fix completely within the right quandrants
else if (obj.x > verticalMidpoint) {
if (topQuadrant) {
index = 0;
}
else if (bottomQuadrant) {
index = 3;
}
}
return index;
};
/*
* Splits the node into 4 subnodes
*/
this.split = function() {
// Bitwise or [html5rocks]
var subWidth = (this.bounds.width / 2) | 0;
var subHeight = (this.bounds.height / 2) | 0;
this.nodes[0] = new QuadTree({
x: this.bounds.x + subWidth,
y: this.bounds.y,
width: subWidth,
height: subHeight
}, level+1);
this.nodes[1] = new QuadTree({
x: this.bounds.x,
y: this.bounds.y,
width: subWidth,
height: subHeight
}, level+1);
this.nodes[2] = new QuadTree({
x: this.bounds.x,
y: this.bounds.y + subHeight,
width: subWidth,
height: subHeight
}, level+1);
this.nodes[3] = new QuadTree({
x: this.bounds.x + subWidth,
y: this.bounds.y + subHeight,
width: subWidth,
height: subHeight
}, level+1);
};
}
A quadtree will index all of the objects in the game into nodes and subnodes. All objects within a node could potentially collide, so we will check only those objects for collision. With the quadtree in hand, we are almost ready to implement collision detection in our game.
Updating Objects for Collision Detection
There is still one more thing to do before we implement 2D collision detection. Not every object can collide with every other object. For example, a ship won’t collide with it’s own bullet, the same goes for an enemy ship. So we need to check to see if the two objects should collide before we check to see if they are colliding. This means that each object will hold a list of objects that it can collide with and the collision detection algorithm will compare this list with the type of the other object.
To start implementing collision detection, we will edit the Drawable object.
function Drawable() {
this.init = function(x, y, width, height) {
// Defualt variables
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
this.speed = 0;
this.canvasWidth = 0;
this.canvasHeight = 0;
this.collidableWith = "";
this.isColliding = false;
this.type = "";
// Define abstract function to be implemented in child objects
this.draw = function() {
};
this.move = function() {
};
this.isCollidableWith = function(object) {
return (this.collidableWith === object.type);
};
}
The object receives two new variables: collidableWith and isColliding, as well as a new function isCollidableWith() to test if the the object can collide with the given object. The isColliding variable tells us when an object is colliding and shouldn’t be redrawn to the canvas.
With the need to have a list of collidable objects, each object in our game has to implement this change. We’ll start with the Bullet object.
this.draw = function() {
this.context.clearRect(this.x-1, this.y-1, this.width+2, this.height+2);
this.y -= this.speed;
if (this.isColliding) {
return true;
}
else if (self === "bullet" && this.y <= 0 - this.height) {
return true;
}
else if (self === "enemyBullet" && this.y >= this.canvasHeight) {
return true;
}
else {
if (self === "bullet") {
this.context.drawImage(imageRepository.bullet, this.x, this.y);
}
else if (self === "enemyBullet") {
this.context.drawImage(imageRepository.enemyBullet, this.x, this.y);
}
return false;
}
};
/*
* Resets the bullet values
*/
this.clear = function() {
this.x = 0;
this.y = 0;
this.speed = 0;
this.alive = false;
this.isColliding = false;
};
Just the draw() and clear() functions have to be changed. The draw function adds the check to see if the object is colliding. If it is, return true to the object pool to let it know the bullet can be reused. The clear function just resets the isColliding variable to false.
The next object we’ll update is the Ship object.
function Ship() {
this.speed = 3;
this.bulletPool = new Pool(30);
this.bulletPool.init("bullet");
var fireRate = 9;
var counter = 0;
this.collidableWith = "enemyBullet";
this.type = "ship";
this.draw = function() {
this.context.drawImage(imageRepository.spaceship, this.x, this.y);
};
this.move = function() {
counter++;
// Determine if the action is move action
if (KEY_STATUS.left || KEY_STATUS.right ||
KEY_STATUS.down || KEY_STATUS.up) {
// The ship moved, so erase it's current image so it can
// be redrawn in it's new location
this.context.clearRect(this.x, this.y, this.width, this.height);
// Update x and y according to the direction to move and
// redraw the ship. Change the else if's to if statements
// to have diagonal movement.
if (KEY_STATUS.left) {
this.x -= this.speed
if (this.x <= 0) // Kep player within the screen
this.x = 0;
} else if (KEY_STATUS.right) {
this.x += this.speed
if (this.x >= this.canvasWidth - this.width)
this.x = this.canvasWidth - this.width;
} else if (KEY_STATUS.up) {
this.y -= this.speed
if (this.y <= this.canvasHeight/4*3)
this.y = this.canvasHeight/4*3;
} else if (KEY_STATUS.down) {
this.y += this.speed
if (this.y >= this.canvasHeight - this.height)
this.y = this.canvasHeight - this.height;
}
// Finish by redrawing the ship
if (!this.isColliding) {
this.draw();
}
}
if (KEY_STATUS.space && counter >= fireRate && !this.isColliding) {
this.fire();
counter = 0;
}
};
The ship object will set its type and will be collidable with enemy bullets. In the draw() function, we will only redraw the ship and let it fire if it is not colliding with anything.
Next up is the Enemy object.
function Enemy() {
var percentFire = .01;
var chance = 0;
this.alive = false;
this.collidableWith = "bullet";
this.type = "enemy";
/*
* Move the enemy
*/
this.draw = function() {
this.context.clearRect(this.x-1, this.y, this.width+1, this.height);
this.x += this.speedX;
this.y += this.speedY;
if (this.x <= this.leftEdge) {
this.speedX = this.speed;
}
else if (this.x >= this.rightEdge + this.width) {
this.speedX = -this.speed;
}
else if (this.y >= this.bottomEdge) {
this.speed = 1.5;
this.speedY = 0;
this.y -= 5;
this.speedX = -this.speed;
}
if (!this.isColliding) {
this.context.drawImage(imageRepository.enemy, this.x, this.y);
// Enemy has a chance to shoot every movement
chance = Math.floor(Math.random()*101);
if (chance/100 < percentFire) {
this.fire();
}
return false;
}
else {
return true;
}
};
/*
* Resets the enemy values
*/
this.clear = function() {
this.x = 0;
this.y = 0;
this.speed = 0;
this.speedX = 0;
this.speedY = 0;
this.alive = false;
this.isColliding = false;
};
The enemy object will set its type and will be collidable with the player bullets. It will only be redrawn and shoot if it is not colliding, and the clear() function resets the isColliding variable.
The last object to edit is the Pool object.
this.init = function(object) {
if (object == "bullet") {
for (var i = 0; i < size; i++) {
// Initalize the object
var bullet = new Bullet("bullet");
bullet.init(0,0, imageRepository.bullet.width, imageRepository.bullet.height);
bullet.collidableWith = "enemy";
bullet.type = "bullet";
pool[i] = bullet;
}
}
else if (object == "enemy") {
for (var i = 0; i < size; i++) {
var enemy = new Enemy();
enemy.init(0,0, imageRepository.enemy.width, imageRepository.enemy.height);
pool[i] = enemy;
}
}
else if (object == "enemyBullet") {
for (var i = 0; i < size; i++) {
var bullet = new Bullet("enemyBullet");
bullet.init(0,0, imageRepository.enemyBullet.width, imageRepository.enemyBullet.height);
bullet.collidableWith = "ship";
bullet.type = "enemyBullet";
pool[i] = bullet;
}
}
};
this.getPool = function() {
var obj = [];
for (var i = 0; i < size; i++) {
if (pool[i].alive) {
obj.push(pool[i]);
}
}
return obj;
}
For each type of bullet, the player bullets and the enemy bullets, we will set the type and collidableWith variables accordingly. We also add a new function, getPool() to return all alive objects in the pool as an array that will then be inserted into the quadtree.
With all our objects updated, we’re nearly ready to implement collision detection.
The Final Step
To implement the quad tree in our game, we add just one line to the end of the Game object, just before return true;
// Start QuadTree
this.quadTree = new QuadTree({x:0,y:0,width:this.mainCanvas.width,height:this.mainCanvas.height});
Next we can update the animate() function to use the quadtree.
function animate() {
// Insert objects into quadtree
game.quadTree.clear();
game.quadTree.insert(game.ship);
game.quadTree.insert(game.ship.bulletPool.getPool());
game.quadTree.insert(game.enemyPool.getPool());
game.quadTree.insert(game.enemyBulletPool.getPool());
detectCollision();
// Animate game objects
requestAnimFrame( animate );
game.background.draw();
game.ship.move();
game.ship.bulletPool.animate();
game.enemyPool.animate();
game.enemyBulletPool.animate();
}
The first thing we do is clear the quadtree and add all objects to it. Once all objects are added to the quadtree, we run our collision detection algorithm in detectCollision(). We finish by moving and animating all objects on the screen. This order ensures that any objects that collide in the frame are not redrawn at the end of the frame.
The last bit of code is the detectCollision() function.
function detectCollision() {
var objects = [];
game.quadTree.getAllObjects(objects);
for (var x = 0, len = objects.length; x < len; x++) {
game.quadTree.findObjects(obj = [], objects[x]);
for (y = 0, length = obj.length; y < length; y++) {
// DETECT COLLISION ALGORITHM
if (objects[x].collidableWith === obj[y].type &&
(objects[x].x < obj[y].x + obj[y].width &&
objects[x].x + objects[x].width > obj[y].x &&
objects[x].y < obj[y].y + obj[y].height &&
objects[x].y + objects[x].height > obj[y].y)) {
objects[x].isColliding = true;
obj[y].isColliding = true;
}
}
}
};
The function first gets all objects in the quadtree and saves them to a single array. It then loops over each object in the array and retrieves another array of objects that the object could collide with. Lastly, it runs the collision detection algorithm against these objects to see if they collide.
We now have a game that is capable of checking for collisions at 60FPS. It took a bit of refactoring to get there, but it was all worth it in the end.
Conclusion
We had to update almost every object and function in the game, but it now implements 2D collision detection fairly quickly. We also learned a good technique for helping speed up collision detection by implementing a quadtree to reduce collision checks.
In the next and final tutorial, we’ll add finishing touches to our game such as sound, score, and a game over screen. We’ll also talk about ways that you could improve and expand the game.