# Continuous collision detection between a moving circle and one or more static line segments – vertex collision included

This is the last post about the theory of continuous collision detection between a moving circle and one (or more) static line segments.

It has been a long journey but now I can predict when a moving circle will hit a static line segment, no matter the circle velocity.

Let’s make a small recap:

To start removing arcade physics from Block it prototype built with TypeScript, I built a basic continuous collision detection between a moving circle and an infinite line. Then I added the capability of predicting circle bounces, but handling collisions against an infinite line is way different than dealing with a finite line segment.

That’s because of the vertices. We can assume a vertex is a circle with radius equal to zero, so I started building a prototype to handle continuous collision detection between a moving circle and a static circle.

Finally I built a method to handle continuous collision detection between a moving circle and a lot of static circles.

Now it’s time to wrap everything together, with a script to handle continuous collision detection between a moving circle and any number of line segments, vertices included.

This is what I built:

The yellow moving circle has a velocity of (740, 0). This means it will try to move by 740 pixels to the right. But there are a lot of random lines which may block its way making it bounce elsewhere.

As you can see, yellow circle movement is determined before it starts moving, thanks to continuous collision detection, in this case used as a predictive trajectory system.

To determine the path I used a recursive function called checkCollision which tries to move the circle for the entire velocity, and if it founds a collision, return the collision itself and another call to the same function trying to move the circle at the collision point for the entire remaining velocity, and so on.

Look at the source code, made of one html file, one css file and 4 TypeScript files:

### index.html

The web page which hosts the game, to be run inside thegame element.

```<!DOCTYPE html>
<html>
<meta name="viewport" content="initial-scale=1, maximum-scale=1">
</style>
<script src="main.js"></script>
<body>
<div id="thegame"></div>
</body>
</html>
```

### style.css

The cascading style sheets of the web page.

```* {
margin : 0;
background-color : #31343a;
}

body {
font : normal 14px arial;
color : white;
}

canvas {
touch-action : none;
-ms-touch-action : none;
}
```

### main.ts

This is where the game is created, with all Phaser related options.

```// 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.NONE,
autoCenter : Phaser.Scale.CENTER_HORIZONTALLY,
parent : 'thegame',
width : 800,
height : 600
}

// game configuration object
const configObject : Phaser.Types.Core.GameConfig = {
type : Phaser.AUTO,
backgroundColor : 0x31343a,
scale : scaleObject,
scene : [PlayGame]
}

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

### playGame.ts

Main file, all logic is stored here, included checkCollision method which is the recursive function mentioned above.

```import { CollisionResult } from './collisionResult';
import { intersectionType, Intersection } from './intersection';

// THE GAME ITSELF

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

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

// method to be executed when the scene has been created
create() : void {
let simulationGraphics : Phaser.GameObjects.Graphics = this.add.graphics();
let movingCircle : Phaser.Geom.Circle = new Phaser.Geom.Circle(40, 300, 30);
simulationGraphics.lineStyle(2, 0xffff00);
simulationGraphics.strokeCircleShape(circleImage);
simulationGraphics.clear();
let path : Phaser.Curves.Path = new Phaser.Curves.Path(movingCircle.x, movingCircle.y);
simulationGraphics.lineStyle(2, 0xff8800);
let staticLines : Phaser.Geom.Line[] = [];
for (let i : number = 0; i < 5; i ++) {
staticLines.push(new Phaser.Geom.Line(Phaser.Math.Between(100, 600), Phaser.Math.Between(0, 600), Phaser.Math.Between(100, 600), Phaser.Math.Between(0, 600)));
simulationGraphics.strokeLineShape(staticLines[i]);
}
let result : CollisionResult[] = this.checkCollision(movingCircle, new Phaser.Math.Vector2(750,  0), staticLines);
result.forEach((collision: CollisionResult, index : number) => {
let collisionCircle : Phaser.Geom.Circle = new Phaser.Geom.Circle(collision.point.x, collision.point.y, movingCircle.radius);
console.log(collision)
path.lineTo(collision.point.x, collision.point.y);
simulationGraphics.lineStyle(2, 0x666666);
simulationGraphics.strokeCircleShape(collisionCircle);
})
simulationGraphics.lineStyle(2, 0xffff00, 1);
path.draw(simulationGraphics);
let circleSprite : Phaser.GameObjects.PathFollower = this.add.follower(path, movingCircle.x, movingCircle.y, 'circle');
circleSprite.startFollow({
duration: 1500,
onComplete: () => this.scene.start()
});
}

checkCollision(movingCircle : Phaser.Geom.Circle, circleVelocity : Phaser.Math.Vector2, staticLines : Phaser.Geom.Line[]) : CollisionResult[] {
let velocityLine : Phaser.Geom.Line = new Phaser.Geom.Line(movingCircle.x, movingCircle.y, movingCircle.x + circleVelocity.x, movingCircle.y + circleVelocity.y);
let gotCollision : boolean = false;
let closestCircleDistance : number = Infinity;
let collisionResult : CollisionResult = new CollisionResult(new Phaser.Geom.Point(movingCircle.x + circleVelocity.x, movingCircle.y + circleVelocity.y), new Phaser.Math.Vector2(0, 0));
staticLines.forEach((staticLine : Phaser.Geom.Line) => {
let staticCircles : Phaser.Geom.Circle[] = [new Phaser.Geom.Circle(staticLine.x1, staticLine.y1, 0), new Phaser.Geom.Circle(staticLine.x2, staticLine.y2, 0)];
staticCircles.forEach((staticCircle : Phaser.Geom.Circle) => {
let distanceBetweenCircles : number = Phaser.Math.Distance.Between(movingCircle.x, movingCircle.y, staticCircle.x, staticCircle.y);
let shortestDistancePoint : Phaser.Geom.Point = Phaser.Geom.Line.GetNearestPoint(velocityLine, new Phaser.Geom.Point(staticCircle.x, staticCircle.y));
let shortestDistanceLine : Phaser.Geom.Line = new Phaser.Geom.Line(staticCircle.x, staticCircle.y, shortestDistancePoint.x, shortestDistancePoint.y);
let shortestDistanceLength : number = Phaser.Geom.Line.Length(shortestDistanceLine);
let distanceFromShortestDistancePoint : number = Math.sqrt(radiiSum * radiiSum - shortestDistanceLength * shortestDistanceLength);
let newCenter : Phaser.Geom.Point = new Phaser.Geom.Point(shortestDistancePoint.x - distanceFromShortestDistancePoint * (circleVelocity.x / Phaser.Geom.Line.Length(velocityLine)), shortestDistancePoint.y - distanceFromShortestDistancePoint * (circleVelocity.y / Phaser.Geom.Line.Length(velocityLine)));
let distanceFromNewCenterToCircle : number = Phaser.Math.Distance.Between(movingCircle.x, movingCircle.y, newCenter.x, newCenter.y);
if (newCenter.x >= velocityLine.left && newCenter.x <= velocityLine.right && newCenter.y >= velocityLine.top && newCenter.y <= velocityLine.bottom && distanceFromNewCenterToCircle < closestCircleDistance) {
let circleToDestinationCircleLine : Phaser.Geom.Line = new Phaser.Geom.Line(staticCircle.x, staticCircle.y, newCenter.x, newCenter.y);
let collisionTangent : Phaser.Geom.Line = Phaser.Geom.Line.Rotate(circleToDestinationCircleLine, Math.PI / 2);
let reflectionAngle : number = Phaser.Geom.Line.ReflectAngle(velocityLine, collisionTangent);
let remainingVelocity : number = Phaser.Math.Distance.Between(newCenter.x, newCenter.y, velocityLine.x2, velocityLine.y2);
gotCollision = true;
closestCircleDistance = distanceFromNewCenterToCircle;
collisionResult = new CollisionResult(newCenter, new Phaser.Math.Vector2(remainingVelocity * Math.cos(reflectionAngle), remainingVelocity * Math.sin(reflectionAngle)));
}
}
}
});
let extendedLine : Phaser.Geom.Line =  Phaser.Geom.Line.Clone(staticLine);
let velocityToSegmentIntersection : Intersection = this.getIntersectionPoint(velocityLine, extendedLine);
let destinationCircle : Phaser.Geom.Circle = new Phaser.Geom.Circle(velocityLine.x2, velocityLine.y2, movingCircle.radius);
let destinationCircleIntersectsBarrier : boolean = Phaser.Geom.Intersects.LineToCircle(staticLine, destinationCircle);
if (velocityToSegmentIntersection.type == intersectionType.Strict || destinationCircleIntersectsBarrier) {
let shortestDistancePoint : Phaser.Geom.Point = Phaser.Geom.Line.GetNearestPoint(staticLine, new Phaser.Geom.Point(movingCircle.x, movingCircle.y));
let shortestDistanceLine : Phaser.Geom.Line = new Phaser.Geom.Line(movingCircle.x, movingCircle.y, shortestDistancePoint.x, shortestDistancePoint.y);
let shortestDistanceLineLength : number = Phaser.Geom.Line.Length(shortestDistanceLine);
let movementLine : Phaser.Geom.Line = new Phaser.Geom.Line(movingCircle.x, movingCircle.y, velocityToSegmentIntersection.point.x, velocityToSegmentIntersection.point.y);
let ratioonmovement : number =  movingCircle.radius / shortestDistanceLineLength;
let newCenter: Phaser.Geom.Point = Phaser.Geom.Line.GetPoint(movementLine, 1 - ratioonmovement);
let closestPoint : Phaser.Geom.Point = Phaser.Geom.Line.GetNearestPoint(staticLine, new Phaser.Geom.Point(newCenter.x, newCenter.y))
let distanceFromNewCenterToCircle : number = Phaser.Math.Distance.Between(movingCircle.x, movingCircle.y, newCenter.x, newCenter.y);
if (closestPoint.x >= staticLine.left && closestPoint.x <= staticLine.right && closestPoint.y >= staticLine.top && closestPoint.y <= staticLine.bottom && distanceFromNewCenterToCircle < closestCircleDistance) {
gotCollision = true;
closestCircleDistance = distanceFromNewCenterToCircle;
let reflectionAngle : number = Phaser.Geom.Line.ReflectAngle(velocityLine, staticLine);
let remainingVelocity : number = Phaser.Math.Distance.Between(newCenter.x, newCenter.y, velocityLine.x2, velocityLine.y2);
collisionResult = new CollisionResult(new Phaser.Geom.Point(newCenter.x, newCenter.y), new Phaser.Math.Vector2(remainingVelocity * Math.cos(reflectionAngle), remainingVelocity * Math.sin(reflectionAngle)));
}
}
});
if (!gotCollision) {
return [collisionResult];
}
else {
return [collisionResult].concat(this.checkCollision(new Phaser.Geom.Circle(collisionResult.point.x, collisionResult.point.y, movingCircle.radius), new Phaser.Math.Vector2(collisionResult.velocity.x, collisionResult.velocity.y), staticLines));
}
}

getIntersectionPoint(line1 : Phaser.Geom.Line, line2 : Phaser.Geom.Line) : Intersection {
if ((line1.x1 == line1.x2 && line1.y1 == line1.y2) || (line2.x1 == line2.x2 && line2.y1 == line2.y2)) {
return new Intersection(intersectionType.None);
}
let denominator : number = ((line2.y2 - line2.y1) * (line1.x2 - line1.x1) - (line2.x2 - line2.x1) * (line1.y2 - line1.y1));
if (denominator == 0) {
return new Intersection(intersectionType.None);
}
let ua : number = ((line2.x2 - line2.x1) * (line1.y1 - line2.y1) - (line2.y2 - line2.y1) * (line1.x1 - line2.x1)) / denominator;
let ub : number = ((line1.x2 - line1.x1) * (line1.y1 - line2.y1) - (line1.y2 - line1.y1) * (line1.x1 - line2.x1)) / denominator;
let outsideSegments : boolean = (ua < 0 || ua > 1 || ub < 0 || ub > 1)
let x : number = line1.x1 + ua * (line1.x2 - line1.x1);
let y : number = line1.y1 + ua * (line1.y2 - line1.y1);
return new Intersection(outsideSegments ? intersectionType.Simple : intersectionType.Strict, new Phaser.Geom.Point(x, y));
}
}
```

### collisionResult.ts

Just a custom class to handle a collision, which is made by a point (the new center of the circle) and a vector (the new circle velocity).

```export class CollisionResult {
point : Phaser.Geom.Point;
velocity : Phaser.Math.Vector2;
constructor(point : Phaser.Geom.Point, velocity : Phaser.Math.Vector2) {
this.point = point;
this.velocity = velocity;
}
}
```

### intersection.ts

Another custom class to define the intersection type of two line segments, which can be None if line segments do not intersect, Simple if they would intersect if they were infinite or Strict if they intersect.

```export enum intersectionType {
None,
Simple,
Strict
}

export class Intersection {
type : intersectionType;
point : Phaser.Geom.Point;
constructor(type : intersectionType, point? : Phaser.Geom.Point) {
this.type = type;
if (point !== undefined) {
this.point = point;
}
}
}
```

And finally we have our non physics driven continuous collision detection method. Next time, we’ll see how to use it in a real world example. Meanwhile, download the source code and play with it.

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 10000000
// 2 Cars
// 2048
// Avoider
// Ballz
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// 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
// Renju
// SameGame
// Security
// Sling
// Slingy
// Sokoban
// Splitter
// Sproing
// Stack
// Stairs
// Stringy
// Sudoku
// Tetris
// Threes
// Toony
// Turn
// TwinSpin
// vvvvvv
// Wordle
// Worms
// Yanga
// Zhed
// zNumbers