Continuous collision detection between two moving AABBs using Minkowski differences.

AABB.hx

package ;
import openfl.display.Sprite;

/**
 * ...
 * @author Kenton Hamaluik
 */
class AABB
{
	public var center:Vector = new Vector();
	public var extents:Vector = new Vector();
	public var min(get, never):Vector;
	public function get_min()
	{
		return new Vector(center.x - extents.x, center.y - extents.y);
	}
	public var max(get, never):Vector;
	public function get_max()
	{
		return new Vector(center.x + extents.x, center.y + extents.y);
	}
	public var size(get, never):Vector;
	public function get_size()
	{
		return new Vector(extents.x * 2, extents.y * 2);
	}
	public var velocity:Vector = new Vector(0, 0);
	public var acceleration:Vector = new Vector(0, 0);

	public function new(center:Vector, extents:Vector, ?velocity:Vector, ?acceleration:Vector) 
	{
		this.center = center;
		this.extents = extents;
		if (velocity != null)
			this.velocity = velocity;
		if (acceleration != null)
			this.acceleration = acceleration;
	}
	
	public function draw(container:Sprite, colour:Int = 0xffffff)
	{
		container.graphics.beginFill(colour, 0.5);
		container.graphics.drawRect(min.x, min.y, size.x, size.y);
		container.graphics.endFill();
	}
	
	public function minkowskiDifference(other:AABB):AABB
	{
		var topLeft:Vector = min - other.max;
		var fullSize:Vector = size + other.size;
		return new AABB(topLeft + (fullSize / 2), fullSize / 2);
	}
	
	public function closestPointOnBoundsToPoint(point:Vector):Vector
	{
		// test x first
		var minDist:Float = Math.abs(point.x - min.x);
		var boundsPoint:Vector = new Vector(min.x, point.y);
		if (Math.abs(max.x - point.x) < minDist)
		{
			minDist = Math.abs(max.x - point.x);
			boundsPoint = new Vector(max.x, point.y);
		}
		if (Math.abs(max.y - point.y) < minDist)
		{
			minDist = Math.abs(max.y - point.y);
			boundsPoint = new Vector(point.x, max.y);
		}
		if (Math.abs(min.y - point.y) < minDist)
		{
			minDist = Math.abs(min.y - point.y);
			boundsPoint = new Vector(point.x, min.y);
		}
		return boundsPoint;
	}
	
	// taken from https://github.com/pgkelley4/line-segments-intersect/blob/master/js/line-segments-intersect.js
	// returns the point where they intersect (if they intersect)
	// returns null if they don't intersect
	private function getRayIntersectionFractionOfFirstRay(originA:Vector, endA:Vector, originB:Vector, endB:Vector):/*Vector*/Float
	{
		var r:Vector = endA - originA;
		var s:Vector = endB - originB;
		
		var numerator:Float = (originB - originA) * r;
		var denominator:Float = r * s;
		
		if (numerator == 0 && denominator == 0)
		{
			// the lines are co-linear
			// check if they overlap
			/*return	((originB.x - originA.x < 0) != (originB.x - endA.x < 0) != (endB.x - originA.x < 0) != (endB.x - endA.x < 0)) || 
					((originB.y - originA.y < 0) != (originB.y - endA.y < 0) != (endB.y - originA.y < 0) != (endB.y - endA.y < 0));*/
			return Math.POSITIVE_INFINITY;
		}
		if (denominator == 0)
		{
			// lines are parallel
			return Math.POSITIVE_INFINITY;
		}
		
		var u:Float = numerator / denominator;
		var t:Float = ((originB - originA) * s) / denominator;
		if ((t >= 0) && (t <= 1) && (u >= 0) && (u <= 1))
		{
			//return originA + (r * t);
			return t;
		}
		return Math.POSITIVE_INFINITY;
	}
	
	public function getRayIntersectionFraction(origin:Vector, direction:Vector):Float
	{
		var end:Vector = origin + direction;
		
		var minT:Float = getRayIntersectionFractionOfFirstRay(origin, end, new Vector(min.x, min.y), new Vector(min.x, max.y));
		var x:Float;
		x = getRayIntersectionFractionOfFirstRay(origin, end, new Vector(min.x, max.y), new Vector(max.x, max.y));
		if (x < minT)
			minT = x;
		x = getRayIntersectionFractionOfFirstRay(origin, end, new Vector(max.x, max.y), new Vector(max.x, min.y));
		if (x < minT)
			minT = x;
		x = getRayIntersectionFractionOfFirstRay(origin, end, new Vector(max.x, min.y), new Vector(min.x, min.y));
		if (x < minT)
			minT = x;
		
		// ok, now we should have found the fractional component along the ray where we collided
		return minT;
	}
}

Main.hx

package ;

import flash.display.Sprite;
import flash.events.Event;
import flash.Lib;
import haxe.Timer;
import openfl.events.KeyboardEvent;
import openfl.events.MouseEvent;
import openfl.text.TextField;
import openfl.text.TextFormat;
import openfl.ui.Keyboard;

/**
 * ...
 * @author Kenton Hamaluik
 */

class Main extends Sprite 
{
	var inited:Bool;
	var drawContainer:Sprite = new Sprite();
	
	var v100Text:TextField;
	var v500Text:TextField;
	var v1000Text:TextField;
	var v10000Text:TextField;
	
	var boxA:AABB;
	var boxB:AABB;
	
	var lastTime:Float = 0;

	/* ENTRY POINT */
	
	function resize(e) 
	{
		if (!inited) init();
		// else (resize or orientation change)
	}
	
	var spr:Sprite = new Sprite();
	
	function init() 
	{
		if (inited) return;
		inited = true;

		this.addChild(drawContainer);
		
		// initialize the boxes
		boxA = new AABB(new Vector(stage.stageWidth / 2, 0), new Vector(10, 10), new Vector(0, 100), new Vector(0, 1000));
		boxB = new AABB(new Vector(stage.stageWidth / 2, 450), new Vector(stage.stageWidth / 2 - 50, 25), new Vector(0, 0));
		
		// draw text to let things reset
		v100Text = new TextField();
		v100Text.defaultTextFormat = new TextFormat(null, 12, 0xffffff);
		v100Text.embedFonts = false;
		v100Text.text = "Reset, v = 100";
		v100Text.x = 10;
		v100Text.y = 10;
		v100Text.mouseEnabled = false;
		v100Text.width = v100Text.textWidth + 5;
		v100Text.height = v100Text.textHeight + 5;
		v100Text.background = true;
		v100Text.backgroundColor = 0x555555;
		drawContainer.addChild(v100Text);
		
		v500Text = new TextField();
		v500Text.defaultTextFormat = new TextFormat(null, 12, 0xffffff);
		v500Text.embedFonts = false;
		v500Text.text = "Reset, v = 500";
		v500Text.x = 10;
		v500Text.y = 20 + v500Text.textHeight;
		v500Text.mouseEnabled = false;
		v500Text.width = v500Text.textWidth + 5;
		v500Text.height = v500Text.textHeight + 5;
		v500Text.background = true;
		v500Text.backgroundColor = 0x555555;
		drawContainer.addChild(v500Text);
		
		v1000Text = new TextField();
		v1000Text.defaultTextFormat = new TextFormat(null, 12, 0xffffff);
		v1000Text.embedFonts = false;
		v1000Text.text = "Reset, v = 1000";
		v1000Text.x = 10;
		v1000Text.y = 30 + v100Text.textHeight + v500Text.textHeight;
		v1000Text.mouseEnabled = false;
		v1000Text.width = v1000Text.textWidth + 5;
		v1000Text.height = v1000Text.textHeight + 5;
		v1000Text.background = true;
		v1000Text.backgroundColor = 0x555555;
		drawContainer.addChild(v1000Text);
		
		v10000Text = new TextField();
		v10000Text.defaultTextFormat = new TextFormat(null, 12, 0xffffff);
		v10000Text.embedFonts = false;
		v10000Text.text = "Reset, v = 10000";
		v10000Text.x = 10;
		v10000Text.y = 40 + v100Text.textHeight + v500Text.textHeight + v1000Text.textHeight;
		v10000Text.mouseEnabled = false;
		v10000Text.width = v10000Text.textWidth + 5;
		v10000Text.height = v10000Text.textHeight + 5;
		v10000Text.background = true;
		v10000Text.backgroundColor = 0x555555;
		drawContainer.addChild(v10000Text);
		
		// add event listeners and begin!
		stage.addEventListener(Event.ENTER_FRAME, onFrame);
		stage.addEventListener(MouseEvent.CLICK, onClick);
		stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyPressed);
		stage.addEventListener(KeyboardEvent.KEY_UP, onKeyReleased);
		lastTime = Timer.stamp();
	}
	
	private inline function ptInTextField(p:Vector, textField:TextField):Bool
	{
		return (p.x >= textField.x && p.x <= textField.x + textField.width && p.y >= textField.y && p.y <= textField.y + textField.height);
	}
	
	private var rightDown:Bool = false;
	private var leftDown:Bool = false;
	function onKeyPressed(event:KeyboardEvent):Void
	{
		if (event.keyCode == Keyboard.W)
		{
			boxA.velocity.y = -400;
			boxA.center.y -= 1;
		}
		else if (event.keyCode == Keyboard.A)
		{
			leftDown = true;
		}
		else if (event.keyCode == Keyboard.D)
		{
			rightDown = true;
		}
	}
	function onKeyReleased(event:KeyboardEvent):Void
	{
		if (event.keyCode == Keyboard.A)
		{
			leftDown = false;
		}
		else if (event.keyCode == Keyboard.D)
		{
			rightDown = false;
		}
	}
	
	function onClick(event:MouseEvent):Void
	{
		if (ptInTextField(new Vector(event.stageX, event.stageY), v100Text))
		{
			boxA.center = new Vector(stage.stageWidth / 2, 0);
			boxA.velocity = new Vector(0, 100);
			boxB.center = new Vector(stage.stageWidth / 2, 450);
			boxB.velocity = new Vector(0, 0);
		}
		else if (ptInTextField(new Vector(event.stageX, event.stageY), v500Text))
		{
			boxA.center = new Vector(stage.stageWidth / 2, 0);
			boxA.velocity = new Vector(0, 500);
			boxB.center = new Vector(stage.stageWidth / 2, 450);
			boxB.velocity = new Vector(0, 0);
		}
		else if (ptInTextField(new Vector(event.stageX, event.stageY), v1000Text))
		{
			boxA.center = new Vector(stage.stageWidth / 2, 0);
			boxA.velocity = new Vector(0, 1000);
			boxB.center = new Vector(stage.stageWidth / 2, 450);
			boxB.velocity = new Vector(0, 0);
		}
		else if (ptInTextField(new Vector(event.stageX, event.stageY), v10000Text))
		{
			boxA.center = new Vector(stage.stageWidth / 2, 0);
			boxA.velocity = new Vector(0, 10000);
			boxB.center = new Vector(stage.stageWidth / 2, 450);
			boxB.velocity = new Vector(0, 0);
		}
	}
	
	function onFrame(event:Event):Void
	{
		var t:Float = Timer.stamp();
		var dt:Float = t - lastTime;
		lastTime = t;
		
		// deal with side-to-side motion
		var moveV:Float = 100;
		if (rightDown && !leftDown)
			boxA.velocity.x = moveV;
		else if (!rightDown && leftDown)
			boxA.velocity.x = -moveV;
		else
			boxA.velocity.x = 0;
		
		// deal with acceleration
		boxA.velocity += boxA.acceleration * dt;
		boxB.velocity += boxB.acceleration * dt;
		
		// construct the relative velocity ray
		var rvRayColour:Int = 0xff0000;
		var rvRay:Vector = (boxA.velocity - boxB.velocity) * dt;
		
		// see if there is already a collision
		var boxAColour:Int = 0xff0000;
		var rvRayIntersection:Vector = null;
		var md:AABB = boxB.minkowskiDifference(boxA);
		var penetrationVector:Vector = null;
		var doMove:Bool = true;
		if (md.min.x <= 0 &&
			md.max.x >= 0 &&
			md.min.y <= 0 &&
			md.max.y >= 0)
		{
			// collision is occurring!
			boxAColour = 0x00ff00;
			
			// find the penetration depth
			penetrationVector = md.closestPointOnBoundsToPoint(Vector.zero);
			
			// offset the box to make sure it's not penetrating
			boxA.center += penetrationVector;
			
			// zero out the box's velocity in the direction of the penetration
			if (!penetrationVector.isZero())
			{
				// zero the velocity in the normal direction
				var tangent:Vector = penetrationVector.normalized.tangent;
				boxA.velocity = Vector.dotProduct(boxA.velocity, tangent) * tangent;
				boxB.velocity = Vector.dotProduct(boxB.velocity, tangent) * tangent;
			}
		}
		else
		{
			// see if there WILL be a collision
			var intersectFraction:Float = md.getRayIntersectionFraction(Vector.zero, rvRay);
			if (intersectFraction < Math.POSITIVE_INFINITY)
			{
				// yup, there WILL be a collision this frame
				rvRayColour = 0x00ff00;
				rvRayIntersection = rvRay * intersectFraction;
				
				// move the boxes appropriately
				boxA.center += boxA.velocity * dt * intersectFraction;
				boxB.center += boxB.velocity * dt * intersectFraction;
				doMove = false;
				
				// zero out the normal of the collision
				var nrvRay:Vector = rvRay.normalized;
				var tangent:Vector = new Vector( -nrvRay.y, nrvRay.x);
				boxA.velocity = Vector.dotProduct(boxA.velocity, tangent) * tangent;
				boxB.velocity = Vector.dotProduct(boxB.velocity, tangent) * tangent;
			}
		}
		
		if (doMove)
		{
			boxA.center += boxA.velocity * dt;
			boxB.center += boxB.velocity * dt;
		}
		
		// clear the graphics
		drawContainer.graphics.clear();
		
		// draw the origin point
		drawContainer.graphics.beginFill(0xffffff);
		drawContainer.graphics.drawCircle(stage.stageWidth / 2, stage.stageHeight / 2, 2);
		drawContainer.graphics.endFill();
		
		// draw the md box (moved to the fake origin)
		var origin:Vector = new Vector(stage.stageWidth / 2, stage.stageHeight / 2);
		md.center += origin;
		md.draw(drawContainer, 0x0000ff);
		
		// draw the intersection point
		if (rvRayIntersection != null)
		{
			drawContainer.graphics.beginFill(0xff00ff);
			rvRayIntersection += origin;
			drawContainer.graphics.drawCircle(rvRayIntersection.x, rvRayIntersection.y, 2);
			drawContainer.graphics.endFill();
		}
		
		// draw the actual boxes
		boxB.draw(drawContainer);
		boxA.draw(drawContainer, boxAColour);
		
		// draw the relative velocity ray
		rvRay.draw(drawContainer, origin, rvRayColour);
	}

	/* SETUP */

	public function new() 
	{
		super();	
		addEventListener(Event.ADDED_TO_STAGE, added);
	}

	function added(e) 
	{
		removeEventListener(Event.ADDED_TO_STAGE, added);
		stage.addEventListener(Event.RESIZE, resize);
		#if ios
		haxe.Timer.delay(init, 100); // iOS 6
		#else
		init();
		#end
	}
	
	public static function main() 
	{
		// static entry point
		Lib.current.stage.align = flash.display.StageAlign.TOP_LEFT;
		Lib.current.stage.scaleMode = flash.display.StageScaleMode.NO_SCALE;
		Lib.current.addChild(new Main());
	}
}

Vector.hx

package ;
import openfl.display.Sprite;

/**
 * ...
 * @author Kenton Hamaluik
 */
private class VectorRaw
{
	public var x:Float = 0;
	public var y:Float = 0;

	public function new(x:Float = 0, y:Float = 0) 
	{
		this.x = x;
		this.y = y;
	}
}

@:forward(x, y)
abstract Vector(VectorRaw) from VectorRaw to VectorRaw
{
	public function new(x:Float = 0, y:Float = 0) 
	{
		this = new VectorRaw(x, y);
	}
	
	public static var zero(get, never):Vector;
	private static inline function get_zero():Vector
	{
		return new Vector(0, 0);
	}
	
	public var length(get, never):Float;
	private inline function get_length():Float
	{
		return Math.sqrt((this.x * this.x) + (this.y * (this.y)));
	}
	
	public var normalized(get, never):Vector;
	private inline function get_normalized():Vector
	{
		var l:Float = length;
		if (l != 0)
			return new Vector(this.x / l, this.y / l);
		return new Vector(0, 0);
	}
	
	public var tangent(get, never):Vector;
	private inline function get_tangent():Vector
	{
		return new Vector(-this.y, this.x);
	}
	
	public static inline function squareDistance(a:Vector, b:Vector):Float
	{
		return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
	}
	
	public inline function isZero():Bool
	{
		return this.x == 0 && this.y == 0;
	}
	
	@:op(A * B)
	@:commutative
	public static inline function multiplyScalar(a:Vector, s:Float)
	{
		return new Vector(a.x * s, a.y * s);
	}
	
	@:op(A / B)
	public static inline function divideByScalar(a:Vector, s:Float)
	{
		return new Vector(a.x / s, a.y / s);
	}
	
	@:op(A + B)
	public static inline function addVectors(a:Vector, b:Vector)
	{
		return new Vector(a.x + b.x, a.y + b.y);
	}
	
	@:op(A - B)
	public static inline function subtractVectors(a:Vector, b:Vector)
	{
		return new Vector(a.x - b.x, a.y - b.y);
	}
	
	@:op(A * B)
	public static inline function crossProduct(a:Vector, b:Vector):Float
	{
		return (a.x * b.y - a.y * b.x);
	}
	
	public static inline function dotProduct(a:Vector, b:Vector):Float
	{
		return a.x * b.x + a.y * b.y;
	}
	
	public function toString():String
	{
		return "[" + this.x + ", " + this.y + "]";
	}
	
	public function draw(container:Sprite, origin:Vector, colour:Int = 0xffffff)
	{
		container.graphics.moveTo(origin.x, origin.y);
		container.graphics.lineStyle(1, colour, 1);
		container.graphics.lineTo(origin.x + this.x, origin.y + this.y);
	}
}