Understanding physics continuous collision detection using swept AABB method and Minkowski sum

During the making of Serious Scramblers tutorial series, some readers reported missing collision detection when playing on mobile phones, and on an old Huawei P10 I had the same bad experience.

This is because Arcade physics, the simplest physics engine shipped with Phaser, does not handle continuos collision detection.

I tried to simulate it in this experiment, but on old mobile phones it’s still buggy.

So I started studying something about continuous collision detection, and the simplest method, which is perfect for simple platformers, is the swept AABB method.

There are three limitations:

1 – Bodies must be axis aligned. In geometry, an axis-aligned object (axis-parallel, axis-oriented) is an object in n-dimensional space whose shape is aligned with the coordinate axes of the space.

2 – Bodies must be bounding boxes, so we are talking about squares or rectangles, or anything which can be simplified as a square or a rectangle.

3 – It works ony applied on linear velocity. It means bodies must move along a straight line.

So how does it work? Look at the picture:

Body A wants to move in the direction of the arrow, but there is body B which won’t let Body A to reach the end of the path.

How, where and when to stop Body A?

Let’s start computing the Minkowski sum of Body A and Body B. In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors A and B in Euclidean space is formed by adding each vector in A to each vector in B, i.e., the set.

Basically, we are going to inflate Body B with body A, this way:

Now the grey box is the Minkowski sum of Body B and Body A.

At this time we only have to place Body A origin on the intersection between the line of movement and the Minkowski rectangle:

And this is where collision happens, no matter the speed of Body A.

This is fascinating, isn’t it? Now the question is: why should I learn this stuff when there are billions of physics engines doing the same thing? I have a lot of answers:

1 – You are actually learning something new.

2 – Knowing how stuff works under the hood is always an achievement

3 – In some cases, why should you use a physics engine when you can solve your problems with a couple of lines of code?

Anyway, let’s see what happens when we compare a physics engine which does not feature continuous collision detection with one which features it.

Look at this example, with an Arcade body and a Swept AABB body fired at 200 pixels per second:

Touch or click the canvas to start the simulation. You should see both dots running at the same speed, then hit the yellow wall.

Fine, now try this other simulation, where the dots are fired at 20000 pixels per second:

Probably the Arcade dot did not stop on the yellow wall, because it was too fast for the simulation.

Now, let’s see the source code of this simple physics engine:

index.html

The webpage which hosts the game, just the bare bones of HTML.

Also look at the thegame div, this is where the game runs.

<!DOCTYPE html>
<html>
    <head>
        <script src = "main.js"></script>
    </head>
<body>
    <div id = "thegame"></div>
</body>
</html>

main.ts

The main TypeScript file, the one called by index.html.

Here we import most of the game libraries and define Scale Manager object.

Here we also initialize the game itself.

// MAIN GAME FILE

// modules to import
import Phaser from 'phaser';
import { PlayGame} from './playGame';

// object to initialize the Scale Manager
const scaleObject: Phaser.Types.Core.ScaleConfig = {
    mode: Phaser.Scale.FIT,
    autoCenter: Phaser.Scale.CENTER_BOTH,
    parent: 'thegame',
    width: 800,
    height: 416
}

// game configuration object
const configObject: Phaser.Types.Core.GameConfig = {
    type: Phaser.AUTO,
    scale: scaleObject,
    scene: [PlayGame],
    physics: {
        default: 'arcade'
    }
}

// the game itself
new Phaser.Game(configObject);

playGame.ts

In playGame class we place all stuff on the canvas, make all stuff work and handle user input

// THE GAME ITSELF

import PhysicsBox from "./physicsBox";

// this class extends Scene class
export class PlayGame extends Phaser.Scene {

    // these are my physics box and wall
    box: PhysicsBox;
    wall: PhysicsBox;

    // these are the Arcade physics box and wall
    arcadeBox: Phaser.Physics.Arcade.Sprite;
    arcadeWall: Phaser.Physics.Arcade.Sprite;

    // speed of the projectile, in pixels per second
    projectileSpeed: number = 20000;

    // constructor
    constructor() {
        super({
            key: 'PlayGame'
        });
    }

    // method to be called once the class preloads
    preload(): void {

        // load graphic assets
        this.load.image('dot', 'assets/dot.png');
        this.load.image('wall', 'assets/wall.png');

    }

    // method to be called once the class has been created
    create(): void {

        // creation of my physics box and wall
        this.box = new PhysicsBox(this, 20, 128, 'dot');
        this.wall = new PhysicsBox(this, 780, 128, 'wall');

        // creation of Arcade box and wall
        this.arcadeBox = this.physics.add.sprite(20, 288, 'dot');
        this.arcadeWall = this.physics.add.sprite(780, 288, 'wall');

        // set the wall as immovable
        this.arcadeWall.setImmovable(true);

        // input listener to fire the bullet
        this.input.on('pointerdown', this.fireBullets, this);

        // just some text to display informaiton
        this.add.text(20, 195, 'Bullet Speed: ' + this.projectileSpeed + ' pixels per second', {
            fontSize: '32px'
        });

        this.add.text(20, 12, 'Swept AABB', {
            fontSize: '24px'
        });
        this.add.text(20, 380, 'Arcade Physics', {
            fontSize: '24px'
        });
    }

    // FIRE!!!
    fireBullets() {

        // fire both my box and Arcade physics box
        this.arcadeBox.setVelocity(this.projectileSpeed, 0);
        this.box.setVelocity(this.projectileSpeed, 0);
    }

    // method to be executed at each frame
    update(totalTime: number, deltaTime: number): void {

        // update box position, checking for wall collision
        this.box.updatePosition(deltaTime, this.wall);
        
        // Arcade physics collider
        this.physics.world.collide(this.arcadeBox, this.arcadeWall);
    }
}

physicsBox.ts

The core of the script, this is where our physics box is defined.

Collision detection is handled in this class.

// PhysicsBox class extends Phaser Sprite class
export default class PhysicsBox extends Phaser.GameObjects.Sprite {

    // vector containing x and y velocity
    velocity: Phaser.Math.Vector2;

    // constructor - arguments: the scene, x and y position and texture key
    constructor(scene: Phaser.Scene, x: number, y: number, key: string) {
        super(scene, x, y, key);
        scene.add.existing(this);

        // physics object has no velocity at the beginning
        this.velocity = new Phaser.Math.Vector2(0, 0);
    }

    // set body velocity - arguments: x and y velocity
    setVelocity(x: number, y: number): void {

        // update velocity property
        this.velocity.x = x;
        this.velocity.y = y;
    }

    // method to update physics box position - arguments: the amount of milliseconds and the obstacle to check collision with
    updatePosition(milliseconds: number, obstacle: PhysicsBox): void {

        // get movement line, from box origin to box destination
        let movementLine: Phaser.Geom.Line =  new Phaser.Geom.Line(this.x, this.y, this.x + this.velocity.x * (milliseconds / 1000), this.y + this.velocity.y * (milliseconds / 1000));
        
        // Minkowski rectangle built inflating the obstacle with the physics body
        let minkowskiRectangle: Phaser.Geom.Rectangle = this.minkowskiSum(obstacle);

        // array to store all intersection points between movement line and Minkowski rectangle
        let intersectionPoints: Phaser.Geom.Point[] = [];
        
        // get all intersection points between movement line and Minkowski rectangle, then store them into intersectionPoints array
        Phaser.Geom.Intersects.GetLineToRectangle(movementLine, minkowskiRectangle, intersectionPoints);

        // different actions according to the number of intersections
        switch (intersectionPoints.length) {

            // no intersection: just move the body
            case 0:
                this.x += this.velocity.x * (milliseconds / 1000);
                this.y += this.velocity.y * (milliseconds / 1000);
                break;

            // one intersection: move the body to intersection point and stop it
            case 1:
                this.x = intersectionPoints[0].x;
                this.y = intersectionPoints[0].y;
                this.setVelocity(0, 0);
                break;

            // 2 or more intersection points: move the body to the closest intersection point and stop it
            default:

                // set the minimum distance to Infinity, the highest number
                let minDistance: number = Infinity;

                // set minimum index to zero (first element)
                let minIndex: number = 0;

                // looping through all instersection points
                for (let i: number = 0; i < intersectionPoints.length; i ++) {

                    // get distance between body and points
                    let distance: number = Phaser.Math.Distance.Between(this.x, this.y, intersectionPoints[i].x, intersectionPoints[i].y);
                    
                    // is distance less then minimum distance?
                    if (distance < minDistance) {

                        // update minimum index
                        minIndex = i;

                        // update minimum distance
                        minDistance = distance;
                    } 
                }

                // move the body to the closest intersection point and stop it
                this.x = intersectionPoints[minIndex].x;
                this.y = intersectionPoints[minIndex].y;
                this.setVelocity(0, 0);
                break;
        }
    }

    // method to perform the Minkowski sum - argument: the box where to sum current body
    minkowskiSum(box :PhysicsBox): Phaser.Geom.Rectangle {
        
        // get boxes bounds
        let b1Bounds = this.getBounds();
        let b2Bounds = box.getBounds();

        // return the inflated rectangle
        return new Phaser.Geom.Rectangle(b2Bounds.left - b1Bounds.width / 2, b2Bounds.top - b1Bounds.height / 2, b1Bounds.width + b2Bounds.width, b1Bounds.height + b2Bounds.height);
    }
}

And now we managed to deal with continuous collision detection in a couple of lines.

But, how can we turn this stuff into something playable? I have an idea in mind, keep following me and meanwhile download the source code of this example.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers