Adrian here, posting after about a million years of silence. Really sorry we haven’t posted anything in a while, we have been SO busy with schoolwork and getting Chronoscience to be one amazing game. Let me tell you, we’ve implemented all this sweet stuff, and we may just have a gameplay video up soon. Stay posted on that ;)

Here I’m going to talk about an essential part of most games – collision detection. This will be a two part installment talking about Grid-Based Collision Systems on the first part and Hierarchical-Grid-Based Systems, what I’ve implemented for Chronoscient, on the second. Since I had trouble finding many resources online on Hierarchical-Grids, I figure I’ll make a contribution to the online community and try my best to explain how they work. These two posts will be based largely off of a paper I found which explains the topic much more thoroughly. I recommend you read it if you want to know more.

The Chronoscient engine does some pretty sweet things. Making entities with predictable futures is no different to the designers/programmers than it is to make regular entities – the engine takes care of figuring out where an entity will be in x milliseconds in the future, completely transparently to the programmer, and it does it with near-perfect accuracy. Unfortunately, it requires a lot of collision checking to do so.

When we first started working on this project, we implemented the easiest collision checking algorithm we could: the naïve solution. The algorithm goes as follows: for every entity we need to check, see if it collides with every other entity we need to check. This worked well enough at the time, and we saw no need to optimize.

If we ran that algorithm on the example situation above you can see that if we’re checking collisions against the player, we need to check the player ship against ten other entities (5 small baddies, 1 big baddie and 4 bullets). This is true for the bullets and the baddies as well (technically we don’t check if baddies are colliding against bullets because we don’t care if they collide against bullets, but that’s beside the point). This technique runs in O(n^2). It is a fine and dandy thing to do for situations without too many entities, but if we ever run into a situation that’s a bit more busy, we find ourselves in runtime hell.

Most games can handle the 20+ entities you see on screen right here with the simple approach to collision detection, and in truth our engine can handle it as well, until you need to do some future-prediction. Our accurate future-prediction takes a lot of collision checks to do properly, and we started feeling that cost when we added more than a few enemies to the screen.When collision checking is running slowly, there are two likely reasons. Possibility one is that the actual check between two entities is too expensive. This is typical in systems that have very accurate collision checking, such as per-polygon tests. It is not as common when you’re using simple collision values. Possibility two is that you are making too many collision checks at a time.

Using a profiler we found that our problem was entirely the second one. We were only using circles and rectangles for our collision volumes, and thus our collision checks were cheap, but we were simply doing way too many of them to run the game smoothly.

Traditionally you can decrease the number of collision checks you do at a time through a grid-based collision detection system. In these systems, the game space is partitioned into equally-sized squares, called cells. Then we keep track of which cells each of our entities inhabits. For example, in the image below, I’ve marked the cells that contain our player (red), the big baddie named Skips (yellow), and one of our smaller baddies, a stingray (purple).

To check if the player is colliding against anything we now only need to check for collisions against entities that share cells with the player. In this case, we would only have to check the player for collisions against entities that share one of its four cells, and that amounts to only checking if the player collides with the bullet coming near him. One collision check instead of ten, great! For all the other baddies on the screen we only have to do one check total, between a stingray and Skips. This is much faster than doing ten checks for each entity.

While grid-based collision systems are better than the simple approach in just about every way, they do have some issues that could be optimized. The biggest issue is the problem of choosing the right cell-size. In a game like Chronoscient, you can have a wide range of sizes for entities, such as tiny little bullets and big massive bosses. Because of this, cell sizes will end up always being too small or too big for certain entities; and that is not optimal. To illustrate these points, I’ll give examples of the same situation but with different cell-sizes.

We don’t have to do any collision checks between enemies or the player in this example, nothing intersects another entity’s area (ignore the bullets on the lower right, we don’t care about them). However, notice that Skips, the boss in the yellow square, takes up 88 cells. This means that every time we check to see if anything is sharing cells with Skips, we need to query each of those cells, most of which will turn up empty and will just be a waste of our time. In other contexts we could call these queries negligible losses and call it a day, but these small things add up when you’re doing hundreds of checks at a time.

In the next example, we use a very large value for our cell size. Now most entities only take up one or two cells except for Skips. However, the stingray in the top left inside the purple box now shares a cell with the stingray to its right, even though they are pretty far apart. This means we have to do extra checks every time we go through our squares.

As you can see, cell size can really affect the efficiency of grid-based collision detection. Make your cells too small for your entities and you're wasting time looping through cells that are probably empty or only have one entity in them. Make your cells too large for your entity and you'll be doing more collision checks than you need to for entities that are far apart. An approach exists that tries to take away the problem of choosing an appropriate cell-size – hierarchical grids. I’ll talk about those next time, in a week or two.