Collision detection for free and smooth movement around a maze

Collision detection is the bane of my life. It’s one of those necessary annoyances that transforms a piece of code in to a game.
Without it your game runs like lightning. With it you have the basis of a challenge to present to your player.

With Castle Adventure I set out to craft something akin to Gauntlet’s free roaming nature. I wanted 8 directions of movement and the ability to slide along a wall until such a time as the player character slipped in to an open door way. It’s just one of those things that makes for a satisfying game experience.
But I ran in to trouble almost immediately with a very restrictive approach to handling collision.

My approach to collision detection has always been to use the much used box model. That is to say that everything that requires collision detecting  operates within a four-sided sprite box. Each of the four corners is tested in turn to see whether it exists within the bounds of the target sprite.

 

collision detection with sprites

Player sprite colliding with a wall tile

In most cases it’s perfectly adequate to register the collision and deal with it. e.g. Collision between monster and player missile. I pretty much don’t care which direction either sprite was travelling in or which side of the sprite got hit. I simply spawn an explosion and register the hit for the purpose of scoring.
But with the player’s sprite it’s a bit different.

I always want the player to press the direction buttons as he sees fit. That is, if he wants to hold down LEFT and DOWN at the same time he should be free to do so. Regardless of the fact that the sprite might only be able to travel in one of those directions. Penalising the player for a basic action is going to ruin the entire experience. Infact poor controls are going to see the player leave without giving the game a fair crack.

My box model of collision applies to the player. Every game tick I hurl every wall tile (32 x 32) at the routine and test all four corners of the player sprite against the four corners of the wall tile. This is EXTREMELY expensive and can half your frame rate if you don’t try to manage it.

I tackle it in two ways.
Firstly if the target wall tile is invisible (i.e. wall.visible = false) then I simply back out of the routine altogether. Wall tiles with door behaviour are set to become invisible once opened.
Second I set a threshold for test based on proximity to the player sprite. In Castle Adventure I currently set a threshold (e.g 64 pixels). If the target wall tile lies beyond that distance from the player sprite in all directions than I once again back out of the routine. The saving in terms of performance is big. Stepping through large arrays is always expensive and should be avoided. Especially when you do it 20+ times a second !

 

Collision detection

Selecting which wall tiles to test for collision based on proximity to player sprite

Once I have a wall tile to test against I set a series of flags.
I use the variable COL and set its TopLeft, TopRight, BottomLeft and BottomRight properties to FALSE before stepping through the WALLTILES array.

var col = { "TopLeft" : false, "TopRight" : false, "BottomLeft" : false, "BottomRight" : false };

The theory is that by the time I’ve tested every wall tile I will have TRUE or FALSE values for all four corners of the player’s sprite. I can then use these values to determin how to control the player. This is where it gets a bit complicated.

The  player object has four directional flags: moveleft, moveup, moveright and movedown. These correspond to each of the four directional controls. e.g. when the player presses the up arrow in Castle Adventure the moveup flag is set.
When determining the direction for the player sprite I simply check which flags are set. e.g. if moveup and move right are set then the player moves north east (direction 1 in my game code based on 0 being north clockwise to 7 being northwest).

 

Sprite directions and corresponding sprite movement properties

So where the player sprite has collided with a wall tile I need to check the direction and which of the four corners was clipped.
Before running this check I store the old x and y co-ordinates of the sprite in oldx and oldy.

So for example – where the player sprite has been travelling south (direction 4) I would expect BottomLeft and / or BottomRight to be set to TRUE following collision detection.
In this case I simply revert player.y back to the stored value.

player.y = player.oldy;

Similarly where the player sprite has been travelling south east (direction 3) I would expect BottomLeft, BottomRight or TopRight to be set to TRUE depending on where the wall was situated in relation to the sprite.
If the wall was directly beneath the player then I would simply set the y value back to the stored y value as in the previous example.
Note: I do not alter the PLAYER.MOVEDOWN value. That is still set to TRUE. I am simply stopping the y value from incrementing.
This is the key to achieving smooth movement.
Essentially the player sprite is sniffing the walls looking for a route south. Every time it sniffs a wall I stop it from going in that direction. But since its MOVEDOWN value is set to TRUE it will keep trying. Sure enough when an opening occurs it jumps at it and smoothly enters the gap without the player having to lift his finger off the down button.

There are situations where all three values are set to true. I test for this scenario explicitly since it forces me to revert both x and y values back to their previous state. In the previous example of the player’s sprite moving south east it’s possible that the sprite would run in to a corner. In this case BottomLeft, BottomRight and TopRight ALL fire and set to TRUE.

There is one final scenario that I have to explain. In order to explain it I should explain how I used to run the collision routine.

Consider this code:

for (var a=0;a<walltiles.length;a++) playercollision(walltiles[a]); // From within the game loop
function playercollision(o)
{
 // code to test player sprite object against the supplied wall tile object (o)...
 // Populate the COL values (TopLeft, TopRight etc).
// Further code to determin what to do in the event of a collision.
};

The problem with the above method is that it takes a wall tile at a time and tests it for collision with the player. Where a couple of the edges of the player sprite return TRUE I’m in luck and can handle the collision correctly. But what if the following were to occur (as illustrated by the image below).

Collision detection

Player sprite straddles two wall tiles

In this scenario the first test against the upper wall tile would return a TRUE for the TopRight of the player sprite but the BottomRight would return FALSE. My code relies upon TopRight and BottomRight being set to TRUE in order to detect a collision with a wall to the right of the player. 3 times out of 4 I will be lucky but suddenly the sprite will stop dead since I am returned a FALSE where I expect a TRUE.

To combat this I change my code slightly.
I set all the COL values to FALSE before iterating through the walltile array in the game loop. I then have the playercollision() function set the COL values as necessary.
By the time the walltile loop has completed I will have an accurate set of values for the four corners of my player sprite.

In the scenario above where the player sprite straddles two wall tiles the first test will set TopRight to TRUE and the second test against the lower wall tile will set BottomRight to TRUE.
I then simply deal with the outcome after the walltile array has been tested in the main game loop.

It’s really not an easy thing to explain so I invite you to examine my code at http://www.wilfscorner.co.uk/sandpit/2/castle.php

Just do the right-click view source thing and look for the routines around function playercollision(o).

If you’ve any questions about my approach here please drop me a line.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Comments

  • Jani Hartikainen  On November 3, 2010 at 8:41 pm

    Your code is such copypasta :D but the game looks and runs nice despite that!

    My code is neat but my games don’t really look so good otherwise :)

    Have you considered using circle-circle collisions for monster-player collisions or such? They are pretty simple math-wise I think.

    • markw1970  On November 3, 2010 at 9:02 pm

      Oh it is :) When the code is stable I’ll condense it and tighten it up a bit. I just like to roll my own code and better still read it ! I’m looking forward to getting down to level design and designing proper sprites :) Thanks for the tip. I’ll take a look.

  • ezmilhouse  On November 3, 2010 at 10:12 pm

    tried it a little differently, basically calculated corner coordinates, then check those against those of obstacles, tried to establish collision events (oncollison, oncollisionout) and collision event handling (over, bump, trigger, vanish), find game demo here: marcfuehnen.com/car/v12

    nice work

    • markw1970  On November 4, 2010 at 9:45 am

      Marc I like your approach. The end result is a very satisfying experience parking a car :-) Which sounds not so cool but the control and “bounce” on collision are very rewarding.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: