JavaScript Game Tutorial - Space Invaders Part 6 - Optimization
This is the sixth part in a series about creating a Space Invaders clone in JavaScript. It is highly recommended to start from the beginning as each part builds directly upon the previous.
| Space Invaders Tutorial Series | |
|---|---|
| Part 0 | Beginner JavaScript Game Tutorial For Professional Use |
| Part 1 | Math Classes and Game Entity Structure |
| Part 2 | User Input |
| Part 3 | Enemy Behavior |
| Part 4 | Collision Detection and Projectiles |
| Part 5 | Sprites and User Interface |
| Part 6 | Optimization |
| Part 7 | 3D Renderer |
| Part 8 | Events and Audio |
Introduction
In Part 5, we completed a fully working Space Invaders clone. Now it is time to optimize the code.
In a real time performance application like a game, it is very important to have a stable frame rate. It can be very disruptive to have sudden frame drops. In JavaScript, one of the things that can cause this is the Garbage Collector. In order for it to run, it has to pause execution of the program, which can easily lead to frame drops if it happens at the wrong time. There is no way to directly control the garbage collector, but you can certainly minimize the work it has to do.
The garbage collector finds objects that aren't being referenced and clears the memory. Therefore, in order to keep its job simple, we want to prevent objects from being dereferenced as much as possible. The worst offenders are temporary objects that get created at the start of a function and dereferenced at the end. Every time this function is called, work is being added to the garbage collector. In a game, some functions could be called dozens of times per frame, adding a tremendous amount of temporary objects to the memory space.
Instead of using local temporary variables, we will try to move those into the class, or other closure, so they can be reused without ever being dereferenced. We will also look for ways to use a pool of objects for situations that aren't as direct as a local temporary variable.
Goals
The goals for this part are:
- Minimize repeated memory allocations to keep garbage collection at a minimum.
- Rewrite Vector2D and Rectangle to not require frequent temporary variables.
- Create a CloneablePool class to store the most used Entity objects.
Firefox Developer Tools
For something small like this Space Invaders clone, it is pretty easy to just read the code and look for every new allocation and find a way to store that variable in a more permanent spot. But in a larger program, you need to prioritize the worst offenders. Thankfully, finding them is easy by using the developer tools in Firefox, or most any other web browser.
In Firefox, open the Developer Tools and click on Performance. In the gear menu, make sure Record Allocations is selected. Now run Invaders and then click "Start Running Performance." We don't actually care about the initial allocations when the game first loads, we only want the allocations that are running continuously throughout the life of the game.
Once this runs for a while, stop recording and click on the Allocations tab. Now you will clearly see which functions are allocating the most memory. Just focus your efforts on the function with the most allocations, then rerun the performance test and see what the next worst culprit is and so on.
Math
The original implementation of Vector2D requires instantiating new objects to perform every single operation. I think this functional approach reads better and is less prone to errors, but it is very wasteful when it comes to memory. It creates a lot of trash for the garbage collector to have to sift through every single frame.
For the sake of limiting the memory allocations, let's have the operations act on the objects themselves and carefully restructure code that uses these functions to store and reuse temporary variables.
//
// Vector2d
//
var Vector2d = function (x, y) {
this.x = x;
this.y = y;
};
Vector2d.prototype.set = function (x, y) {
this.x = x;
this.y = y;
};
Vector2d.prototype.clone = function () {
return new Vector2d(this.x, this.y);
};
Vector2d.prototype.add = function (v2) {
this.x += v2.x;
this.y += v2.y;
};
Vector2d.prototype.subtract = function (v2) {
this.x -= v2.x;
this.y -= v2.y;
};
Vector2d.prototype.scalarMultiply = function (s) {
this.x *= s;
this.y *= s;
};
Similarly, we need to make the same change to Rectangle. The union operation will now modify the rectangle directly.
//
// Rectangle
//
function Rectangle (x, y, width, height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
Rectangle.prototype.set = function(x, y, w, h) {
this.x = x;
this.y = y;
this.width = w;
this.height = h;
};
Rectangle.prototype.clone = function () {
return new Rectangle(this.x, this.y, this.width, this.height);
};
Rectangle.prototype.left = function () {
return this.x;
};
Rectangle.prototype.right = function () {
return this.x + this.width;
};
Rectangle.prototype.top = function () {
return this.y;
};
Rectangle.prototype.bottom = function () {
return this.y + this.height;
};
Rectangle.prototype.intersects = function (r2) {
return this.right() >= r2.left() &&
this.left() <= r2.right() &&
this.top() <= r2.bottom() &&
this.bottom() >= r2.top();
};
Rectangle.prototype.containsPoint = function (x, y) {
return this.left() <= x &&
x <= this.right() &&
this.top() <= y &&
y <= this.bottom();
};
Rectangle.prototype.union = function (r2) {
var x, y, width, height;
if( r2 === undefined ) {
return;
}
x = Math.min( this.x, r2.x );
y = Math.min( this.y, r2.y );
width = Math.max( this.right(), r2.right() ) -
Math.min( this.left(), r2.left() );
height = Math.max( this.bottom(), r2.bottom() ) -
Math.min( this.top(), r2.top() );
this.x = x;
this.y = y;
this.width = width;
this.height = height;
};
Cloneable Pool
For longer lived objects, we want to create a pool so that those objects don't have to be dereferenced, but can be saved and used later when they are needed again. I call this the CloneablePool because the objects in the pool have to implement an informal "Cloneable" protocol by having init() and clone() functions.
This works especially well when the amount of objects will stay in the same range over time, which is exactly what we have with the Enemy, Projectile and Explosion Entities. Every round will have the same number of Enemies created, there will only be a handful of Projectiles on screen at any one time, and there will only ever be one explosion on screen.
This is a very basic pool system, but it is enough for our purposes. A more complete version would have a mechanism to release unused memory. In a more dynamic game, you could have rare moments where you allocate many more objects than usual, and you don't want to hold onto that memory forever, which is what this simple implementation does.
| CloneablePool | |
|---|---|
| Function | Description |
| CloneablePool( cloneable ) | The constructor takes a Cloneable object that will be used as a template for all objects created in the pool. Consequently, pools may only contain one type of object. |
| take() | Returns a clone of the template object that has had its init() method called. If no pool objects are available, a new clone is created and added to the pool. |
| putBack( cloneable ) | Returns the object to the pool, marking it as available. If the object isn't in the pool, nothing happens. |
//
// Cloneable Pool
//
function CloneablePool( cloneable ) {
this.template = cloneable;
this.pool = [];
}
CloneablePool.prototype.take = function () {
// If there is an available object, return it.
for(var i=this.pool.length-1; i>=0; i--) {
if( this.pool[i].available ) {
this.pool[i].available = false;
this.pool[i].object.init();
return this.pool[i].object;
}
}
// Otherwise, create a new one and return it.
var obj = this.template.clone();
obj.init();
this.pool.push({available: false, object:obj});
return obj;
};
CloneablePool.prototype.putBack = function (cloneable) {
// Mark the object as available again.
for(var i=this.pool.length-1; i>=0; i--) {
if( this.pool[i].object === cloneable ) {
this.pool[i].available = true;
break;
}
}
};
Of course, the changes to Vector2D, Rectangle and the addition of CloneablePool have big impacts all over the code base. Let's go through it from top to bottom and come up with solutions for each class.
Entity
Entity will be given an init() and clone() method so that it can work in a CloneablePool. The init() method sets all the values to the default. The clone() method creates a new object using the same values as the original object.
We will also update collisionRect(). Previously, we created a new rectangle every single time collisionRect() was called. Let's instead store the collision rectangle as a member variable and just update its value and return it in collisionRect().
//
// Entity
//
function Entity(position, speed, direction) {
this.position = position.clone();
this.speed = speed;
this.direction = direction.clone();
this.time = 0;
this.width = 5;
this.height = 5;
this.hp = 1;
this._collisionRect = new Rectangle(
this.position.x - this.width/2,
this.position.y - this.height/2,
this.width,
this.height );
}
Entity.prototype.init = function () {
this.position.set(0, 0);
this.speed = 0;
this.direction.set(0, 0);
this.time = 0;
this.width = 5;
this.height = 5;
this.hp = 1;
};
Entity.prototype.clone = function () {
return new Entity(this.position, this.speed, this.direction);
};
Entity.prototype.update = function (dt) {
this.time += dt;
};
Entity.prototype.collisionRect = function () {
this._collisionRect.x = this.position.x - this.width/2;
this._collisionRect.y = this.position.y - this.height/2;
this._collisionRect.width = this.width;
this._collisionRect.height = this.height;
return this._collisionRect;
};
Player
Continuing down to the Player class, there is an obvious problem in the updateDirection() function. The original version instantiates 3 vectors to calculate the direction. With our new Vector2D, we don't have to instantiate any at all, we can simply modify the direction directly.
Player.prototype.updateDirection = function () {
var x = 0;
if( this.movingLeft ) {
x -= 1;
}
if( this.movingRight ) {
x += 1;
}
this.direction.set(x, 0);
};
In the Player fire() function, we can fix two things now. Previously, we used a filter on the projectiles array to find how many player projectiles existed. This required creating a whole new array just to get this count. Instead, we now count the number of player projectiles directly.
Secondly, we update the Projectile creation to use the pool. All we have to do is take() a projectile from the pool, set its properties and add it to the game object as normal.
Player.prototype.fire = function () {
var playerProjectileCount = 0;
var projectiles = game.projectiles();
for(var i=projectiles.length-1; i>=0; i--) {
if(projectiles[i].type === "player") {
playerProjectileCount++;
}
}
if( playerProjectileCount === 0 ) {
var proj = game.projectilePool().take();
proj.position.set( this.position.x, this.position.y );
proj.speed = 180;
proj.direction.set( 0, -1 );
proj.type = "player";
game.addEntity(proj);
}
};
Enemy
Enemy also gets init() and clone() functions so it can be placed in a CloneablePool.
Enemy.prototype.init = function () {
Entity.prototype.init.call(this);
this.width = 13;
this.height = 10;
this.rank = 0;
this.dropTarget = 0;
this.dropAmount = 1;
this.timer = 0;
this.firePercent = 10;
this.fireWait = Math.random() * 5;
};
Enemy.prototype.clone = function () {
return new Enemy(this.position, this.speed, this.direction, this.rank);
};
There are several tricks we can do in the Enemy.update() function to save on allocations. These really add up, since this is called on every Enemy every single frame.
- We use a closure to store the temporary p variable and the existsUnderneath() function.
- We update the way we choose the direction and calculate p to use our new Vector2D functions.
- Just like Player, we now use the projectile pool when firing a projectile.
Enemy.prototype.update = function () {
var p = new Vector2d(0, 0);
function existsUnderneath(e) {
var rect = e.collisionRect();
if( !rect ) {
return false;
}
return p.y <= rect.top() &&
rect.left() <= p.x && p.x <= rect.right();
}
return function update (dt) {
// Edge collision
var enemiesLeft = game.enemiesRect().left(),
enemiesRight = game.enemiesRect().right(),
edgeMargin = 5,
gameLeftEdge = game.gameFieldRect().left() + edgeMargin,
gameRightEdge = game.gameFieldRect().right() - edgeMargin;
Entity.prototype.update.call(this, dt);
// Drop if the enemiesRect hits an edge margin
if( (this.direction.x < 0 && enemiesLeft < gameLeftEdge) ||
(this.direction.x > 0 && enemiesRight > gameRightEdge) ) {
this.dropTarget += this.dropAmount;
}
// Determine Direction
if( this.position.y < this.dropTarget ) {
this.direction.set(0, 1);
}
else if( this.direction.y > 0 ) {
var x = (enemiesRight > gameRightEdge) ? -1 : 1;
this.direction.set(x, 0);
}
// Determine Firing Weapon
p.set( this.position.x, this.position.y + 5);
this.timer += dt;
if( this.timer > this.fireWait ) {
this.timer = 0;
this.fireWait = 1 + Math.random() * 4;
if( randomInt(100) < this.firePercent &&
!game.enemies().find(existsUnderneath) ) {
var proj = game.projectilePool().take();
proj.position.set( p.x, p.y );
proj.speed = 60;
proj.direction.set( 0, 1 );
proj.type = "enemy";
game.addEntity(proj);
}
}
};
}();
Projectile
Projectile just gets init() and clone() methods so it can work in CloneablePools.
Projectile.prototype.init = function () {
Entity.prototype.init.call(this);
this.width = 1;
this.height = 5;
this.type = "";
};
Projectile.prototype.clone = function () {
return new Projectile(this.position, this.speed, this.direction, this.type);
};
Explosion
Same as Projectile, Explosion gets init() and clone() functions.
Explosion.prototype.init = function () {
Entity.prototype.init.call(this);
this.width = 13;
this.height = 10;
this.rank = 0;
this.duration = 0;
};
Explosion.prototype.clone = function () {
return new Explosion(this.position, this.speed, this.direction, this.rank, this.duration);
};
Physics
We update the physics object to use the new Vector2D. We pull out the velocity temporary variable and make it a member variable that keeps getting reused.
The collision detection has been completely rewritten. Previously, a list of collisions to check was created, which required a lot of memory allocations. Now we handle the collisions as they are found, which requires no memory allocations.
//
// Physics
//
var physics = (function () {
var velocityStep = new Vector2d(0, 0);
function _collide(entity0, entity1) {
if( entity0 && entity1 &&
entity0.collisionRect().intersects(entity1.collisionRect()) ) {
entity0.hp -= 1;
entity1.hp -= 1;
}
}
function _update(dt) {
var i, j, e,
entities = game.entities(),
enemies = game.enemies(),
projectiles = game.projectiles(),
player = game.player();
for( i=entities.length-1; i>=0; i-- ) {
e = entities[i];
velocityStep.set(e.direction.x, e.direction.y);
velocityStep.scalarMultiply( e.speed*dt );
e.position.add( velocityStep );
}
// Collision Detection
// Player vs All enemies
for( i=enemies.length-1; i>=0; i-- ) {
_collide(player, enemies[i]);
}
// Projectiles vs other Entities
for( i=projectiles.length-1; i>=0; i-- ) {
// Enemy Projectiles vs Player
if( projectiles[i].type === "enemy") {
_collide(projectiles[i], player);
}
// Player Projectiles vs Enemies
else if( projectiles[i].type === "player" ) {
for( j=enemies.length-1; j>=0; j-- ) {
_collide(projectiles[i], enemies[j]);
}
}
}
// Enemy vs floor (special case)
if( game.enemiesRect() && player &&
game.enemiesRect().bottom() > player.collisionRect().bottom() ) {
game.setGameOver();
}
...
})();
Game
The game object has several improvements. Most of them are centered around more efficient handling of Entities.
We add this function that will delete an element from an array without having to create a new array in the process. This works by replacing the element at the index with the last element in the array and then simply shortening the length of the array.
Keep in mind that this changes the order of objects in the array, which is a terrible side effect in an array function. However, the order of the arrays we use isn't important, so this is a very fast way to delete an element in our specific case.
function mutableRemoveIndex(array, index) {
if( index >= array.length ) {
console.error('ERROR: mutableRemoveIndex: index is out of range');
return;
}
if( array.length <= 0 ) {
console.error('ERROR: mutableRemoveIndex: empty array');
return;
}
array[index] = array[array.length-1];
array[array.length-1] = undefined;
array.length = array.length-1;
}
We create CloneablePool objects for the Enemies, Projectiles and Explosions.
var _enemyPool = new CloneablePool(
new Enemy(new Vector2d(0, 0),
0,
new Vector2d(0, 0),
0));
var _projectilePool = new CloneablePool(
new Projectile(new Vector2d(0, 0),
0,
new Vector2d(0, 0),
""));
var _explosionPool = new CloneablePool(
new Explosion(new Vector2d(0, 0),
0,
new Vector2d(0, 0),
0,
0));
We have to update the calculation for the _enemiesRect in the Game update() function. We will manually go through the enemies and update the existing _enemiesRect using the new Rectangle.union() function.
// Calculate the bounding rectangle around the enemies
if( _enemies.length > 0 ) {
// Prime _enemiesRect
var rect = _enemies[0].collisionRect();
_enemiesRect.set(rect.x, rect.y, rect.width, rect.height);
// Calculate the rest of the enemiesRect
for( i=_enemies.length-1; i>=0; i-- ) {
_enemiesRect.union(_enemies[i].collisionRect());
}
}
In removeEntities(), we now use the mutableRemoveIndex() function and return objects to their pools.
function _removeEntities(entities) {
if( entities.length === 0 ) {
return;
}
for( var i=entities.length-1; i>=0; i--) {
var idx = _entities.indexOf(entities[i]);
if( idx >= 0 ) {
mutableRemoveIndex(_entities, idx);
}
idx = _enemies.indexOf(entities[i]);
if( idx >= 0 ) {
mutableRemoveIndex(_enemies, idx);
_enemyPool.putBack(entities[i]);
}
idx = _projectiles.indexOf(entities[i]);
if( idx >= 0 ) {
mutableRemoveIndex(_projectiles, idx);
_projectilePool.putBack(entities[i]);
}
_explosionPool.putBack(entities[i]);
}
if(entities.includes(_player)) {
_player = undefined;
}
}
We need to update the creation of Enemies and Explosions. When an Enemy dies, we take an Explosion from the pool, set its properties and add it as usual.
if( e instanceof Enemy ) {
_score += e.rank + 1;
var exp = _explosionPool.take();
exp.position.set(e.position.x, e.position.y);
exp.speed = e.speed;
exp.direction.set(e.direction.x, e.direction.y);
exp.rank = e.rank;
exp.duration = 5/60;
this.addEntity(exp);
}
It's exactly the same for creating Enemies.
var dropTarget = 10+j*20,
enemy = _enemyPool.take();
enemy.position.set(50+i*20, dropTarget-100);
enemy.direction.set(1, 0);
enemy.speed = _enemySpeed;
enemy.rank = 4-j;
enemy.dropTarget = dropTarget;
enemy.firePercent = _enemyFirePercent;
enemy.dropAmount = _enemyDropAmount;
this.addEntity( enemy );
We have to expose the projectilePool for use in the Enemy and Player objects when they create Projectiles.
return {
...
projectilePool: function () { return _projectilePool; }
};
})();
Finally, another trick we can do is store the callback function we use for requestAnimationFrame() in a variable. This saves allocating that function variable every single frame.
var _updateFunc;
function _start() {
...
if( !_started ) {
_updateFunc = this.update.bind(this);
window.requestAnimationFrame(_updateFunc);
_started = true;
}
}
function _update(time) {
...
window.requestAnimationFrame(_updateFunc);
}
Player Actions
There some small tweaks we can do that save some allocations on every user input. We can move the action dictionaries out from the start and end functions and into the singleton so we only create those objects once.
//
// Player Actions
//
var playerActions = (function () {
var _ongoingActions = [];
var startActs = {
"moveLeft": function () {
if(game.player()) game.player().moveLeft(true);
},
"moveRight": function () {
if(game.player()) game.player().moveRight(true);
},
"fire": function () {
if(game.player()) game.player().fire();
}
};
var endActs = {
"moveLeft": function () {
if(game.player()) game.player().moveLeft(false);
},
"moveRight": function () {
if(game.player()) game.player().moveRight(false);
}
};
function _startAction(id, playerAction) {
if( playerAction === undefined ) {
return;
}
var f;
if(f = startActs[playerAction]) f();
_ongoingActions.push({ identifier: id,
playerAction: playerAction });
}
function _endAction(id) {
var f;
var idx = _ongoingActions.findIndex(
function(a) {
return a.identifier === id;
});
if (idx >= 0) {
if(f = endActs[_ongoingActions[idx].playerAction]) f();
_ongoingActions.splice(idx, 1); // remove action at idx
}
}
return {
startAction: _startAction,
endAction: _endAction
};
})();
Similarly, we can pull out getOffsetLeft() and getOffsetTop() from within getRelativeTouchCoords() to save creating those functions on every touch.
//
// Touch
//
function getOffsetLeft( elem ) {
var offsetLeft = 0;
do {
if( !isNaN( elem.offsetLeft ) ) {
offsetLeft += elem.offsetLeft;
}
}
while( elem = elem.offsetParent );
return offsetLeft;
}
function getOffsetTop( elem ) {
var offsetTop = 0;
do {
if( !isNaN( elem.offsetTop ) ) {
offsetTop += elem.offsetTop;
}
}
while( elem = elem.offsetParent );
return offsetTop;
}
function getRelativeTouchCoords(touch) {
var scale = game.gameFieldRect().width / canvas.clientWidth;
var x = touch.pageX - getOffsetLeft(canvas);
var y = touch.pageY - getOffsetTop(canvas);
return { x: x*scale,
y: y*scale };
}
Conclusion
I hope this has been an enlightening look into the optimization stage of game development. This certainly isn't the end-all-be-all of optimization guides, this was just a one-day pass over the code looking for the most obvious problem areas and fixing them.
Some of these add quite a bit of complexity for sake of saving a few allocations, but if those allocations happened to be very large objects, the tradeoff is worth it, as keeping a steady frame rate is critically important in most games.
In the next parts:
I have packaged the code for the full tutorial series for anyone interested in downloading it.
