# 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.

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 10000000
// 2 Cars
// 2048
// Avoider
// Ballz
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// BoxHead
// Breakout
// Bricks
// Columns
// CubesOut
// Dots
// DROP'd
// Dudeski
// Eskiv
// Filler
// Fling
// Globe
// HookPod
// Hundreds
// InkTd
// Iromeku
// Lumines
// Magick
// MagOrMin
// Maze
// Memdot
// Nano War
// Nodes
// o:anquan
// Ononmin
// Pacco
// Phyballs
// Platform
// Poker
// Pool
// Poux
// Pudi
// qomp
// Racing
// Radical
// Renju
// SameGame
// Security
// Sling
// Slingy
// Sokoban
// Splitter
// Sproing
// Stack
// Stairs
// Stringy
// Sudoku
// Tetris
// Threes
// Toony
// Turn
// TwinSpin
// vvvvvv
// Wordle
// Worms
// Yanga
// Zhed
// zNumbers