Submit to StumbleUpon Share

Hello and welcome back to my blog!

In this series of articles, I'm talking about the technology behind a platform game.

If you missed part 1 you can check it out here.

The language is actionscript 3.0, but the techniques are applicable to all languages.

In this particular article I'm going to talk about the physics, collision detection and AI aspects of the game.

The Game

There is a playable version at the bottom of the post, for those with Flash support in browser.

Class hierarchy

It makes sense at this point to talk about the class hierarchy I've used in the game, to represent everything which moves:

Figure 1

Figure 1 shows the class hierarchy - at the very top sits MoveableObject, which is where all the generic collision detection and response gets done; I say generic because the player does specialised work to handle things like ladders etc.

Each level in the hierarchy represents separate functionality; for example, Character contains the AnimationController which handles playing the various different animations for each character, SimpleEnemy represents a certain class of enemy character which does no collision detection with the world, and obeys special position markers when it encounters them. The Diamond pickup is a simple object which has no AI, and just collides with the world, so it inherits from the base class, since that's all the functionality it needs.

This may seem like a lot of extra complexity for such a simple game, but it really makes adding new enemy types very easy indeed, and simplifies the debugging process because there is so much code shared between each object.

If I had to give one piece of advice from 10 years of game development it would be this: avoid code duplication at all costs. It leads to slow development and bug city whereby you fix a bug in one location, and then forget to fix it in the other duplicated locations.

MoveableObject has certain properties which it requires be implemented by any class which inherits from it:

  • m_HasWorldCollision - whether full collision detection should be performed
  • m_ApplyGravity - whether gravity should be applied
  • m_ApplyFriction - whether the world collision should apply friction

That way, and child class can chose what elements of collision detection it wants enabled.

Consider the following snippet from the Skeleton character:

package Code.Characters
{
	import Code.Maths.Vector2;
 
	public class Skeleton extends Enemy
	{
		...
 
		/// <summary>
		/// Apply collision detection only when not hurt
		/// </summary>
		public override function get m_HasWorldCollision( ):Boolean
		{
			return !IsHurt();
		}
 
		/// <summary>
		/// Apply gravity only when not hurt
		/// </summary>
		protected override function get m_ApplyGravity( ):Boolean
		{
			return !IsHurt();
		}
 
		/// <summary>
		/// Apply friction only when not hurt
		/// </summary>
		protected override function get m_ApplyFriction( ):Boolean
		{
			return !IsHurt();
		}
 
		...
	}
}

Its been set up to only do collision detection, apply gravity or friction when its not been 'hurt' (i.e punched by the player), this allows it to have the same behaviour as all other creatures when the player kills them.

Physics

Ok, so lets talk about the simple physics inside MoveableObject. Every MoveableObject has a position, a velocity and a radius.

This radius comes from the Flash IDE - an object instance called 'm_flaCollision' is checked for in the constructor of MoveableObject, and is a requirement, so the physics engine knows what the object's radius is. This radius is then turned into an AABB of size radius x radius, because the collision shapes are all AABBs.

Position is the position of the object in world space (i.e. pixels) and velocity is pixels/second. The update loop for MoveableObject looks like this:

package Code.Physics
{
	import flash.display.*;
	import Code.Maths.Vector2;
	import Code.*;
	import Code.System.*;
	import Code.Geometry.*;
	import Code.Graphics.*;
	import Code.Level.*;
 
	public class MoveableObject extends MovieClip implements IAABB, ICircle
	{
		...
 
		/// <summary>
		/// Apply gravity, do collision and integrate position
		/// </summary>	
		public function Update( dt:Number ):void
		{
			if ( m_ApplyGravity )
			{
				m_vel.AddYTo( Constants.kGravity );
 
				// clamp max speed
				m_vel.m_y = Math.min( m_vel.m_y, Constants.kMaxSpeed*2 );
			}
 
			if ( m_HasWorldCollision )
			{
				// do complex world collision
				Collision( dt );
			}
 
			// integrate position
			m_pos.MulAddScalarTo( m_vel.Add(m_posCorrect), dt );
 
			// force the setter to act
			m_Pos = m_pos;
			m_posCorrect.Clear( );
		}
 
		...
	}
}

This is the part which actually calls out to the various features of MoveableObject and depends on the child class's implementation of those properties I discussed earlier. Child classes call out to this function from their own Update() which contains their specific logic.

This is just your basic physics set-up:

  • Add gravity
  • Do collision detection
  • Integrate position

This is basically all we need for the game as it stands.

Collision detection

When writing the demo above, I did a lot of research on collision detection techniques for platform games because I knew that back in the 1980s when these games first came out, there were no floating point units and collision detection research was in its infancy, so there must be some really easy tricks you can do to get a great result nice and simply.

Update: I wish I'd found this article before I started writing this, its about how the original developers of M.C.Kids on the SNES handled tile based collision detection. In summary its kind of similar to the article I reference below, in that it used collision points, only it goes into more detail about all the ins and outs of the technique.

This article contains the most detailed explanation that I could find, but on implementing it I found there were a few things I didn't like; the author advocates using a number of predefined points around the player to help detect collisions and to judge what to do next, like this:

Points around player

The author writes:

If the point we check on top goes inside a solid block, we move the player downward so that the top point is just below the block it bumped into. If either right point goes inside a solid block, we move the player left until the offending point is just left of the block it bumped into, and so on...

Another benefit of detecting player collision using six points in that hexagon configuration is that if the player is jumping horizontally and the feet hit a corner, the player is automatically bumped up onto the surface; if the player falling vertically hits a corner off-center, or steps off a ledge, the player slides off away from the wall. (Try this! It feels much better than it would if the player behaved as a boxy rectangle.)

However, I found that the last part he mentions about the player being automatically bumped onto the surface was very jarring and often left me wondering what had happened while playing the game. I also found that it didn't help me when the player was moving quickly and became embedded inside a block, because with all points inside the block, there was no clearly correct way to resolve. Also, the amount of code I found I needed was getting excessive so I decided to discard this method - maybe it would have been better if my player character was taller like in his example.

A new way and tiles as a broad-phase

Obviously I needed a new way, but first lets talk about the tile coordinate system and how it makes collision detection nice and easy.

Figure 2

Consider Figure 2 in which the tile coordinates have been numbered 0-6 in the X axis, and 0-5 in the Y. This shows a typical scenario where the player character (shown in red) is jumping up and will hit the green platform at some point between the current frame and the next frame (the player's velocity is shown as the arrow). In order for the collision system to know which tiles need checking against the player, its a simple matter to enclose the player's range of motion within an axis aligned bounding box, or AABB.

Figure 3

Figure 3 shows this bounding box overlaid on the scene in blue. If we take that bounding box and highlight every tile which intersects with it, we now know which tiles we need to consider for collision detection against the player.

Figure 4

Figure 4 shows the relevant tiles highlighted in yellow.

Because there is a direct 1->1 mapping between world coordinates and tile coordinates, it becomes incredibly easy to get access to the tiles in order to perform fine grained collision detection against. This is in essence what a broad-phase collision detection system does, and its refreshing to see it arise naturally as a direct consequence of using a tile engine in the first place.

The new way

Because we don't want the player (or any other fast moving object) passing though platforms if they move too quickly, the fine grained collision detection system, or narrow phase, must be good enough to prevent this from happening.

I'm going to use a technique I first talked about a while back, called Speculative Contacts. Don't worry if it sounds horribily complex, its actually rather simple.

All it requires to work is a function which can return the distance between any two objects.

The collision shape

Before I go into the details, its important that I talk about how the choice of collision shape will affect the feel of the game. I started out with a circle to represent moving objects, but I soon realised this wasn't going to work.

Figure 5

The reason is obvious looking at Figure 5; circles tend to roll smoothly off the edges of objects when placed right on them, which is exactly what you don't want happening when you're lining yourself up for a jump.

Figure 6

A better choice is the AABB, which naturally cannot rotate and therefore will allow objects to perch right on the edge of platforms without falling off them, as shown in Figure 6.

Distance function

In order to implement Speculative Contacts in this case, we need a distance function which will give us distance between two AABBs.

In order to achieve this we turn to the a technique from the Minkowski Difference. If we shrink one AABB down to a point, and grow the other one by the extents (width and height) of the first, the problem becomes one of finding the distance between the point and the new AABB.

Figure 7

Figure 7: In order to find the distance d, between AABBs A and B...

Figure 8

Figure 8: We shrink B down to a point and expand A by the extents of B, then we can use a simple distance from AABB to point function.

Distance from AABB to point

We actually only need the closest distance in each axis for our purposes, so we're ignoring the case where the corner of the AABB is the closest to the point.

Figure 9

Figure 9: To find the distance between AABB A and point B we calculate the vector from A->B, D and then take the Major Axis of this vector. That is, the signed, unit length vector in which the only coordinate filled in represents the largest coordinate of the original vector.

/// <summary>
/// Get the largest coordinate and return a signed, unit vector containing only that coordinate
/// </summary>	
public function get m_MajorAxis( ):Vector2
{
	if ( Math.abs( m_x )>Math.abs( m_y ) )
	{
		return new Vector2( Scalar.Sign(m_x), 0 );
	}
	else 
	{
		return new Vector2( 0, Scalar.Sign(m_y) );
	}
}

Figure 10

Figure 10: The Major Axis has now become the plane normal for our collision. We can calculate the position of the plane by scaling this normal by the half extents of A and adding on the position of A in world space). The distance d, from point B to this new plane is the final distance between point and AABB, and thus the distance between two AABBs.

Speculative Contacts

Now we have all the tools we need to get this technique working!

Figure 4

Looking back at Figure 4 again, all we have to do now is to query the map to see if any of those tiles highlighted in yellow are collidable and if so, we must calculate the distance to each one and the normal as we did above.

package Code.Physics
{
	import flash.display.*;
	import Code.Maths.Vector2;
	import Code.*;
	import Code.System.*;
	import Code.Geometry.*;
	import Code.Graphics.*;
	import Code.Level.*;
 
 
	public class MoveableObject extends MovieClip implements IAABB, ICircle
	{
		...
 
		/// <summary>
		/// Do collision detection and response for this object
		/// </summary>	
		protected function Collision( dt:Number ):void
		{
			// where are we predicted to be next frame?
			var predictedPos:Vector2 = Platformer.m_gTempVectorPool.AllocateClone( m_pos ).MulAddScalarTo( m_vel, dt );
 
			// find min/max
			var min:Vector2 = m_pos.Min( predictedPos );
			var max:Vector2 = m_pos.Max( predictedPos );
 
			// extend by radius
			min.SubFrom( m_halfExtents );
			max.AddTo( m_halfExtents );
 
			// extend a bit more - this helps when player is very close to boundary of one map cell
			// but not intersecting the next one and is up a ladder
			min.SubFrom( Constants.kExpand );
			max.AddTo( Constants.kExpand );
 
			PreCollisionCode( );
 
			m_map.DoActionToTilesWithinAabb( min, max, InnerCollide, dt );
 
			PostCollisionCode( );
		}
 
		/// <summary>
		/// Inner collision response code
		/// </summary>	
		protected function InnerCollide(tileAabb:AABB, tileType:int, dt:Number, i:int, j:int ):void
		{
			// is it collidable?
			if ( Map.IsTileObstacle( tileType ) )
			{
				// standard collision responce
				var collided:Boolean = Collide.AabbVsAabb( this, tileAabb, m_contact, i, j, m_map );
				if ( collided )
				{
					CollisionResponse( m_contact.m_normal, m_contact.m_dist, dt );
				}
			}
			else if ( Map.IsJumpThroughPlatform( tileType ) || Map.IsTileLadderTop(tileType) )
			{
				// these type of platforms are handled separately since you can jump through them
				collided = Collide.AabbVsAabbTopPlane( this, tileAabb, m_contact );
				if ( collided )
				{
					CollisionResponse( m_contact.m_normal, m_contact.m_dist, dt );
				}
			}
		}
 
 
 
		...
	}
}

The above snippet shows the relevant code in the MoveabeObject class. The function Collision is the entry point.

package Code.Level
{
	import Code.Geometry.AABB;
	import Code.System.*;
	import Code.Maths.Vector2;
	import Code.*;
 
	public class Map
	{
		...
 
		/// <summary>
		/// Call out to the action for each tile within the given world space bounds
		/// </summary>
		public function DoActionToTilesWithinAabb( min:Vector2, max:Vector2, action:Function, dt:Number ):void
		{
			// round down
			var minI:int = WorldCoordsToTileX(min.m_x);
			var minJ:int = WorldCoordsToTileY(min.m_y);
 
			// round up
			var maxI:int = WorldCoordsToTileX(max.m_x+0.5);
			var maxJ:int = WorldCoordsToTileY(max.m_y+0.5);
 
			for ( var i:int = minI; i<=maxI; i++ )
			{
				for ( var j:int = minJ; j<=maxJ; j++ )
				{
					// generate aabb for this tile
					FillInTileAabb( i, j, m_aabbTemp );
 
					// call on the mid-ground map (ladders and special objects)
					action( m_aabbTemp, GetMidgroundTile( i, j ), dt, i, j );
				}
			}
 
			for ( i = minI; i<=maxI; i++ )
			{
				for ( j = minJ; j<=maxJ; j++ )
				{
					// generate aabb for this tile
					FillInTileAabb( i, j, m_aabbTemp );
 
					// call the delegate on the main collision map
					action( m_aabbTemp, GetTile( i, j ), dt, i, j );
				}
			}
		}
 
		...
	}
}

The above snippet shows the code which actually does the looping over the tiles in the map shown in Figure 4. You can see that I do two loops, one for the mid-ground tiles and one for the foreground. This is primarily because of ladders which are currently mapped in the mid-ground layer. I would like to explore mapping them solely in foreground in a future version, though as it would make the code smaller.

The interesting thing about Speculative Contacts is that they do no work if they're not required to - so, for all the yellow tiles in Figure 4 we calculate the distance to each one and the normal at that point, but the function CollisionResponse doesn't do anything unless the following condition is true:

var nv:Number = m_vel.Dot( normal ) + separation/dt;
if (nv < 0)
{
    // do something
}

What this is saying is: if the projection of the velocity of the object onto the contact normal (i.e. the velocity in the normal direction) is less than the closest distance between the objects (divided by the timestep, to convert to the same units), then do nothing. I.e. if the objects can not touch between this frame and next, do nothing.

Figure 11

Figure 11 show this in diagram form, A is heading towards B and the projected velocity is shown (v.n) but is shorter than the distance between objects d and so no collision is possible.

There is one important caveat to mention, in that if the objects are moving fast enough, ghost collisions are possible - whereby one object will appear to hit an object that it shouldn't have. This occurs because the CollisionResponse code only knows about the infinite plane of the collision point and not the actual geometry (for performance reasons), so a fast moving object will sometimes hit the empty space next to the surface of the object rather than passing through. However, this is not a noticeable artefact in the game shown on this page, particularly because the maximum speed of all objects is clamped.

Internal edges

One of the problems that a lot of collision detection systems face is that of internal edges and unfortunately, this game is no different.

Figure 12

In Figure 12, the red ball will be judged for collision against the blue block, and the distance function will return the unit vector N as the closest direction, this is correct in isolation, but considering there are other blocks on either side and this is in fact one continuous surface, problems arise. If nothing is done to prevent this, the player will get stuck on the gap between blocks and will even be able to stand the gaps between vertical blocks.

Player stands on the gap between blocks

Solution

To prevent this from happening, I have some special code in the collision detection system which checks for internal edges.

package Code.Geometry
{
	import Code.System.*;
	import Code.Maths.*;
	import Code.Geometry.*;
	import Code.Characters.Character;
	import Code.Level.*;
	import Code.eTileTypes;
	import Code.Platformer;
	import Code.Constants;
 
	public class Collide
	{
		/// <summary>
		/// Helper function which checks for internal edges
		/// </summary>	
		static private function IsInternalCollision( tileI:int, tileJ:int, normal:Vector2, map:Map ):Boolean
		{
			var nextTileI:int = tileI+normal.m_x;
			var nextTileJ:int = tileJ+normal.m_y;
 
			var currentTile:uint = map.GetTile( tileI, tileJ );
			var nextTile:uint = map.GetTile( nextTileI, nextTileJ );
 
			var internalEdge:Boolean = Map.IsTileObstacle(nextTile);
 
			return internalEdge;
		}
 
		...
	}
}

What this does is to simply check the map to see if there is another collide-able tile 'next to' the current one. 'Next to' is defined as one tile along from the current one in the direction of the collision normal. If there is a tile there which is an obstacle, this collision is marked as an internal edge and the system discards it.

Going back to Figure 12, the block which is checked is the one pointed to by the normal, this is a collide-able block and so the collision is discarded correctly.

Jump-through platforms

Some types of platform game are built of completely solid platforms which you cannot jump through, but others like The Newzealand Story and Rainbow Islands are built entirely of platforms that the player can jump through.

To make this game engine as flexible as possible I wanted to support both.

In order to achieve this I needed a distance function which would give me the distance between an point and just the top plane of another (remember we shrunk down one AABB to a point and grew the other). Even still, I only want to consider colliding with this if the moving object was sufficiently close to the top plane of the AABB - if not, the collision is discarded.

Figure 14

Figure 14 shows jump-through platform B and movable object A, which is d distance to the top plane of B and N is the major axis.

There are two collision acceptance conditions on top of the regular AABB vs AABB code.

  • If the major axis is pointing up, i.e. this is a ground platform
  • If the distance of the moving object to the top of the platform is greater than some negative tolerance

If these conditions are satisfied then the collision is accepted. If not, its rejected. The negative tolerance is to handle the transition between being just under the top of the platform and being on it. Its negative because when the moving object is below the platform, the distance is always negative; it grows less and less negative as the object moves up until its 0 right on the platform, then it becomes positive again. This tolerance is shown as the blue bar in Figure 14.

Figure 15

Figure 15 shows one discarded case, where the moving object is too far below the blue bar of tolerance.

Collision Response

The collision response at work here is just to remove the normal velocity of the moving object completely upon collision (and also correct for any penetration which occurs). This means objects do not bounce, but for this game, that is an acceptable compromise.

package Code.Physics
{
	import flash.display.*;
	import Code.Maths.Vector2;
	import Code.*;
	import Code.System.*;
	import Code.Geometry.*;
	import Code.Graphics.*;
	import Code.Level.*;
 
 
	public class MoveableObject extends MovieClip implements IAABB, ICircle
	{
		...
 
		/// <summary>
		/// Collision Reponse - remove normal velocity
		/// </summary>	
		protected function CollisionResponse( normal:Vector2, dist:Number, dt:Number ):void
		{
			// get the separation and penetration separately, this is to stop pentration 
			// from causing the objects to ping apart
			var separation:Number = Math.max( dist, 0 );
			var penetration:Number = Math.min( dist, 0 );
 
			// compute relative normal velocity require to be object to an exact stop at the surface
			var nv:Number = m_vel.Dot( normal ) + separation/dt;
 
			// accumulate the penetration correction, this is applied in Update() and ensures
			// we don't add any energy to the system
			m_posCorrect.SubFrom( normal.MulScalar( penetration/dt ) );
 
			if ( nv<0 )
			{
				// remove normal velocity
				m_vel.SubFrom( normal.MulScalar( nv ) );
 
				// is this some ground?
				if ( normal.m_y<0 )
				{
					m_onGround = true;
 
					// friction
					if ( m_ApplyFriction )
					{
						// get the tanget from the normal (perp vector)
						var tangent:Vector2 = normal.m_Perp;
 
						// compute the tangential velocity, scale by friction
						var tv:Number = m_vel.Dot( tangent )*kGroundFriction;
 
						// subtract that from the main velocity
						m_vel.SubFrom( tangent.MulScalar( tv ) );
					}
 
					if (!m_onGroundLast)
					{
						// this transition occurs when this object 'lands' on the ground
						LandingTransition( );
					} 
				}
			}
		}
 
		...
	}
}

The first few lines compute the separation and penetration (positive or negative components of the distance between objects)

// get the separation and penetration separately, this is to stop pentration 
// from causing the objects to ping apart
var separation:Number = Math.max( dist, 0 );
var penetration:Number = Math.min( dist, 0 );

Then, I compute the relative normal velocity and accumulate the position correction vector which handles penetration resolution:

// compute relative normal velocity require to be object to an exact stop at the surface
var nv:Number = m_vel.Dot( normal ) + separation/dt;
 
// accumulate the penetration correction, this is applied in Update() and ensures
// we don't add any energy to the system
m_posCorrect.SubFrom( normal.MulScalar( penetration/dt ) );

If the normal velocity is less than 0, i.e the objects will touch between this frame and next, remove the normal velocity from the moving object:

if ( nv<0 )
{
	// remove normal velocity
	m_vel.SubFrom( normal.MulScalar( nv ) );

If this is a piece of ground we're going to collide with, record that fact, and then if we need to apply friction, do so:

m_onGround = true;
 
// friction
if ( m_ApplyFriction )
{
	// get the tanget from the normal (perp vector)
	var tangent:Vector2 = normal.m_Perp;
 
	// compute the tangential velocity, scale by friction
	var tv:Number = m_vel.Dot( tangent )*kGroundFriction;
 
	// subtract that from the main velocity
	m_vel.SubFrom( tangent.MulScalar( tv ) );
}

If we weren't recorded as being on the ground in the last collision, then call out to some code which handles landing on the ground (this is user definable code):

if (!m_onGroundLast)
{
	// this transition occurs when this object 'lands' on the ground
	LandingTransition( );
}

And that's it! The only slightly hairy part is the friction calculation, but even that is relatively simple - it just gets the unit length vector perpendicular to the normal (i.e. the sliding vector), calculates the object's velocity in the sliding direction, scales that down by some friction coefficient and then subtracts that from the total velocity.

Figure 13

Figure 13 shows the computation of the tangential velocity; if you were to remove this tangential velocity from the full velocity you would have infinite friction.

If you would like more in-depth details of the collision response code, I suggest you read Physics Engines For Dummies, which covers this in great detail.

End of part 2

Wow, I thought I would have space to talk about the AI in this article, but obviously not! There was an unexpectedly large amount of collision detection to discuss. Ok, so next time I will definitely talk more about the AI and the software engineering behind it all.

As ever, if you want, you can buy the source-code for the entire game (or even try a version for free), including all the assets and levels you see above. It will require Adobe Flash CS4+, the Adobe Flex Compiler 4.0+ and either Amethyst, or Flash Develop to get it to build. And you'll want Mappy or some alternative in order to create your own levels!

Following on from feedback from the Angry Birds article, I've included a Flash Develop project as well as an Amethyst project inside the .zip file, to help you get started more quickly, no matter which development environment you have.

You are free to use it for whatever purposes you see fit, even for commercial games or in multiple projects, the only thing I ask is that you don't spread/redistribute the source-code around. Please note that you will need some programming and design skills in order to make the best use of this!


Click the game to give it focus... Apologies for the programmer art, and my level design (not my best qualities!)

Go to the source-code option page to choose the version you'd like - from completely free to the full version!

Subscribers can access the source here

Until next time, Have fun!

Cheers, Paul.

Continue reading in part 3

Submit to StumbleUpon Share