Created
October 6, 2014 05:38
-
-
Save hamaluik/e69f96e253a190273bf0 to your computer and use it in GitHub Desktop.
Continuous collision detection between two moving AABBs using Minkowski differences.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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()); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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