Computer Games Programming

ESSENTIAL INGREDIENTS OF A COLLISION DETECTION TECHNIQUE

There are in general six main elements (challenges) need to be addressed effectively by any Collision Detection technique in a 2D platform game environment:

A) To allow use of Arbitrary Geometry (this in plain English means that any kind of obstruction can be literarily anywhere on the screen).

B) To allow Free-form Player Movement (FPM) in every possible direction and jumping (meaning that the player can move freely on a real per-pixel basis or what we have set to represent the pixel basic unit in our game environment).

C) To handle effectively and realistically all possible collisions between the main character (the player controlled character in our game) and the geometry dictated by the game environment.

D) To allow effective and realistic application of Gravity.

E) To effectively and realistically address the so-called “Jitter” problem.

F) To effectively and realistically address the so-called “Bullet-Through-Paper” problem.

Despite the fact that we all tend to regard present computer games status as the most advanced and the only one really worthwhile to spend time on studying, the fact remains and will always remain that all started back in the 80s. Inevitably, most of the classic techniques well-known for their combination of simplicity and efficiency are originating from this in many respects ground-breaking decade.

The “Grid-based” Collision Detection Technique

In “Grid-based” platform games every level of the game is arranged as on a rectangular grid. Each grid square contains a platform or a background tile. The main and all the other characters in the game always reside in exactly one square, with especially the main character largely animated to give the appearance of being half on one square and half on another. Nevertheless, when the main character moves left or right the movement always takes place in such a way as it ends up exactly in the next grid square.

Collision Detection-wise the alignment of the game environment on a grid simplifies things a lot. The game environment is “reproduced” first in a 2D array in RAM and then we check with every frame if the main character’s desired movement will cause him to end up in a platform or other foreground tile; if this is so we prevent the movement from happening. The good news about this technique are there’s absolutely no need for any sort of complicated “Pixel-based” Collision Detection and there are no “Angular Collisions” to worry about since our main character can only move in one of four directions at a time.

Figure 1: “Bomberman” is a “Grid-based” 2D platform game originally released in 1983.

The “Pixel Colour” Collision Detection Technique

This technique was originally invented to take advantage of graphics cards capable of reproducing a limited number of colour combinations (8 or 16 colour combinations). Under this technique, all the background elements in the game environment were to be plotted in one colour, while all other game elements in other colours of choice. The main character is allowed to move around in every possible direction but the colour of adjacent pixels is tested before movement is allowed. The idea here is to check first if the movement will cause the main character to “Collide” with a platform and/or wall. Apart from the fairly simple idea behind this technique and its considerably straight forward implementation, the technique possesses the disadvantage of developers never being able to use the platforms’ colour for other purposes within the game environment or in the making of other characters, or even in the background.

Figure 2: “Background Tiles”, “Hill Tiles” & “Solid Ground Tiles” in a “Pixel Colour” Collision Detection arrangement.

The “Pixel Tile” Collision Detection Technique

For this technique to effectively solve the Collision Detection problem what is required is for the available platforms to be limited to a pre-defined selection of square tiles. The main character can move freely in every direction and a number of “Collision Points” are defined around the main character sprite (his feet, shoulders, knees, head etcetera…) and for each tile type. In a 2D array we store information indicating what’s to be done if a collision occurs on a specific pixel of the tile.

For example, in a 32×32 pixel tile where half of it is representing a hill sloping down from top-left to bottom-right the collision array must specify that when moving left, if a collision occurs between the main character’s feet and the solid part of the tile, the main character must be moved up by one pixel. In the opposite case, the main character must be moved down by one pixel when moving right. That way, what actions required in response to a collision are encoded in the tile information.

The “Mask” Collision Detection Technique

This technique requires a copy of the level (or what’s currently visible of it to the player) to be kept stored in RAM in Black and White colours. For this technique, White colour represents platforms or any other obstructions we have introduced into our level, while Black colour represents literarily anything else. In the same sense, on a respective copy of the main character sprite in RAM, also stored in Black and White colours, White colour represents all the Solid Points on the main character’s figure where collisions must be considered and Black coloured pixels are completely ignored.

A Colour-coded image like this (binary colour representation, namely in Black and White colours only), of a colour image is called a “Mask”. The net effect is that when the main character attempts to move, each White coloured pixel in the main character’s “Mask” is compared with each pixel in the level “Mask” at the corresponding position of the main character in the level. In the case that two pixels are both found to be White colour pixels, then a collision has occurred.

The main advantage of this technique is that the player can move freely in every direction, and the platforms and/or the scenery can be of any shape with no restrictions at all. What’s more, the Collision Detection algorithm if implemented correctly is accurate to the single pixel but contains the inherent deficiency of being potentially very expensive in terms of computational system resources consumption because large Bitmap images may need to be stored in RAM. This technique is one of those that either in its original form or in variations seeking to improve the technique at particular points according to specific needs, is still in use today by a surprisingly large number of games.

The “Bounding Box” Collision Detection Technique

In this technique, the “Bounding Box” term refers to the smallest possible rectangle that can be made to entirely contain a piece of geometry. The “Bounding Box” of the main character is compared with the “Bounding Box” of each platform tile and/or enemy characters (the ones within a particular distance from the main character). In the case that the “Bounding Boxes” intersect, then a collision has occurred.

The technique works perfectly fine for Horizontal or Vertical (flat) platforms and under the condition that the main character and the enemies are mostly rectangular in shape. On the contrary, it fails miserably when the game environment is made of sloped surfaces, abstract shapes and/or shapes being or close to circular. For these reasons the “Bounding Box” technique is nowadays used as the basis and/or optimisation component of other more modern techniques. This is so because of the fact that checking the “Bounding Boxes” of the level scenery against the “Bounding Box” of the main character is a very quick way of narrowing down the number of pieces of geometry in need of further testing for achieving a more accurate Collision Detection result.

The “Discrete Collision Detection” Technique

Many modern computer games employ this technique in order to realise an effective and accurate Collision Detection algorithm. The technique’s main advantage is that can easily deal with many simultaneously moving objects within a game environment colliding with one another as in a single frame, in contrary to the “one-object-colliding-with-a-static-set-of-geometry” situation.

For this to become possible the technique demands the calculation of the total “Bounding Box” for each moving object, in respect to both its Current and Expected position after the current frame. This is called an “Axis-aligned Bounding Box” (AABB). The simple rule governing the technique is that any “Axis-aligned Bounding Boxes” overlapping are considered to be at risk of their objects colliding (as their paths may, or not, cross each other). Each set of overlapping “Axis-aligned Bounding Boxes” is then grouped together into a so-called “Time of Impact Island” (TOI Island).

At a second step, potential collisions in each “Time of Impact Island” are then handled sequentially using a so-called “Contact Solver” (or “Collision Solver”) an algorithm using complex mathematics to determine the “Time of Impact” ordering of each object in the island and its new trajectory. By thinking about it a bit more deeply, will eventually become apparent that solving all the collisions and changing the trajectory of objects can cause inevitably new collisions. To come around this side effect, the whole process of the “Axis-aligned Bounding Box” calculation, the one of the “Time of Impact Island” calculation and the contact solving are repeated for a Programmer-defined standardised arbitrary number of times. This approach to the problem increases the visible stability of the objects, since over-corrections and constant toggling of an object against a surface between colliding and non-colliding can give rise to the so-called “Jitter” problem.

The good news is that the “Time of Impact Island” ordering is generally only needed for simulations rather than 2D platform games. In computer games, “Axis-aligned Bounding Boxes” are calculated to check if a main character or any other object at this respect is about to hit some scenery element with the aim of identifying what is the amount of movement beyond which the result will be for the main character or any other object to find itself in a rather awkward situation (inside a wall or stuck in the ground). This is called “Penetration Resolution”.

The “Speculative Contacts” Collision Detection Technique

This represents the “latest-and-greatest” in Collision Detection techniques. Usage of this technique in the latest computer games has given it a rather prestigious place among all the other techniques currently available. The original intention behind its development was to effectively solve the so-called “Bullet-Through-Paper” problem, present in “Discrete Collision Detection” whereby a fast-moving object can pass completely through a piece of geometry. This becomes possible because in “Discrete Collision Detection” only the initial and final position of the object during each frame is considered and not all of the possible in-between positions that the object would occupy during its movement. For example, if we consider a main character made of a single-pixel, falling at 50 pixels per frame with a 5-pixel tall platform 30 pixels below him, then according to our description no collision will be detected as both the main character’s current position and his position 50 pixels further down do not touch the platform at all. The only way to solve this problem is to examine the in-between positions, as well as the initial and final positions, on a per-frame movement basis. The “Speculative Contacts” Collision Detection technique aims to do exactly this.
A POSSIBLY OPTIMUM COLLISION DETECTION APPROACH

The most convenient way to start with our Collision Detection approach is by defining 8 points in an octagonal shape on the edges of the main character sprite. Specific pairs of these points can be later on selected to test for Collisions depending largely on the player’s direction of movement. The reason why we use 8 points and not any other number of them is because this approach has some very specific advantages over other “obvious” methods like the one that is only using the four corners (4 points for a “Bounding Box”) of the main character sprite, the Collision Detection will be less visually uneven. To further advance this idea, let us consider the situation where the four corners are used. In this case the main character can be seen standing completely off the edge of a platform with only a bottom corner touching it and still not fall. On the other hand, Collisions with ceilings and walls may be detected where none really exists. Therefore, it is much better for us to consider using actual points on the main character itself for a much closer to the optimum result.

Figure 3: A 64×64 Main Character Sprite with eight (8) Collision Points (black spots).

In some form of code the above stated approach can be realised as follows:

(The Array to Hold the Collision Points on the Main Character Sprite)
CollisionPointsArray collisionPoint[8];

(The Eight (8) Collision Detection Points for our 64×64 Main Character Sprite)
CollisionPointsArray points[8] = {
{5, 0}, {15, 0}, //Top of the head
{5, 40}, {15, 40}, //At Feet
{0, 10}, {0, 30}, //At the Left Arm
{20, 10}, {20, 30}}; //At the Right Arm
For (int i = 0; i < 8; i++)
collisionPoint[i] = points[i];

The “Penetration Resolution” Method

As a term “Penetration Resolution” refers to the process of adjusting the main character’s position slightly in order to correct for any Collisions. In general, Collisions will occur in mainly three situations: a) when the main character is resting on the ground level due to the force of Gravity, b) when the main character is walking into walls, and c) when the main character is hitting some sort of ceiling while jumping. In all the Collision Detection arising situations the need is to push/pull the player away from the Collision objects up until they are no longer touching it.

The most primitive way of dealing with the problem is arising out of the fact that 2D imposes on us a massive constraint on how easily we can calculate the “Normal Vector” or “Distance” between two geometry objects. So, at a first instance we can simply wind the main character’s position backwards from the “Current” to the “Previous” position one pixel at a time and re-test with every backward movement until we can certify that there is no longer a Collision occurring. As a rule of thumb, we do not use this method in commercial games.

The “Penetration Resolution” method is an iterative process that must be performed multiple times per frame. This is the case mainly because resolving one Collision can cause another. As a result, all nearby objects must be re-calculated and re-checked until there are no Collisions detected. Now, comes without saying that the more iterations we allow, the more stable the result will be, with the objects involved experiencing less “Jittering” as they are constantly corrected and re-corrected.

With this method we need to know the direction the Collision came from in order to adjust the main character’s speed in that direction to zero, and also to turn off the “Jumping Flag” variable if needed. By means of using the “Collision Points” on the main character sprite, we can now check if the scenery geometry intersects with (or we can think of it as: “if contains”) any of these points, one pair at a time (top pair, bottom pair, left pair and right pair). In case of a Collision been detected, the projected “Movement Vector” is adjusted by one pixel until it no longer collides with the scenery geometry. The “Movement Vector” is set to the adjusted projection when all the work is finally done. At this point, what we actually have is a “Movement Vector” which does not cause any collisions with the object currently being tested.

The “Penetration Resolution” Method on “Jumping” Situations

When treating a “Jumping” situation the main character can’t just continue jumping if hit the side of something, but rather must fall. Otherwise, a main character hitting a wall during a jump will continue trying to travel upwards producing a very unrealistic effect in the end. What we need is a condition so the main character won’t be able to jump anymore while standing still directly next to a wall, in the direction of the wall. Without this condition, jumping upwards and hitting a sloping overhang can cause the main character to spring backwards while still moving upwards.

If a Collision has been detected, we need to first update the main character’s position immediately and then set the movement for the rest of the frame to zero (0 - no movement), then re-iterate to test for new Collisions. In every other case we do nothing. Additionally, if the main character has fallen and hit a ground surface, we reset the “Jumping Flag” variable so the main character can jump again.

The “Bounding Box Optimisation” Approach

As becomes apparent from what we discussed so far, checking every single scenery object against collision with the main character is both pointless and computationally expensive. The simpler approach to the problem of finding out scenery objects in the vicinity of the main character demand the realisation of the so-called “Bounding Box Optimisation”. For “Bounding Box Optimisation” we pre-calculate (that is, before the game starts) the “Bounding Boxes” of every static scenery object (the platforms) and then, on each frame, we compare these with the “Total Bounding Box” of the main character’s Current Position and Desired Position after movement. Any intersects (overlaps) are considered to be nearby and will be passed for “Penetration Resolution”.

We still have to examine the “Bounding Box” of every scenery object, but this time this is in terms of a couple of quick subtractions and overall is a far cheaper operation than testing for intersections with every piece of arbitrarily-shaped scenery geometry. Of course, we can always put the scenery objects in a series of “Buckets” or an “N-tree” in order to isolate those ones we need to test.
THE “SPECULATIVE CONTACTS” APPROACH

All the approaches we discussed so far are doing the job properly but there are still some optimisation issues to be taken into consideration. For example, let us consider a situation at which the main character repeatedly shifts between two adjacent positions at a “floor” scenery level. This may often happen because a Collision repeatedly occurs and is corrected. In situations like this we only need to stop this Collision from happening.

Apart from that, there is also the opposite problem. Sometimes, when the main character jumps off a platform or something of a similar nature may fall right through it (off the top of a thin platform or something of a similar nature below). This is the so-called “Bullet-Through-Paper” problem and happens because “Penetration Resolution” only considers where a particular object starts and finishes in a frame; not any of the theoretical positions it would have occupied in between to move between the two points.

Figure 4: The Bullet-Through-Paper problem.

It is in order to address situations like this that we’ll need to employ the “Speculative Contacts” approach. The “Speculative Contacts” approach mainly tackles the problem from the opposite to “Penetration Resolution” approach, by trying to prevent Collisions before they actually occur. For this approach to work properly the calculation of the distance between the main character and a piece of scenery geometry is needed. If the player’s movement then would cause the scenery object to be passed through, the “Movement Vector” is immediately adjusted so that the main character just reaches the edge of the scenery geometry instead.

For a fully deployed implementation of the approach we need to consider “Time-of-Impact” (TOI) ordering of multiple moving scenery objects and not only “Player vs. Static Scenery Geometry” Collisions. The good news in this respect is that in general, in 2D platform games, “Time-of-Impact” ordering is not usually necessary.

Figure 5: The “Speculative Contacts” Approach resolves the “Bullet-Through-Paper” problem by shortening the main character’s “Movement Vector” such that it just touches the edge of the scenery geometry that would otherwise be passed through.

So, whenever we have to face the restriction of not been allowed to calculate the position between two scenery geometries, we implement the opposite of what we have to implement for the “Penetration Resolution” approach. That is, we start at the main character’s Current Position and advance one unit (Pixel or other) at a time until we encounter a Collision. The thing is, as was the case before, this is a very inefficient way of doing things and we need to employ a partial optimisation to further improve efficiency. For this we cannot work only in the “X-axis” or “Y-axis” direction in isolation as we need to make our way along the path of movement.

First we’ll need a set of variables to store the length of the “Movement Vector” and how far we are along it. For this we re-employ the “Bounding Box Optimisation” with the aim of considering only nearby scenery objects. We need to remember that, after “Penetration Resolution”, the whole process repeats including “Speculative Contacts” where we need to calculate “Bounding Boxes” in every iteration.

At the beginning all are rather similar to “Penetration Resolution”, even though we have to work along the “Movement Vector” in the right direction (rather than the “X-axis” and the “Y-axis” individually), we still test the Collision Points of the main character sprite in pairs according to the direction of movement. If we choose not to do this and rather test all 8 points regardless of “Movement Direction”, we can become stuck in the game world. Performing the necessary calculations by means of “Pythagoras’ Theorem” (the Theorem states that the length of the longest side of a Right-angled triangle is equal to the square root of the length of the other two sides squared) we calculate the expected “X-axis” and “Y-axis” movement, and we get the length of the “Movement Vector” (in pixels, since the “X-axis” and “Y-axis” Movement Distances are also specified in pixels), and that’s all we need. We should continue until either a Collision is found, or we have reached the end of the “Movement Vector” (in which case there is no Collision occurring). Inside a loop, we advance our position along the “Movement Vector” by one unit.

Dealing with the case of a Collision occurring, we backtrack by one unit so that the main character’s movement will land him or her at the edge of the scenery geometry rather than slightly inside it. If there was already a Collision at the starting position (segments would be 0 since no advancement was made), we do nothing as there is no backtracking to do.

Finally, we need to update the main character’s “Movement Vector” for the frame depending on which direction we were currently testing. This is a notable difference from other implementations where we generally need to shorten the vector length, something that actually immediately means shortening both the “X-axis” and “Y-axis” components. However, instead, we can distort the direction of movement (when the ball hits the platform downwards), as its “X-axis” movement is retained so it will still end up moving as far to the right as originally intended rather than stopping dead and it will just be on the platform instead of passing through it. With the constant force of Gravity being applied any left or right movement by the main character is actually a left-down or right-down movement. If we shorten the “Movement Vector” to zero when standing on a platform due to Gravity, we would also need to shorten the “X-axis” “Movement Vector” to zero, meaning that the main character would be permanently stuck in one place and unable to move left or right.

If we try to implement the code realising what we discussed so far and test it we’ll see that it will no longer be possible for the main character to fall through any platform or platform like scenery geometry at high speed, so we have implemented a fully-functioning 2D platform Collision Detection system.

Download "PlaneMissile"

Computer Games Programming

Few Words About SCIENZA

Links I

Links II

Terms