Skip to content

Instantly share code, notes, and snippets.

@hamaluik
Created October 6, 2014 05:38
Show Gist options
  • Save hamaluik/e69f96e253a190273bf0 to your computer and use it in GitHub Desktop.
Save hamaluik/e69f96e253a190273bf0 to your computer and use it in GitHub Desktop.
Continuous collision detection between two moving AABBs using Minkowski differences.
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;
}
}
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());
}
}
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment