How to make a 2d platform game – part 2 collision detection

Figure 4
Submit to StumbleUpon

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

About Paul Firth

A games industry veteran of ten years, seven of which spent at Sony Computer Entertainment Europe, he has had key technical roles on triple-A titles like the Bafta Award Winning Little Big Planet (PSP), 24: The Game (PS2), special effects work on Heavenly Sword (PS3), some in-show graphics on the BBC’s version of Robot Wars, the TV show, as well as a few more obscure projects.   Now joint CEO of Wildbunny, he is able to give himself hiccups simply by coughing.   1NobNQ88UoYePFi5QbibuRJP3TtLhh65Jp
This entry was posted in AS3, Collision Detection, Platform game, Technical and tagged , , , , , , , , , . Bookmark the permalink.

35 Responses to How to make a 2d platform game – part 2 collision detection

  1. Chris DeLeon says:

    My platforming article example that you linked to above is from one of my entries intended for beginning developers, in particular those just beginning to make the leap from programming at all into videogame development concepts. I wholly agree that the 6 points solution isn’t best, for the same reasons stated, but was just minimally functional and minimally complex to illustrate the concept.

    Your approach is certainly more robust!

    That said, when the same simplistic points approach is applied instead to rectangles, it produces the pretty versatile collision behavior used in my Everyone’s Platformer example code. I wrote a follow-up breaking down it’s collision detection, though since it’s mostly just an extension of the points behavior into solid rectangles, most of the space there is dedicated to discussing quad trees, tunneling, and other related concepts. The same engine and collision approach was used for my work on Vision by Proxy: Second Edition, if anyone’s curious to see it in an example other than the Everyone’s Platformer sample content.

    Great write up here, and thanks for linking :D

  2. Rhuno says:

    I think this is awesome and your programmer art is vastly superior to my own. It is hard to find good, full examples on collision and game development in general; nice work! :)

  3. Pingback: How to make a 2d Platform Game – part 3 ladders and AI | Paul's blog@Wildbunny

  4. Pingback: How to make a 2d Platform Game – part 1 | Paul's blog@Wildbunny

  5. Pingback: How to make games | Paul's blog@Wildbunny

  6. Phil says:

    Thanks for the tutorial, it’s pretty good. There is one thing I couldn’t quite figure out and I hope you can to clarify this. You accumulate m_posCorrect to correct for any penetration between a MoveableObject and a tile. If multiple tiles right next to each other produce a collision response then wouldn’t this cause “over correcting” the penetration?

    • Paul Firth says:

      Hi Phil,

      Yes, this would happen if I weren’t filtering out ‘internal edges’ – two tiles right next to each other would generate 2 contacts as you point out, but with internal edges removed I only end up with one. I think :) Its been a while since I wrote that code now.

      You’re welcome to download the free version and see how it performs?

      Cheers, Paul.

      • Phil says:

        Here is an illustration of what I mean: http://i.imgur.com/zM512.png If these contacts are accumulated and added to the position then you push the object up twice. If the object is bigger and collides with more tiles then the problem gets even worse. An internal edge is one that is sideways but I don’t see why there can’t be multiple external edges like in the illustration.

        • Paul Firth says:

          Hi Phil,

          Sure, I understand what you mean – this problem is mitigated by the fact that the objects are not pushed fully out of penetration each frame, rather they are pushed towards being fully out, IIRC by 10%. This is commonly referred to as Baumgarte correction.

          Its not a precise or completely accurate way to deal with penetration but one which works well in practice :)

          Cheers, Paul.

  7. Phil says:

    Thanks that makes sense. I couldn’t find where it only applies a fraction (to me it still looks like the code uses the full penetration). At least I understand what you’re saying and can try that out as a possible solution.

    • Paul Firth says:

      You know what, looking at the code I’m not actually doing what I described in this particular example – that’s probably a mistake on my part. I guess the question is: why doesn’t this manifest itself visually as the player moves between tiles? Not sure I know the answer – its possible that penetration is so little in the game that this is never a problem – speculative contacts are very good for reducing penetration to a minimum :)

  8. Will says:

    Hi Paul,

    Great article. I have ported your collision code to Unity, and it works great except for one edge case. If an object hits a corner just right, a rather large correction velocity is applied, which causes the object to pop. Have you seen this kind of thing happen before? I’d be happy to upload my project somewhere if you’d like to see the code.

    Thanks!

    • Paul Firth says:

      Hi will,

      Iirc, the collision resolution should never introduce velocity, only remove it, so it should be quite easy to trap this case and debug where its going wrong. Possible things to look for would be incorrect normals or badly computed input velocities. I’ve not see this case myself – is it definitely velocity and not position correction?

      Cheers, Paul.

      • Will says:

        After looking at it a little more, it looks like the normal is to blame. If the character doesn’t have a square AABB, and hits a corner just right or is sliding along a wall and comes to a corner, the normal is incorrect. Here’s a video of what I’m seeing:

        Collision Problem

        Square AABBs work, because the major axis doesn’t change until the character is above the tile.

        • Paul Firth says:

          Hi Will,

          Yes, you’re correct there is a bug in my code. Please try this version:

          static public function AabbVsAabbInternal( delta:Vector2, aabbCentre:Vector2, aabbHalfExtents:Vector2, point:Vector2, outContact:Contact ):Boolean
          {
          var di:Vector2 = delta.m_Abs.Sub( aabbHalfExtents );
          var mc:Number = di.m_MaxComp;
          var clampedDi:Vector2 = di.Max( Constants.kZeroVector );
          var clampedDiLen:Number = clampedDi.m_Len;

          if ( mc<=clampedDiLen )
          {
          // interior distance

          // build and push
          outContact.Initialise( delta.m_MajorAxis.m_Neg, mc, point );
          }
          else
          {
          // exterior distance
          var clampedDelta:Vector2 = delta.Min( aabbHalfExtents );
          var deltaD:Vector2 = delta.Sub( clampedDelta );

          // build and push
          outContact.Initialise( deltaD.m_Unit.m_Neg, clampedDiLen, point );
          }

          return true;
          }

          I’ve tested that with a non-square aabb and it seems to fix the problem.

          Hope that helps!

          Cheers, Paul.

  9. Ivan says:

    Hey Paul,
    Great article as usual. I’m programming a platforming engine in Lua and have encountered similar issues regarding the ‘inside edges’ of AABBs. I think one simple solution is to use line shapes for platforms instead of AABBs. Line shapes don’t have inside edges and can easily be modified to support inclined and one-sided (jump-trough) platforms. However, I’ve hit programmer’s block and can’t figure out how to calculate the magnitude of the penetration vector between an AABB and a line.

    function testLineRect(a, b)
    -- line vector
    local dx, dy = a.x2 - a.x, a.y2 - a.y
    -- line halflength vector
    local hdx, hdy = dx/2, dy/2
    -- line midpoint
    local mx, my = a.x + hdx, a.y + hdy
    -- translate midpoint to rect origin
    mx, my = mx - b.x, my - b.y

    -- separating axes tests
    local ahdx = abs(hdx)
    if abs(mx) > b.hw + ahdx then
    return
    end
    local ahdy = abs(hdy)
    if abs(my) > b.hh + ahdy then
    return
    end

    -- wedge product test (cross product in 2D)
    local cross1 = b.hw*ahdy + b.hh*ahdx
    local cross2 = abs(mx*hdy - my*hdx)
    if cross2 > cross1 then
    return
    end

    -- collision normal is the line rotated by 90 degrees
    local d = sqrt(dx*dx + dy*dy)
    local nx, ny = dy/d, -dx/d

    -- todo: figure out the penetration depth
    local pen = ???

    return nx, ny, pen
    end

    Notice that rects are represented as a center position (b.x, b.y) with half-width/heights (b.hw, b.hh). Any tips of figuring out what the penetration depth would be? I have a feeling there’s a simpler way then projecting all 4 corners of the rect onto the line.
    Thanks in advance!

    • Paul Firth says:

      Hi there,

      Just treat your line as if it were an AABB with zero height; if your AABB vs AABB code is good enough, it should be able to handle that case :)

      Cheers, Paul.

  10. Fer says:

    Hi!, great tutorial Paul. but Could you please tell me what m_x and m_y stand for?
    I ca’t seem to figure it out!.

  11. Cord Rehn says:

    Hey Paul- great series, really appreciate it! I have converted your free, barebones example to Java using libgdx for rendering/input. It works beautifully minus one thing:

    When jumping, where jump adds to y-velocity some amount, it works as expected coming from a stand-still. However if you hold the jump, the initial jump is fine, but the jumps after landing the first time are inconsistent and vary in height causing a ‘bouncing’ effect.

    Upon closer inspection, on_ground flag is true (which is the condition to allow another jump to happen) even though the Y-velocity still is negative number (which changes each time). I takeit the accumulation penetration ‘pos_correct’ vector should also be a jump condition ?

    Let me know, Thanks Paul!

    • Paul Firth says:

      Hi Cord,

      Can you reproduce the same behaviour in the original version?

      Have you got a varying time-step? That could well cause varying jump heights due to numerical integration errors. On Little big planet, we actually had to fix the time-step completely! And IIRC my flash examples all have a fixed time-step.

      Cheers, Paul.

      • Cord Rehn says:

        I was using a variable timestep, I just tried it with a fixed time step and the problem persists.

        Uh oh. Just tested it and you may reproduce this problem in all of the platform games you have live on your site! :C

        http://www.wildbunny.co.uk/blog/how-to-make-a-platform-game-source-code-options/

        We both have a bug to fix my friend.

        Your code doesn’t keep polling for ‘jump’ key, so you need to mash the ‘up’ arrow. Try to time it right when you land. You will notice if you chain your jumps in perfect sequence, the sequential jumps will have a lower height. To make this defect more noticeable, increase gravity and poll the ‘up’ arrow each update.

        To track the problem, set a breakpoint in your jump routine just before adding the jump-velocity and see if your velocity.m_y is 0 (ideal) or a negative value (< 0) which would effectively reduce the jump height. My gravity is -50 units with a 20 unit instantaneous jump height and I am getting negative values ranging from -5 to -20 meaning I am losing between 5% to 40% of my jump height.

        It would seem using 'on_Ground' as a condition for jumping isn't sufficient. I will keep you updated on my progress Paul, let me know if you find anything out!

        • Cord Rehn says:

          Just as a follow up, I found a solution to this problem. It involves adding 1 more constraint to your character’s jump ability, the constraints I am using currently are:

          if (!isDead()) // not dead
          if (!isJumping()) // not already jumping
          if (isOnGround()) // on ground
          if (!isJustLanded()) // not if we just landed. don’t allow jumping yet so velocity can zero out. fixes an inconsistent jump height bug

  12. Me says:

    Hello,

    Please can I use your “enemies” seen in this game when I create my platform game?
    Sorry for my english.

  13. Collis says:

    Hi, Im trying to solve my problem with collision,
    looking for help on google and I found your site. Sorry for wasting your time, but please can you help?

    I use collision code from a book, the code is telling me from which side collision is occured, for example, if characters are on top of a blocks its ‘bottomCollision’,
    it will prevent them from falling down.
    The bad thing is that when I have jumping characters, code usually works fine, but if character jump exactly where the 2 blocks are connected, for some reason Right or Left collision is occured, not Bottom. Im pretty sure thats because character hit top-left or top-right corner. But if character walking (not jumping) on same blocks, right or left collision is never occured.
    Do you have any idea how to fix this?

    • Paul Firth says:

      Sorry, its almost impossible to tell you the answer to that question without seeing the source code of the routine you’re using.

      The only real way to fix this is to debug it – make a special level with only a couple of blocks, add some print output to your collision code to indicate what collision case is happening and then walk/jump around on the blocks and see what happens.

      That way you will be able to tell what the code *thinks* is happening and you should be able to see the problem more clearly.

      • Collis says:

        I did all that things, when collision is occured I stop characters moving, so they always stop on the same place where their down-right or down-left corner hit top-left or top-right corner of the blocks. Insted of bottom collision, right or left collision are occured. Thats what I see in output.

  14. Collis says:

    I forgot tell you it is checking for collision between bounding boxes.

  15. Jim says:

    What is happening in Scalar.Sign() with the function get m_MajorAxis?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing