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>
    <head>
        <meta name="viewport" content="initial-scale=1, maximum-scale=1">
        <link rel="stylesheet" href="style.css">
        </style>
        <script src="main.js"></script>
    </head>
    <body>
        <div id="thegame"></div>
    </body>
</html>

style.css

The cascading style sheets of the web page.

* {
    padding : 0;
    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);
        let circleImage : Phaser.Geom.Circle = new Phaser.Geom.Circle(movingCircle.radius + 1, movingCircle.radius + 1, movingCircle.radius);
        simulationGraphics.lineStyle(2, 0xffff00);
        simulationGraphics.strokeCircleShape(circleImage);
        simulationGraphics.generateTexture('circle', movingCircle.radius * 2 + 2, movingCircle.radius * 2 + 2);
        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 radiiSum : number = staticCircle.radius + movingCircle.radius;
                if (distanceBetweenCircles >= radiiSum) {     
                    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);
                    if (shortestDistanceLength < radiiSum) {
                        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);
            Phaser.Geom.Line.Extend(extendedLine, movingCircle.radius);
            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.

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