Tutorial: Per Pixel Collision

In this tutorial we will take a look at implementing per pixel collision detection. Resolving collisions at the pixel level offers more precision than traditional bounding box methods and allows for more advanced interactions. In this example, we'll be using it to move our character over some hilly terrain. If you want to peek ahead at the end result, check out the demo here.

Take a look at the screenshot below from Super Mario Bros. on the NES. You'll notice in many older games, the world is constructed of blocks or squares. This worked nicely for bounding box collisions because well, every shape is a box! The nice thing about using boxes for collisions is that its fast and efficient. For many games, the box collisions works just fine, but if you want more precision or flowing terrain, then per pixel collision is a solid option.

smb1

First, what exactly is per pixel collision anyway? It is the process of looking at individual pixels within two images and checking to see if they overlap. It is helpful because it allows you to ignore collisions with pixels that don't meet a certain criteria. For our purposes, pixels with a zero alpha value will be ignored as they aren't visible to the user.

Let's take a look at a simple example below. The left image shows what a bounding box collision may look like. Note that the game would register a hit here because the projectile has made contact with Mega Man's collision box. However, as we can see, it hasn't actually made contact with the character. With pixel level collision detection, we would know that the hit hasn't occurred yet. The middle image shows that with per pixel detection, we do not have a hit. The image on the right shows a hit using per pixel collision. With per pixel collision, you can check individual pixels and only register a hit if opaque pixels are overlapping

Bounding Box Hit

Per pixel, no hit

Per pixel hit

Now that we have a better idea of what we're talking about let's get down to business and see how to go about implementing it. This tutorial was written with Haxe and OpenFL using the FlashDevelop IDE. The programming language is very similar to ActionScript 3.0 (which is awesome) and it publishes to nearly every platform you can imagine. Even if you aren't using Haxe for your own project, the concepts presented here may give you an idea of how to implement per pixel detection in your chosen language.

Let's begin with a new project and the default Main.hx file as shown below.

package;

class Main extends Sprite {

    public function new() {
        super();
    }
}

Go ahead and check your project.xml file and make sure it looks similar to what's shown below. Note I've set the game size to 640x480.

<?xml version="1.0" encoding="utf-8"?>
<project>
	
  <meta title="PerPixelTest" package="com.sample.perpixeltest" version="1.0.0" company="Name" />
  <app main="Main" path="Export" file="PerPixelTest" />
	
  <source path="Source" />
	
  <haxelib name="openfl" />
	
  <assets path="Assets" rename="assets" />
	
  <window width="640" height="480" fps="60" />
	
</project>

Next we'll add some import statements above the class declaration. These are all the imports we're going to need for this project.

package;

import openfl.display.Bitmap;
import openfl.display.BitmapData;
import openfl.display.Sprite;
import openfl.Assets;
import openfl.events.Event;
import openfl.events.KeyboardEvent;
import openfl.geom.Point;
import flash.Lib;

class Main extends Sprite {

    public function new() {
        super();
    }
}

Now let's add some variables to our class. For this example, we're going to need a couple of bitmaps; one for the player character and one for the environment. We're going to use a Point object to store our player's x and y velocity, and we'll have three boolean values to help with movement. Lastly, we'll have three constants. One for the player's speed, one for the player's jump power and another for gravity. Note that we use all caps for our constant names as haxe doesn't officially support constants. Go ahead and add these variables as shown below.

package;

import openfl.display.Bitmap;
import openfl.display.BitmapData;
import openfl.display.Sprite;
import openfl.Assets;
import openfl.events.Event;
import openfl.events.KeyboardEvent;
import openfl.geom.Point;
import flash.Lib;

class Main extends Sprite {

    private var SPEED:Int = 8;
    private var JUMP_POWER:Int = 45;
    private var GRAVITY:Int = 10;
	
    private var _ball:Bitmap;	// player
    private var _bg:Bitmap;  // environment / terrain
    private var _velocity:Point;
    private var _moveLeft:Bool;
    private var _moveRight:Bool;
    private var _isJumping:Bool;

    public function new() {
        super();
    }
}

Now that we've got all the variables and imports we need, let's get things set up in the new function. We'll add our code just below the call to the super() method.

public function new () {
		
    super ();

    stage.color = 0x33bbff;
    _moveLeft = false;
    _moveRight = false;
    _isJumping = true;
		
    var bData:BitmapData = Assets.getBitmapData( "assets/bg.png" );
    _bg = new Bitmap( bData );
		
    bData = Assets.getBitmapData( "assets/ball.png" );
    _ball = new Bitmap( bData );
		
    addChild( _bg );
    addChild( _ball );
		
    _ball.x = 32;
    _ball.y = 10;
    _velocity = new Point( 0, GRAVITY );
		
    stage.addEventListener( KeyboardEvent.KEY_DOWN, _keyDown );
    stage.addEventListener( KeyboardEvent.KEY_UP, _keyUp );
    stage.addEventListener( Event.ENTER_FRAME, _update );
}

The first thing we do after the super() call is set the stage background color. Next we initialize our movement variables. _isJumping is set to true because our player will be dropping into the world and we don't want the user to be able to jump unless the character is on the ground. Then we load our images from the assets directory and add them to the display. You can get the assets from the downloadable zip here. Next we set our player's x and y positions along with the velocity. Finally, we add three event listeners. The first two will help us with movement and the last is our main update loop.

Note that none of these functions exist yet; don't worry, we'll get to those in a moment. First, let's go ahead and write our pixel collision detection function! That is, afterall, what this tutorial is all about.

private function _checkCollision():Point {
    var result:Point = null;
    var testPt:Point = new Point( _ball.x + ( _ball.width * 0.5 ), ( _ball.y + _ball.height ) + _velocity.y );
		
    if ( testPt.y > _bg.bitmapData.height ) {
        testPt.y = _bg.bitmapData.height - 1;
    }
		
    var curPixel:Int =  _bg.bitmapData.getPixel32( Math.round(testPt.x), Math.round(testPt.y) );
	
    if ( curPixel >> 24 & 0xff != 0 ) {
        // it's a hit, let's step back up to find the actual point of contact
        while ( curPixel >> 24 & 0xff != 0 ) {
            testPt.y -= 1;
            curPixel = _bg.bitmapData.getPixel32( Math.round(testPt.x), Math.round(testPt.y) );
        }
        testPt.y += 1;
        result = testPt;
    }
		
    return result;		
}

OK, let's step through this together now. This function evaluates the ball's position and checks to see if it makes contact with the ground. If it does make contact, we need to find out where this happens. Once found, the function returns the point of contact, or null if the ball is not touching the ground.

We begin by creating two Point objects. The first will be the result, the second is the position we need to test against. For this project, the bottom middle of the ball is going to be used as it's collision point so we set our test point x value to half the ball's width and it's y value to the bottom of the ball, plus the y velocity. We add the velocity because we want to check the position the ball will be at after the update, not the position it is at right now.

The next step is to make sure that our test point's y value is not greater than the background image's height. If it is, we just set it to the image height minus 1. This check is important because if the ball's velocity is great enough, it could pass right through the world and the pixel test would never detect a hit - the player would just fall for eternity!

Next we get the value of the pixel (as ARGB) at our test point within the background image. We then chop off the RGB bytes, curPixel >> 24, and get the alpha value by using a bitwise & with 0xff (255). If the pixel's alpha value is not zero, then we've hit solid ground. Now we enter the while loop to find the point of contact. In each iteration of the loop we simply step up one pixel and repeat the check. Once we've found a zero alpha pixel, we're no longer hitting the ground. Then just add one to the point's y position and you've got your point of contact! Adding one makes it so that the character is actually on the ground and not floating one pixel above it. Finally, we assign the found point to our result and return it.

It is worth noting that you can set the alpha threshold to be whatever you want. For example, if you wanted the character to pass through some semi-transparent pixels, you could check against a non-zero value.

We've got our collision routine finished, now we just need to write the event handler functions to take care of movement and updating the game. We'll start with the key up and down listeners as those are fairly simple and are required to move our character around. I put these functions just above the _checkCollision function we just wrote.

private function _keyDown( event:KeyboardEvent ):Void {
    if ( event.keyCode == 37 ) // left arrow
        _moveLeft = true;
    else if ( event.keyCode == 39 ) // right arrow
        _moveRight = true;
    else if ( event.keyCode == 38 ) { // up arrow
        if( !_isJumping ) {
            _velocity.y -= JUMP_POWER;
            _isJumping = true;
        }
    }
}
	
private function _keyUp( event:KeyboardEvent ):Void {
    if ( event.keyCode == 37 ) // left arrow
        _moveLeft = false;
    else if ( event.keyCode == 39 ) // right arrow
        _moveRight = false;
}

These two functions are pretty straight forward. The first one checks to see if a particular arrow key is pressed. If so, we set the appropriate boolean to true. We add a little additional logic for the up arrow as we don't want the player to be able to jump if they are already jumping. The second function just sets the boolean to false when one of the arrow keys get released; this stops our character movement.

The last function we need to write is _update. This function will take care of moving our character, applying gravity and it will call _checkCollision to find out if the character has hit the ground or not. Here is the code for our _update method:

private function _update( event:Event ) {				
			
    if ( _moveLeft && _ball.x - SPEED > 0 ) {
        _ball.x -= SPEED;
    }
    else if ( _moveRight && _ball.x + _ball.width + SPEED < stage.stageWidth ) {
        _ball.x += SPEED;
    }

    if ( _isJumping == true ) {
        _velocity.y += GRAVITY * 0.25;
    }
		
    var colPt:Point = _checkCollision();
		
    if ( colPt == null ) {	
        _ball.y += _velocity.y;
    }
    else {
        // we're on the ground
        _ball.y = colPt.y - _ball.height;
        _isJumping = false;
        _velocity.y = GRAVITY;
    }		
}

The function begins by checking for left and right movement. It does some simple bounds checking to keep our character on the screen at all times. I'm not making use of our velocity's x component here, but this approach is simple to understand and works just as well. Next there's a check to see if the character is jumping. If so, we increase the y velocity by a quarter of our gravity constant. This allows the player to fall faster and faster instead of at one steady rate. Note that the values for the constants and this 0.25 were found through trial and error; I just changed them until I found a result that felt good to me. Feel free to alter these numbers to your liking.

Once the y velocity is set, we perform our collision check to find the point of contact. If colPt ends up as null, then we haven't hit the ground and can apply the y velocity to our player's y position. If it is not null, then the player is on the ground so we set the bottom of the ball to colPt.y, set _isJumping to false and reset our y velocity to the value of GRAVITY.

And with that; we're all done! Congratulations on making it to the end of this tutorial on per pixel collision detection! Hopefully you've learned the basic concepts behind this technique, how to check individual pixels within an image and how to use that data to determine a character's point of contact with the world. The entire code is shown below and you can download the completed tutorial here.

Thanks for reading!

package;

import openfl.display.Bitmap;
import openfl.display.BitmapData;
import openfl.display.Sprite;
import openfl.Assets;
import openfl.events.Event;
import openfl.events.KeyboardEvent;
import openfl.geom.Point;
import flash.Lib;

class Main extends Sprite {
    private var SPEED:Int = 8;
    private var JUMP_POWER:Int = 45;
    private var GRAVITY:Int = 10;
	
    private var _ball:Bitmap;	
    private var _bg:Bitmap;
    private var _velocity:Point;
    private var _moveLeft:Bool;
    private var _moveRight:Bool;
    private var _isJumping:Bool;
	
    public function new () {
		
        super ();
		
        stage.color = 0x33bbff;
        _moveLeft = false;
        _moveRight = false;
        _isJumping = true;
		
        var bData:BitmapData = Assets.getBitmapData( "assets/bg.png" );
        _bg = new Bitmap( bData );
		
        bData = Assets.getBitmapData( "assets/ball.png" );
        _ball = new Bitmap( bData );
		
        addChild( _bg );
        addChild( _ball );
		
        _ball.x = 32;
        _ball.y = 10;	
        _velocity = new Point( 0, GRAVITY );
		
        stage.addEventListener( KeyboardEvent.KEY_DOWN, _keyDown );
        stage.addEventListener( KeyboardEvent.KEY_UP, _keyUp );
        stage.addEventListener( Event.ENTER_FRAME, _update );
    }
	
    private function _update( event:Event ) {				
			
        if ( _moveLeft && _ball.x - SPEED > 0 ) {
            _ball.x -= SPEED;
        }
        else if ( _moveRight && _ball.x + _ball.width + SPEED < stage.stageWidth ) {
            _ball.x += SPEED;
        }
			
        if ( _isJumping == true ) {
            _velocity.y += GRAVITY * 0.25;
        }
		
        var colPt:Point = _checkCollision();
		
        if ( colPt == null ) {
            _ball.y += _velocity.y;
        }
        else {
            _ball.y = colPt.y - _ball.height;
            _isJumping = false;
            _velocity.y = GRAVITY;
        }		
    }
	
    private function _keyDown( event:KeyboardEvent ):Void {
        if ( event.keyCode == 37 ) // left arrow
            _moveLeft = true;
        else if ( event.keyCode == 39 ) // right arrow
            _moveRight = true;
        else if ( event.keyCode == 38 ) { // up arrow
            if( !_isJumping ) {
                _velocity.y -= JUMP_POWER;
                _isJumping = true;
            }
        }
    }
	
    private function _keyUp( event:KeyboardEvent ):Void {
        if ( event.keyCode == 37 ) // left arrow
            _moveLeft = false;
        else if ( event.keyCode == 39 ) // right arrow
            _moveRight = false;
    }
	
    private function _checkCollision():Point {
        var result:Point = null;
        var testPt:Point = new Point( _ball.x + ( _ball.width * 0.5 ), ( _ball.y + _ball.height ) + _velocity.y );
		
        if ( testPt.y > _bg.bitmapData.height ) {
            testPt.y = _bg.bitmapData.height - 1;
        }
		
        var curPixel:Int =  _bg.bitmapData.getPixel32( Math.round(testPt.x), Math.round(testPt.y) );
		
        if ( curPixel >> 24 & 0xff != 0 ) {
            // it's a hit, let's step back up to find the actual point of contact
            while ( curPixel >> 24 & 0xff != 0 ) {
                testPt.y -= 1;
                curPixel = _bg.bitmapData.getPixel32( Math.round(testPt.x), Math.round(testPt.y) );
            }
            testPt.y += 1;
            result = testPt;
        }
		
        return result;		
    }	
}
Bookmark and Share

One Response to “Tutorial: Per Pixel Collision”

  1. Jeff Ward says:

    Not bad, but it is a very simple vertical getPixel detection method.

    Grant Skinner had an amazing detector using getColorBoundsRect — since OpenFL should have the same BitmapData APIs, this should be possible:

    http://blog.gskinner.com/archives/2005/08/flash_8_shape_b.html

Leave a Reply

Subscribe to RSS feed FGS5 Badge