Typescript Polygon Collision Detection

Polygon Collision Detection is all about the Separating Axis Theorem. The Separating Axis Theorem was briefly covered earlier, and it's the idea that if you have two convex objects, if you can draw a line (or axis) between the two object then they do not collide. Also, if there is a line that can separate those two polygons, there must also be a line that is parallel to one of the edges of at least one of the polygons that can separate the two polygons.

Vector Projection

We are going to use Vector Projection as a method to determine if there is a line parallel to one of those edges that can separate our two polygons. The way to do that is to take a line that is 90 degrees to our chosen edge, and project all the edges from both polygons onto that line and see if the ranges of those projections overlap. We have covered Vector Projection in our previous tutorial on Oriented Rectangle Collision Detection. The basic principle of projecting one vector onto another is to make a right triangle connecting the projecting vector and the projected vector. The new vector will be the same direction as the vector you are projecting onto, but with a new magnitude. In the diagram below we are projecting the blue vector onto the green vector. The new vector will have the direction of the green vector, but a new magnitude that will be where the black dashed line intersects with the green line.

Here's the source code for our vector projection that must be added to our cVector class:

public project = (onto: cVector): cVector => {
   var proj: cVector = this.duplicate();
   var d: number = onto.magSq();

   if (d != 0) {
      var mult: cVector = new cVector(onto.x, onto.y);
      mult.multiply(proj.dot(onto) / d);
      return mult;
   }
   return onto;
}

What this function is doing is taking the vector we are projecting onto and modifying it's magnitude based on the dot product with the projecting vector. We don't actually use this project method to detect the collision because we want to project our edges along a line. Let's condense all of our previously defined colliders down to a single collider that we can extend in all of our shape classes.

class cCollider {
   public position: cVector = new cVector();
   public rotation: number = 0;
   protected _pointList: Array<cVector> = new Array<cVector>();
   protected _edgeList: Array<cLine> = new Array<cLine>();
   protected _finalEdge: cLine = new cLine();

   public hitTest = (obj: cCollider): boolean => {
      var edge: cLine;

      for (var i: number = 0; i < this.edgeCount; i++) {
         edge = this.getEdge(i);
         if (obj.axisOverlap(edge, this) == false) {
            return false;
         }
      }

      for (var i: number = 0; i < obj.edgeCount; i++) {
         edge = obj.getEdge(i);
         if (this.axisOverlap(edge, obj) == false) {
            return false;
         }
      }

      return true;
   }

   public static isConvex(collider: cCollider ): boolean {
      var point_count: number = collider.pointCount();
      if (point_count < 4) {
         return true;
      }

      var point: cVector = new cVector();
      var d1: cVector = new cVector();
      var d2: cVector = new cVector();
      var sign: boolean = false;

      for (var i: number = 0; i < point_count; i++) {
         point.copy(collider.getPoint(i));

         if (i < point_count - 2) {
            d1.copy(collider.getPoint(i + 1));
            d2.copy(collider.getPoint(i + 2));

            d2.subtract(d1);
            d1.subtract(point);

         }
         else if (i < point_count - 1) {
            d1.copy(collider.getPoint(i + 1));
            d2.copy(collider.getPoint(0));

            d2.subtract(d1);
            d1.subtract(point);
         }
         else {
            d1.copy(collider.getPoint(0));
            d2.copy(collider.getPoint(1));

            d2.subtract(d1);
            d1.subtract(point);
         }

         d2.rotate90();
         var dot: number = d1.dot(d2);

         if (i == 0) {
            sign = dot > 0;
         }
         else if (sign != (dot > 0)) {
            return false;
         }

      }

      return true;
   }

   public axisOverlap = (axis: cLine, p2: cCollider): boolean => {
      var edge: cLine;

      var direction: cVector = axis.position.duplicate();
      direction.subtract(axis.endPosition);
      direction.normalize();
      direction.rotate90();

      var axis_range: cRange = new cRange();
      for (var i: number = 0; i < p2.edgeCount; i++) {
         edge = p2.getEdge(i);
         range = cCollider.ProjectLine(edge, direction);
         if (i == 0) {
            axis_range.copy(range);
         }
         else {
            axis_range = axis_range.combine(range);
         }
      }

      var range: cRange;

      var projection: cRange = new cRange();

      for (var i: number = 0; i < this.edgeCount; i++) {
         edge = this.getEdge(i);
         range = cCollider.ProjectLine(edge, direction);
         if (i == 0) {
            projection.copy(range);
         }
         else {
            projection = projection.combine(range);
         }
      }

      return axis_range.overlap(projection);
   }

   public findClosePointNum = (point: cVector): number => {
      var close_dist_sq: number = 99999999;
      var temp_point: cVector;
      var dist_vec: cVector = new cVector();
      var close_point_num = -1;

      for (var i: number = 0; i < this._pointList.length; i++) {
         temp_point = this._pointList[i];
         dist_vec.copy(point);
         dist_vec.subtract(temp_point);

         if (dist_vec.magSq() < close_dist_sq) {
            close_dist_sq = dist_vec.magSq();
            close_point_num = i;
         }
      }
      return close_point_num;
   }
   public static ProjectLine = (line: cLine, onto: cVector): cRange => {
      var ontoNormalized: cVector = onto.duplicate();
      ontoNormalized.normalize();

      var range: cRange = new cRange();
      var dot1: number = ontoNormalized.dot(line.position);
      var dot2: number = ontoNormalized.dot(line.endPosition);

      if (dot2 > dot1) {
         range.min = dot1;
         range.max = dot2;
      }
      else {
         range.min = dot2;
         range.max = dot1;
      }

      return range;

   }

   public getEdge = (edge_num: number): cLine => {
      var p1: cVector;
      var p2: cVector;

      if (edge_num < this._pointList.length - 1) {
         p1 = this.getPoint(edge_num);
         p2 = this.getPoint(edge_num + 1);
      }
      else {
         p1 = this.getPoint(edge_num);
         p2 = this.getPoint(0);
      }

      if (p1 == null || p2 == null) {
         return null;
      }

      var p1_transform: cVector = p1.duplicate();
      var p2_transform: cVector = p2.duplicate();

      p1_transform.rotate(this.rotation);
      p1_transform.add(this.position);

      p2_transform.rotate(this.rotation);
      p2_transform.add(this.position);

      var edge: cLine = new cLine();
      edge.position = p1_transform;
      edge.endPosition = p2_transform;
      return edge;
   }

   public getPoint = (point_num: number): cVector => {
      return this._pointList[point_num];
   }

   public pointCount = (): number => {
      return this._pointList.length;
   }

   get edgeCount(): number {
      return this._pointList.length;
   }

   public clearPoints = (): void => {
      this._pointList = new Array<cVector>();
      this._edgeList = new Array<cLine>();
   }

   public addPoint = (point: cVector): void => {
      this._pointList.push(point);
   }
   public projectEdge = (edge_num: number, onto: cVector): cRange => {
      var line: cLine = this.getEdge(edge_num);
      var ontoNormalized: cVector = onto.duplicate();
      ontoNormalized.normalize();

      var range: cRange = new cRange();
      var dot1: number = ontoNormalized.dot(line.position);
      var dot2: number = ontoNormalized.dot(line.endPosition);

      if (dot2 > dot1) {
         range.min = dot1;
         range.max = dot2;
      }
      else {
         range.min = dot2;
         range.max = dot1;
      }

      return range;
   }
}

That's a lot of code, so let's look at it one piece at a time. First let's look at hitTest().

Collider Hit Test

   public hitTest = (obj: cCollider): boolean => {
      var edge: cLine;

      for (var i: number = 0; i < this.edgeCount; i++) {
         edge = this.getEdge(i);
         if (obj.axisOverlap(edge, this) == false) {
            return false;
         }
      }

      for (var i: number = 0; i < obj.edgeCount; i++) {
         edge = obj.getEdge(i);
         if (this.axisOverlap(edge, obj) == false) {
            return false;
         }
      }

      return true;
   }

The guts of this method is the two for loops that loop through all of the edges of each of the collider and uses that edge as an axis along which to project all of the other edges for the two colliders looking to see if there is overlap. If there is an edge that does not have overlap, then there is an axis which can be used to separate the two polygons, and the colliders do not intersect. At this point we will need to look at the axisOverlap() method to see how that works.

Collider Axis Overlap

   public axisOverlap = (axis: cLine, p2: cCollider): boolean => {
      var edge: cLine;

      var direction: cVector = axis.position.duplicate();
      direction.subtract(axis.endPosition);
      direction.normalize();
      direction.rotate90();

      var axis_range: cRange = new cRange();
      for (var i: number = 0; i < p2.edgeCount; i++) {
         edge = p2.getEdge(i);
         range = cCollider.ProjectLine(edge, direction);
         if (i == 0) {
            axis_range.copy(range);
         }
         else {
            axis_range = axis_range.combine(range);
         }
      }

      var range: cRange;

      var projection: cRange = new cRange();

      for (var i: number = 0; i < this.edgeCount; i++) {
         edge = this.getEdge(i);
         range = cCollider.ProjectLine(edge, direction);
         if (i == 0) {
            projection.copy(range);
         }
         else {
            projection = projection.combine(range);
         }
      }

      return axis_range.overlap(projection);
   }

The first thing we do is take the line we pass in and change that into a vector by subtracting the starting point from the ending point. The next thing we need to do is rotate that vector by 90 degrees. This will be the vector we will project our edges along. We will do that in a for loop for each collider and combine the ranges returned for every edge. Finally we will check to see if those two ranges overlap, and return that value.

Range Class

A range is a minimum and a maximum value and several methods that help you manage those values.

class cRange {
   public min: number = 0;
   public max: number = 0;

   constructor(min: number = 0, max: number = 0) {
      this.min = min;
      this.max = max;
   }

   public overlap = (other: cRange): boolean => {
      return other.min <= this.max && this.min <= other.max;
   }

   public sort = (): void => {
      if (this.min > this.max) {
         var temp: number = this.min;
         this.min = this.max;
         this.max = temp;

      }
   }

   public copy = (range: cRange): void => {
      this.min = range.min;
      this.max = range.max;
   }

   public duplicate = (): cRange => {
      return new cRange(this.min, this.max);
   }

   public combine = (range: cRange): cRange => {
      var combined: cRange = new cRange();
      combined.min = this.min;
      combined.max = this.max;
      if (range.min < this.min) {
         combined.min = range.min;
      }

      if (range.max > this.max) {
         combined.max = range.max;
      }
      return combined;
   }

   public extend = (value: number): void => {
      if (value > this.max) {
         this.max = value;
      }
      else if (value < this.min) {
         this.min = value;
      }
   }

   public clamp = (value: number): number => {
      if (value < this.min) {
         return this.min;
      }
      if (value > this.max) {
         return this.max;
      }
      return value;
   }
}

Extending the Collider Class

At this point we are going to need to go back and retrofit our Space Ship, Asteroid, and Bullet classes to extend the collider class that we have added. We are also going to need to change our Bullet and Space Ship classes somewhat to accomidate the point lists used by the Collider class.

In the Bullet class we are now extending the Collider class. In order to make this work, we are going to be adding a setSize() method as well as changing the constructor to use it. The setSize method will add values into the _pointList array to be used by the collider to help with edge detection.

class cBullet extends cCollider implements iShape {
   public active: boolean = true;
   public lineWidth: number = 5;
   private _size: number = 0;
   private _halfSize: number = 0;
   public color: string = "red";

   public lineWidthAnimVal: number = 0;
   public widthUp: boolean = true;

   public velocity: cVector = new cVector();
   public speed: number = 5;

   public launch = (orientation: cVector, rotation: number): void => {
      this.velocity.copy(orientation);
      this.velocity.multiply(this.speed);
      this.rotation = rotation;
   }

   public draw = (): void => {
      if (this.active == false) {
         return;
      }

      if (this.widthUp == true) {
         this.lineWidthAnimVal += 0.1;

         if (this.lineWidthAnimVal >= 2) {
            this.widthUp = false;
         }
      }
      else {
         this.lineWidthAnimVal -= 0.1;
         if (this.lineWidthAnimVal <= -2) {
            this.widthUp = true;
         }
      }
      this.position.x += this.velocity.x;
      this.position.y += this.velocity.y;

      if (this.position.x < -10 || this.position.x > 1290 || this.position.y < -10 || this.position.y > 730) {
         this.active = false;
      }

      ctx.save();
      ctx.translate(this.position.x, this.position.y);
      ctx.rotate(this.rotation);
      ctx.beginPath();
      ctx.strokeStyle = this.color;
      ctx.lineWidth = this.lineWidth + this.lineWidthAnimVal;
      ctx.rect(-this._halfSize, -this._halfSize, this._size, this._size);

      ctx.stroke();
      ctx.restore();
   }

   public constructor(x: number, y: number, size: number, color: string = "red", lineWidth: number = 5) {
      super();
      this.position.x = x;
      this.position.y = y;
      this.setSize( size );
      this.color = color;
      this.lineWidth = lineWidth;
   }

   public setSize = (size: number): void => {
      this._size = size;
      this._halfSize = size / 2;
      while (this._pointList.length > 0) {
         this._pointList.pop();
      }
      this._pointList.push(new cVector(-this._halfSize, -this._halfSize));
      this._pointList.push(new cVector(this._halfSize, -this._halfSize));
      this._pointList.push(new cVector(this._halfSize, this._halfSize));
      this._pointList.push(new cVector(-this._halfSize, this._halfSize));
   }

   public static GetInactiveBullet(): cBullet {
      var bullet: cBullet = null;
      for (var i: number = 0; i < bullet_array.length; i++) {
         bullet = bullet_array[i];
         if (bullet.active == false) {
            break;
         }
      }
      return bullet;
   }
}

Changes to the Ship class

Next we need to make changes to the Ship class to make it extend the Collider class. A few things to notice about the Ship class, is that we need to keep a seperate version of the point list (_drawPointList) that is convex, since our ship has a small concave part at it's back. Only convex shapes work with the separating axis theorem, but our ship looks a little more like an arrow than a triangle. However, what we are going to detect our collisions with will have to be a triangle.

class cSpaceShip extends cCollider implements iShape {
   public alive: boolean = true;
   public velocity: cVector = new cVector(0, 0);
   public orientation: cVector = new cVector(1, 0);
   public maxSpeedSQ: number = 25;
   private _maxSpeed: number = 5;
   public acceleration: number = 0.1;
   protected _drawPointList: Array<cVector> = new Array<cVector>();

   public lineWidth: number = 5;
   public color: string = "white";
   public size: number = 20;
   public rotation: number = 0;

   private _tempVec: cVector = new cVector(0, 0);

      public accelerate = (): void => {
      if (this.velocity.x == 0 && this.velocity.y == 0) {
         this.velocity.copy(this.orientation);
         this.velocity.multiply(this.acceleration);
      }

      this._tempVec.copy(this.orientation);
      this._tempVec.multiply(this.acceleration);
      this.velocity.add(this._tempVec);
      if (this.velocity.magSq() >= this.maxSpeedSQ) {
         this.velocity.multiply(this.maxSpeed / this.velocity.magnitude());
      }
   }

   public shoot = (): void => {
      if (bulletWait > 0) {
         return;
      }
      bulletWait = 0.5;
      var bullet: cBullet = cBullet.GetInactiveBullet();

      if (bullet == null || bullet.active == true) {
         bullet = new cBullet(this.position.x, this.position.y, 3);
         bullet_array.push(bullet);
      }
      else {
         bullet.position.x = this.position.x;
         bullet.position.y = this.position.y;
         bullet.active = true;
      }
      bullet.launch(this.orientation, this.rotation);
   }

   public decelerate = (): void => {
      this.velocity.multiply(0.9);

      if (this.velocity.magSq() < 1) {
         this.velocity.x = 0;
         this.velocity.y = 0;
      }
   }

   get maxSpeed(): number {
      return Math.sqrt(this.maxSpeedSQ);
   }

   set maxSpeed(value: number) {
      this._maxSpeed = value;
      this.maxSpeedSQ = value * value;
   }

   public draw = (): void => {
      if (this.alive == false) {
         return;
      }

      this.position.add( this.velocity );

      if (this.position.x < -this.size * 2) {
         this.position.x = 1280 + this.size * 2;
      }
      else if (this.position.x > 1280 + this.size * 2) {
         this.position.x = -2 * this.size;
      }

      if (this.position.y < -this.size * 2) {
         this.position.y = 720 + this.size * 2;
      }
      else if (this.position.y > 720 + this.size * 2) {
         this.position.y = -2 * this.size;
      }

      ctx.save();
      ctx.translate(this.position.x, this.position.y);
      ctx.rotate(this.rotation);
      ctx.beginPath();

      ctx.strokeStyle = this.color;
      ctx.lineWidth = this.lineWidth;

      ctx.moveTo(this._drawPointList[this._drawPointList.length - 1].x,
      this._drawPointList[this._drawPointList.length - 1].y);

      for (var i: number = 0; i < this._drawPointList.length; i++) {
         ctx.lineTo(this._drawPointList[i].x, this._drawPointList[i].y);
      }

      ctx.closePath();

      ctx.stroke();
      ctx.restore();
   }

   public turnLeft = (): void => {
      this.rotation -= 0.1;
      if (this.rotation < 0) {
         this.rotation += Math.PI * 2;
      }
      this.orientation.x = 1;
      this.orientation.y = 0;
      this.orientation.rotate(-this.rotation);
   }

   public turnRight = (): void => {
      this.rotation += 0.1;
      this.rotation %= Math.PI * 2;
      this.orientation.x = 1;
      this.orientation.y = 0;
      this.orientation.rotate(-this.rotation);
   }

   constructor(x: number, y: number, size: number, color: string = "white", line_width: number = 2) {
      super();
      this.position.x = x;
      this.position.y = y;
      this.size = size;

      this._pointList.push(new cVector(3 * size, 0));
      this._pointList.push(new cVector(-2 * size, -2 * size));
      // REMOVE THIS POINT FROM COLLISION DETECTION TO MAKE CONVEX
      // this._pointList.push(new cVector(-1 * size, 0));
      this._pointList.push(new cVector(-2 * size, 2 * size));

      this._drawPointList.push(new cVector(3 * size, 0));
      this._drawPointList.push(new cVector(-2 * size, -2 * size));
      this._drawPointList.push(new cVector(-1 * size, 0));
      this._drawPointList.push(new cVector(-2 * size, 2 * size));

      this.color = color;
      this.lineWidth = line_width;
   }

}

Asteroid class changes

In addition to changing the Asteroid class to extend the Collider class, we are going to need to make sure any Asteroid we create is convex.

class cAsteroid extends cCollider implements iShape {
   public active: boolean = true;
   public lineWidth: number = 5;
   public color: string = "white";
   private _size: number = 20;
   public rotation: number = 0;
   public rotationSpeed: number = 0;
   public velocity: cVector = new cVector();

   public setSize = (size: number): void => {
      this._size = size;
      var xrand: number = 0;
      var yrand: number = 0;

      xrand = Math.round(Math.random() * size - size / 2);
      yrand = Math.round(Math.random() * size - size / 2);

      do {
         while (this._pointList.length > 0) {
            this._pointList.pop();
         }
         this._pointList.push(new cVector(xrand, yrand + 3 * size));

         xrand = Math.round(Math.random() * size - size / 2);
         yrand = Math.round(Math.random() * size - size / 2);

         this._pointList.push(new cVector(xrand + 3 * size, yrand + size));

         xrand = Math.round(Math.random() * size - size / 2);
         yrand = Math.round(Math.random() * size - size / 2);

         this._pointList.push(new cVector(xrand + 3 * size, yrand - size));

         xrand = Math.round(Math.random() * size - size / 2);
         yrand = Math.round(Math.random() * size - size / 2);

         this._pointList.push(new cVector(xrand + size, yrand - 3 * size));

         xrand = Math.round(Math.random() * size - size / 2);
         yrand = Math.round(Math.random() * size - size / 2);

         this._pointList.push(new cVector(xrand - size, yrand - 3 * size));

         xrand = Math.round(Math.random() * size - size / 2);
         yrand = Math.round(Math.random() * size - size / 2);

         this._pointList.push(new cVector(xrand - 3 * size, yrand - size));

         xrand = Math.round(Math.random() * size - size / 2);
         yrand = Math.round(Math.random() * size - size / 2);

         this._pointList.push(new cVector(xrand - 3 * size, yrand + size));

         xrand = Math.round(Math.random() * size - size / 2);
         yrand = Math.round(Math.random() * size - size / 2);

         this._pointList.push(new cVector(xrand - size, yrand + 3 * size));

      } while (cCollider.isConvex(this) == false);
   }

   public getSize = (): number => {
      return this._size;
   }

   public static SpawnAsteroid(x: number, y: number, size: number, color: string = "white", line_width: number = 2) {
      var temp_asteroid: cAsteroid;
      for (var i: number = 0; i < asteroid_array.length; i++) {
         temp_asteroid = asteroid_array[i];
         if (temp_asteroid.active == false) {
            temp_asteroid.active = true;
            temp_asteroid.position.x = x;
            temp_asteroid.position.y = y;
            temp_asteroid.setSize( size );
            temp_asteroid.color = color;
            temp_asteroid.lineWidth = line_width;
            temp_asteroid.SetRandVelocity();
            return;
         }
      }
      asteroid_array.push(new cAsteroid(x, y, size, color, line_width));
   }
   public draw = (): void => {
      this.position.add(this.velocity);

      if (this.position.x < -this._size * 4) {
         this.position.x = 1280 + this._size * 4;
      }
      else if (this.position.x > 1280 + this._size * 4) {
         this.position.x = -4 * this._size;
      }

      if (this.position.y < -this._size * 4) {
         this.position.y = 720 + this._size * 4;
      }
      else if (this.position.y > 720 + this._size * 4) {
         this.position.y = -4 * this._size;
      }

      this.rotation += this.rotationSpeed;
      ctx.save();
      ctx.translate(this.position.x, this.position.y);
      ctx.rotate(this.rotation);
      ctx.beginPath();
      ctx.strokeStyle = this.color;
      ctx.lineWidth = this.lineWidth;

      ctx.moveTo(this._pointList[this._pointList.length - 1].x,       this._pointList[this._pointList.length - 1].y);

      for (var i: number = 0; i < this._pointList.length; i++) {
         ctx.lineTo(this._pointList[i].x, this._pointList[i].y);
      }

      ctx.closePath();
      ctx.stroke();
      ctx.restore();
   }

   public SetRandVelocity = (): void => {
      var size_sq: number = this._size * this._size;
      this.velocity.x = 80 * Math.random() / size_sq - 40 / size_sq;
      this.velocity.y = 80 * Math.random() / size_sq - 40 / size_sq;
   }

   constructor(x: number, y: number, size: number, color: string = "white", line_width: number = 2) {
      super();
      this.SetRandVelocity();
      this.position.x = x;
      this.position.y = y;
      this.setSize(size);

      this.rotationSpeed = Math.random() * 0.06 - 0.03;
      this.color = color;
      this.lineWidth = line_width;
   }
}

Source Code

The full source code is available. Below is what it looks like in action.

Part 4 - Oriented rectangle collision detection

Part 3 - Line line collision detection

Part 2 - Rectangle collision detection

Part 1 - Circle circle collision detection