Managing Entities

As our games get larger, we typically need to add more and more entities into the game world. This can add significant complexity to our game. Consider the simple case of updating our entities. If we have n entities, and we call update() on each, we're looking at a complexity of O(n). If we also test for collisions between each entity in the world, the complexity of that algorithm is O(n^2).

# Entities Updates Collision Tests
10 10 100
100 100 10,000
1000 1000 1,000,000

While the complexity isn't a big issue for small games with few entities, as we can see from the table, once reach 1,000 entities, we're performing a million collision tests and a thousand updates... clearly the brute-force approach does not work well for larger games.

Entity Manager

However, just what does work will vary significantly from game to game; different games suggest different solutions. Nonetheless, it can be helpful to have a uniform abstraction that we can use to discuss and frame the problem. Enter the entity manager, an object responsible for doing just that. We want our entity manager to keep track of all the entities in our game, calling their update and render methods for us. This helps keep our top-level game code cleaner. Let's start with a bare-bones build of such a class:

"use strict"; module.exports = exports = EntityManager; function EntityManager() { this.entities = []; }

Our constructor is unremarkable, it simply sets up an array to hold our entities.

EntityManager.prototype.add = function(entity) { this.entities.push(entity); } EntityManager.prototype.remove = function(entity) { var index = this.entities.indexOf(entity); if(index != -1) this.entities.splice(index, 1); }

The add() and remove() methods simply put entities into or remove them from that array. Note that to remove an item from our array, we use the splice() method to remove one element at the entity's position (i.e. the entity itself). The array is modified in-place, so that it no longer contains the entity.

EntityManager.prototype.update = function(elapsedTime) { this.entities.forEach(function(entity){ entity.update(elapsedTime); }); } EntityManager.prototype.render = function(elapsedTime, ctx) { this.entities.forEach(function(entity){ entity.render(elapsedTime, ctx); }); }

And the update and render methods simply pass along the elapsed time and rendering context to the entities within the list. We'll add a method to query the entity manager for all entities within a region.

function testForRectCollision(r1, r2) { return !( r1.x > r2.x + r2.width || r1.x + r1.width < r2.width || r1.y > r2.y + r2.height || r1.y + r1.height < r2.y ); } EntityManager.prototype.queryRect = function(x, y, width, height) { this.entities.filter(function(entity) { return testForRectCollision(entity, {x: x, y: y, width: width, height: height}); } }

Here we showcase several powerful features of JavaScript. The first is the filter() function for the array, part of an extremely useful family of mapping functions that transform arrays. The filter() function returns a new array composed of all elements that pass the test in the provided function; in this case, all entities that fall within the query rectangle. The second feature we make use of is duck typing. As a dynamically-typed language, JavaScript doesn't require parameters and variables to have a type; so we can use the testForRectCollision() helper method to test any two objects with an x, y, width, and height parameter for a collision. In fact, we dynamically create such an object from our parameters to queryRect().

And finally, we'll add a method to process collisions:

EntityManager.prototype.processCollisions = function(callback) { this.entities.forEach(function(entity1){ this.entities.forEach(function(entity2){ if(entity1 !=== entity2 && testForRectCollision(entity1, entity1) callback(entity1, entity2); }); }); }

Note that here we re-use the testForRectCollision() helper function, along with a simple rejection test (entity1 !== entity2) which prevents us from deciding an entity is colliding with itself. When we find a collision, we defer to the user-supplied callback to handle the decision of what should be done.

The astute observer will recognize that what we have written here is nothing more than the brute force approach we discussed before, abstracted into a class module. This is certainly true, so perhaps it would be better to name this a brute force entity manager. However, it serves as a starting point for discussing adding spatial partitioning.

Grid Spatially-Partitioned Entity Manager

The next step would be to add a spatial partition of some kind to our entity manager, to reduce the complexity of updates and collision tests by limiting the number of entities we need to deal with. Let's look at the case of a grid-based entity manager, which divides the game world into equally-sized cells.

function EntityManager(width, height, cellSize) { this.cellSize = cellSize; this.widthInCells = Math.ceil(width / cellSize); this.heightInCells = Math.ceil(height / cellSize); this.numberOfCells = this.widthInCells * this.heightInCells; this.cells = []; for(var i = 0; i < this.numberOfCells; i++) { this.cells[i] = []; } this.cells[-1] = []; }

We make a number of changes to our constructor to account for the need to divvy the world into grid cells. The supplied width and height parameters are the size of our game world, in pixels, and the cellSize is the length of the side of one of our square grid cells. Exactly what cellSize is optimal varies from game implementation to game implementation; some experiments are called for. However, generally cells will need to be large than the largest entity in the game, as we want them to be wholly contained within a cell, or overlapping at most into immediately adjacent cells.

We also need to initialize our cells to be empty arrays. We also initialize an empty array with the index of -1; this probably seems bizarre to you (or, if are you familiar with languages like Python where a negative index starts counting from the back of the array, dangerous). In fact, we are exploiting an aspect of JavaScript arrays in that they are also an object, and we can use the bracket notation to set properties on objects. So this.cells[-1] is not actually an index in our array, but a property key. The confusion is worth the simplification of indexing, as we will use an index of -1 for entities that are not in the world.

Adding new entities is therefore a simple matter of sorting them into the appropriate cell; we'll do so by using the upper-left-hand corner of the entity's bounds (the x and y) as the position.

function cellIndex(position) { var x = Math.floor(position.x / this.cellSize); var y = Math.floor(position.y / this.cellSize); if(x >= this.widthInCells || y >= this.heightInCells || x < 0 || y < 0) return -1; else return y + this.widthInCells * x; } EntityManager.prototype.add = function(entity) { var index = cellIndex(entity); this.cells[index].push(entity); entity._cell = index; }

First, note the helper function cellIndex() which determines which of our cells the entity should be placed into, or -1 for an entity not within the bounds of our defined world. These entities are placed in the previously discussed out-of-bounds array this.cells[-1], which uses the same notation as those being placed in a proper cell. We then take advantage of JavaScript's dynamic nature to store the cell index in the entity itself. Prefacing the _cell member with an underscore is a visual indicator that this property should not be modified lightly in other code. We'll see how it is used next.

EntityManager.prototype.remove = function(entity) { var index = this.cells[entity._cellIndex].indexOf(entity); if(index != -1) this.cells[entity._cellIndex].splice(index, 1); }

The index stored in the entity's _cell member is used to identify the cell to remove the entity from; instead of necessitating a search of all entities, which would be O(n), we only need to search the much smaller set of entities in the particular cell. It also benefits us in the update:

EntityManager.prototype.update = function(entity) { this.cells.forEach(function(cell) { cells.forEach(function(entity){ entity.update(elapsedTime); var index = cellIndex(entity); if (index != entity._cell) { // Remove from old cell var subIndex = this.cells[entity._cell].indexOf(entity); if(subIndex != -1) this.cells[entity._cell].splice(subIndex, 1); // Place in new cell this.cells[index].push(entity); entity._cell = index; } }); }); }

After we have called the entity's update() method (which, presumably may have moved it), we check to see if it remains in the same cell. If not, we remove it from the old cell and add it to the new. Again, having the cell index available on the entity itself simplifies this process.

Also, we see that to iterate over all the entities, we simply iterate over the cells first, and then the entities in the cells. We don't need the entities array of our brute force approach, though we could certainly add it back; doing so doubles our book-keeping effort, but for some spatial data structures having an easy-to-access array may be worth the hassle. Also, it is important to note that entities that are out-of-bounds not updated by this code; remember that this.cells[-1] is a property, not an array address, so the array method forEach() does not process it. If we want to update off-screen entities, we will need to provide a loop just for them.

There is one final consideration for our entity iteration methods. What if we only wanted to update or render a portion of our game world? This might especially make sense if our world large enough that not all of it is visible in the screen at once. In this case, we probably wouldn't want to render off-screen entities. We might then write our render() method as:

EntityManager.prototype.render = function(elapsedTime, context, viewport) { // Min x range var xMin = Math.floor(viewport.x / this.cellSize); xMin = (xMin > 0) ? xMin : 0; // Max x range var xMax = Math.ceil((viewport.x + viewport.width)/this.cellSize) + 1; xMax = (xMax < this.widthInCells) ? xMax : this.widthInCells; // Min y range var yMin = Math.floor(viewport.y / this.cellSize); yMin = (yMin > 0) ? yMin : 0; // Max y range var yMax = Math.ceil((viewport.y + viewport.height)/this.cellSize) + 1; yMax = (yMax < this.widthInCells) ? yMax : this.widthInCells; // iterate over included cells for(var x = xMin; x < xMax; x++) { for(var y = yMin; y < yMax; y++) { this.cells[y * this.widthInCells + x].forEach(function(entity)) { entity.render(elapsedTime, context); }); } } }

This method calculates the minimum and maximum coordinates of the viewport region, and uses them to iterate over only those cells within the region. Do note that we have to clamp these values to the actual size of the world (as measured in cells) to avoid accidentally drawing cells that don't exist.

We can implement our query function using much the same approach:

function testForRectCollision(r1, r2) { return !( r1.x > r2.x + r2.width || r1.x + r1.width < r2.width || r1.y > r2.y + r2.height || r1.y + r1.height < r2.y ); } EntityManager.prototype.queryRect = function(x, y, width, height) { var results = []; // Min x range var xMin = Math.floor(x / this.cellSize); xMin = (xMin > 0) ? xMin : 0; // Max x range var xMax = Math.ceil((x + width)/this.cellSize) + 1; xMax = (xMax < this.widthInCells) ? xMax : this.widthInCells; // Min y range var yMin = Math.floor(y / this.cellSize); yMin = (yMin > 0) ? yMin : 0; // Max y range var yMax = Math.ceil((y + height)/this.cellSize) + 1; yMax = (yMax < this.widthInCells) ? yMax : this.widthInCells; // iterate over included cells for(var x = xMin; x < xMax; x++) { for(var y = yMin; y < yMax; y++) { results.concat( this.cells[y * this.widthInCells + x].filter(function(entity) { return testForRectCollision(entity, {x: x, y: y, width: width, height: height}); } ); } } return results; }

Here we combine our selection of the cells within the query region with the filter() function we used before, concatinating each cell's results into a single results array that is returned after each is considered. The testForRectCollision() helper is the same; it is simply reproduced for reference.

Finally, we can turn our attention to handling collisions:

EntityManager.prototype.processCollisions = function(callback) { this.cells.forEach(function(cell, index){ // Check for collisions between entities within this cell cell.forEach(function(entity1){ cell.forEach(function(entity2){ if(entity1 !=== entity2 && testForRectCollision(entity1, entity1) callback(entity1, entity2); }); }); // Check for collisions between entities within this cell // and its neighbor to the right if((index + 1) % this.widthInCells != 0) { cell.forEach(function(entity1){ this.cells[index+1].forEach(function(entity2){ if(entity1 !=== entity2 && testForRectCollision(entity1, entity1) callback(entity1, entity2); }); }); } // Check for collisions between entities within this cell // and the cell beneath it if(index >= this.numberOfCells - this.widthInCells) { cell.forEach(function(entity1){ this.cells[index+this.widthInCells].forEach(function(entity2){ if(entity1 !=== entity2 && testForRectCollision(entity1, entity1) callback(entity1, entity2); }); }); } // Check for collisions between entities within this cell // and the cell diagonally beneath to the right if((index + 2) % this.widthInCells != 0 && index >= this.numberOfCells - this.widthInCells) { cell.forEach(function(entity1){ this.cells[index+this.widthInCells+1].forEach(function(entity2){ if(entity1 !=== entity2 && testForRectCollision(entity1, entity1) callback(entity1, entity2); }); }); } }); }

There are four cells we need to check, the current cell, the cell to the right, the cell below, and the cell below to the right. This lets us catch collisions between entities that are partway out of their cell and into the neighboring cell. We don't need to check above or behind, because we start at the upper-right-hand corner and work our way across and down (which means those collisions have already been checked for).

You might question what the benefit of this work is - as we've clearly added a lot of extra code over the brute-force approach. Let's consider it from a complexity angle. What is the worst case scenario for a grid-based spatial partition? That all of our entities are in one cell. In this case, we'll iterate over all the entities twice in our first loop, which is O(n^2) again. For all other cells our forEach() will short-circuit with a length of 0, for only the constant-time cost of a few comparisons. So technically, it will be slightly higher than our brute force approach, but not enough to worry about. But what about best case? That would be when our entities are evenly distributed over our d cells, In this case, each cell will be of cost O((n/d)^2), for d cells. We end up much lower on the exponential growth curve, for much better computation time. And, we haven't added significantly more memory costs - as we've still got the same number of array entries, just spread over d arrays instead of a single array. Of course, there are more record-keeping tasks that need to be performed, so we want to strike a good balance with our choice of cell size.

Also, this suggests that a grid-based spatial approach is best for games where our entities will be more or less evenly spread throughout the game world. If they tend to cluster on a single axis, a single-dimension grid might make more sense. And for large worlds that feature both sparse and densely populated regions, a hierarchical structure like a quadtree will perform better.