Optimizing WarSim

When I first started thinking about WarSim, I knew it would be a game full of challenges. I had the game in mind for a while, as it is kind of a remake of my first real game (made using Flash), but I always portponed its development because it would involve a lot of work. Indeed, HTML5 is getting faster, but complex games like this are still very rare.

Another reason I kept postponing the game was performance: I wanted the game to be playable on mobile, but making a game with so many enemies, large maps and full of effects was hardly compatible with current mobile devices, unless it was optimized from the start. Now that the game is done, I can share some of the tricks I used to make it playable at a decent framerate.

Taking care of what matters

When creating a game with quite large levels, one thing you have to worry about is to take care what you need only, and nothing else. For instance, if an enemy is on the other side of the map, and you can't see it, why bother making it move? Its AI might not be very complex, that is still execution time that you could save.

The lazy way

One lazy easy way to do it is to check if the enemy is visible by checking the distance from the camera. Something like this:

for each enemy in world:
    if distance < MAX_DISTANCE:
        apply_ai()
    else:
        // enemy is too far, do nothing

This is a solution I've used in several projects, and it works pretty well. You still have to loop over all the enemies, therefore complexity is the same, but enemies that are too far won't take too long.

Though, there are cases where this method is flawed. Let's say we're adding bullets in the world. At each frame, we need to check if the bullet is hitting an enemy.

for each bullet in world:
    for each enemy in world:
        if bullet hits enemy:
            kill_enemy()
            remove_bullet()
        else:
            move_bullet()

Now, for each frame, we need to loop over every single bullet, and every single bullet needs to check if it's hitting every single enemy. Your complexity becomes O(number_of_bullets * number_of_enemies), which could easily be a very high number.

Still not convinced there is a problem? Let's say we need to check if enemies are colliding with other enemies. The complexity could become O(number_of_enemies²). Not really something acceptable given the number of enemies.

Using a more complex data structure

The idea would be to be able to only loop over the elements that are concerned. One famous solution is the Quadtree data structure. Basically, elements are stored within a tree which guarantees that each leaf does not contain more than n elements.

Quadtrees are interesting but they need to be maintained, which makes them more complex. There are libraries for that, but I couldn't find one that wouldn't rebuild the entire tree to maintain it. Therefore I used my own, more intuitive solution: a grid.

The idea is to simply divide the global list containing enemies (or anything else) into smaller lists. Each enemy is inserted to the corresponding list.

Here is an example of how elements within a world would be stored:

Example of elements stored within a grid

In this grid, we have 13 elements, stored in 16 different lists: one for each cell. Each cell contains a small amount of elements.

Now, back to our initial problem. Let's say we want to get all the enemies that are visible. Since our camera might see several cells at the same time, here is the algorithm:

for each visible cell:
    for each element in the cell:
        do_something()

This already looks much better than the distance solution. Instead of iterating over every single element in our world, we only iterate over the elements that could be seen. Of course, some of them would still not be visible, but there isn't that much.

In terms of complexity, theoretically, this is the same as having a single list, since all elements might be stored in the same cell. Though, this is very unlikely, so in the end, this should be faster.

If your elements are moving, which is probably the case, you also need to maintain that grid up-to-date. All you have to do is to check if an element needs to be moved from one cell to the other.

This is where the cell size becomes important. If your cells are too small, elements will always need to be moved from one cell to another, which is gonna cost you a lot. On the contrary, if your cells are too big, you will end up with bigger lists, and you will lose the advantage of using the grid.

You also have to keep in mind the type of lookups you need to perform. For instance, if you only want to retrieve the elements close to a certain point, having smaller cells might be a good solution.

The cell size is really something that should be different for each project, depending on your needs.

You should also mix structure types based on your need. For instance, in my case, I only want to make the enemies that are visible to move. The grid is perfect for that. But I also need to make the bullets move. These bullets won't be created unless they're shot by enemies, therefore they should be close, so I don't need to use a grid: a simple global list is enough. It's all about the lookups you need to perform.

One way to easily mix those structures is to introduce an abstraction layer. For instance, you could have an abstract class called ElementsContainer, and subclasses implementing different data structures, instead of using arrays, grids and trees directly.

Example of data structures abstraction

Applying the same idea to the rendering

When rendering the level, the same problem arises: why display what the player can't see?

In most games, rendering elements that are outside of the screen is not a big deal: the world is small and does not contain many elements. In my case, I need to render quite large maps that are made of thousands of tiles.

What's more, the rendering time is the slowest part. If you want to optimize your game, this is definitely the part you should look into.

The first idea would be to cache the whole level, store it as a huge image, and render it at each frame. The issue is that the image would be too big, especially for mobile devices that are limited. Also, I would be rendering a lot of off screen parts, which has an impact on performance.

The second idea would be to set only the visible elements to be rendered. The issue is that it involves a huge loop.

The idea I kept consists in dividing the world as a grid (yes, again). Each cell would only contain the corresponding tiles. Each cell is then cached, so I only have a few images to render, and all the sprites are removed, to free some memory.

Then, I can use an algorithm that is similar to the one above to only render the necessary cells:

// Resetting all cells
for each cell:
    set cell not to be rendered

// Setting the right cells to be rendered
for each visible cell:
    set cell to be rendered

If your cells aren't too small, these loops should take very little time to perform. You could also consider not doing this at each frame if the camera doesn't move too fast.

Here is a gif demonstrating how this works:

Demonstration of the rendering cells

The blue rectangle represents the camera. This is what should be seen by the players. Any cell that does not intersect with the frame will not be rendered.

There are still important parts of the levels that are rendered even though they are not visible, but fixing that would require smaller cells, and therefore longer loops (in the algorithm above).

Conclusion

These are some of the tricks that I used to optimize my game. They are simple, therefore easy to implement, but they work quite well. I was able to achieve decent framerates on devices for which HTML5 games are a lot more basic.

In the next article, I will cover the enemies' AI in the game. If you are interested in structuring your game in terms of AI, you should read my article: Combining enemy types and enemy behaviors.

If you found this article interesting, please let me know (on Twitter for example). I am always curious about ways to improve them.