There is hardly a single game that does not need some form of collision between game objects. In many cases it is enough to approximate the shape of an object by a simpler one to simplify and speed up collision detection. It is for example very common – especially in 2D games – to use circles or boxes as colliding shapes.
Today I want to talk about how we can make use of collision code written for simple shapes like circles, and still end up with much more complex collision behaviour.
Why circles?
The great advantage of using circles for collision detection is how easy this makes computation. A collision check between two circles is as easy as checking the distance between two points, and even shooting rays at circles – a common task if we are looking at games with any sort of projectile – only takes a couple of lines of code.
In many ways, circles are the simplest two-dimensinoal shape with greater than zero area. This is why we will use them in this post as an example for the technique I would like to talk about.
The same can be applied to any other shape however, and doing so can lead to even more flexible results – although it means loosing some of the efficiency of the code.
Limitations of circles
As simple as they are, circles have limitations when it comes to using them for collision checks. Chief among them: they are circles. This means that they are a very bad simplification for any shapes that are not circular – or close to – themselves.
On the surface this may make circles seem rather unsuitable for almost any kind of collision testing – unless we are actually dealing with circular objects.
However, if we take enemies in a shoot-em-up game as an example, we can see that circles do a reasonable job at approximating simple ships. Especially in a fast paced game, the player will hardly ever notice that we are cheating in this way. This is especially true for small objects, since here the error of approcimation is correspondingly small.
When it comes to larger objects however, we run into trouble. Take for example the image of a boss enemy in Roche Fusion below.
Clearly, a circle is not a good fit for this enemy. We will either end up with a circle much too large, or a circle much too small.
In either case, the player will notice that they either seem to be hitting an invisible wall in front of the enemy, or they will wonder why they can only hit the enemy in the center, and not to its sides.
We need a better solution for cases like this.
Multiple circles
Ignoring the possibility to make our collision system significantly more complicated by including shapes like boxes, or even arbitrary polygons, we are left with only one option: use more circles.
If we do not limit ourselves to a single circle per object, we can approximate any shape as arbitrarily closely as we like. The only thing we need to do is use lots of small circles. This allows us to even pretend that an object has straight edges and corners.
The only remaining question is: how do we best handle multiple circles per object, in a way that is both flexible and efficient?
For non deformable objects, this is relatively straight forward. We can store the relative position of each circle to the object’s center, as well as the circle’s size.
When testing for collisions we then have to either:
- perform all collision checking in the local space of the object, or
- calculate the absolute position of all circles and test against these.
However, I will not go into too much detail on these here. Instead, there is a second question I want to ask.
What if we are dealing with deformable objects?
Moving circles
This is the question we had to answer for Roche Fusion almost two years ago when it became clear that single circles would not work for many of the larger units in the game.
The solution to this problem was surprisingly simple however. The key aspect was the way we are rendering – and deforming – any kind of unit in Roche Fusion.
We do this by using a keyframe animated skeleton.
That means that each unit has a skeleton of bones that is represented by a tree, where each node is a bone and knows its position and orientation relative to its parent.
Most units consist of many sprite, each of which is linked to one of the bones and moves, rotates, and scales with it. This allowed us to add interesting visual transformations of units with hardly any special work from our sprite artist.
We realised that it would be almost trivial to give each bone in this skeleton a radius for collision checking, so this is exactly what we did
This system allowed us to create virtually arbitrary collision volumes for the game’s units – all from within our animation editor, which made it very easy to correspond collision shapes with the visual sizes of the varies sprites of the enemies.
Conclusion
By linking two existing systems – circle collisions, and skeletal keyframe animations – together, we were able to easily create much more intuitive and realistic looking collision detection in Roche Fusion without the need to implement collision testing code for shapes other than circles.
Let me know what you think of this approach, especially if you have used it yourself – maybe in a different way – or if you think there are better alternatives to solve the same problem.
Next week I will continue on this topic and explain how we used smart caching of collision shapes to significantly increase the performance of Roche Fusion’s physics simulations.
Until then, enjoy the pixels!
| Reference: | Animation based collision volumes from our NCG partner Paul Scharf at the GameDev<T> blog. |
