Rectangle Collisions

For final version please visit
http://blog.yoz.sk/2010/11/4-000-000-rectangle-collisions-per-second/

click to run benchmarks

jozefchutka

forked:1
favorite:11
lines:394
license : MIT License
modified : 2010-11-18 18:25:13

Embed: Tweet

/*
For final version please visit 
http://blog.yoz.sk/2010/11/4-000-000-rectangle-collisions-per-second/

click to run benchmarks
*/

package
{
    import flash.display.Shape;
    import flash.display.Sprite;
    import flash.display.StageAlign;
    import flash.display.StageScaleMode;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.geom.Point;
    import flash.text.TextField;
    
    [SWF(width="465", height="465", frameRate="30", backgroundColor="#FFFFFF")]
    public class WonderflApp extends Sprite
    {
        private var shape1:Shape = new Shape();
        private var rect1:Point = new Point(0, 0);
        private var rect1Width:uint = 100;
        private var rect1Height:uint = 50;
        private var r1p1:Point;
        private var r1p2:Point;
        private var r1p3:Point;
        private var r1p4:Point;
        
        private var shape2:Shape = new Shape();
        private var rect2:Point = new Point(0, 0);
        private var rect2Width:uint = 80;
        private var rect2Height:uint = 60;
        private var r2p1:Point;
        private var r2p2:Point;
        private var r2p3:Point;
        private var r2p4:Point;
        
        private var button:Sprite = new Sprite();
        private var tf:TextField = new TextField();
        
        public function WonderflApp():void
        {
            stage.scaleMode = StageScaleMode.NO_SCALE;
            stage.align = StageAlign.TOP_LEFT;
            
            shape1.graphics.beginFill(0, 0.6);
            shape1.graphics.drawRect(rect1.x, rect1.y, rect1Width, rect1Height);
            shape1.x = 200;
            shape1.y = 100;
            shape1.rotation = 40;
            addChild(shape1);
            
            shape2.graphics.beginFill(0, 0.6);
            shape2.graphics.drawRect(rect2.x, rect2.y, rect2Width, rect2Height);
            shape2.rotation = 30;
            addChild(shape2);
            
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
            
            addChildAt(button, 0);
            button.graphics.beginFill(0, 0);
            button.graphics.drawRect(0, 0, stage.stageWidth, stage.stageHeight);
            button.addEventListener(MouseEvent.CLICK, onClick);
            
            addChild(tf);
            tf.width = stage.stageWidth;
            tf.height = 100;
            tf.y = stage.stageHeight - tf.height;
            tf.multiline = true;
        }
        
        private function onClick(event:MouseEvent):void
        {
            var count:uint = 500000;
            var i:uint = count;
            var d1:Date = new Date;
            
            while(i--)
                FastCollisions.rectangles(
                    r1p1.x, r1p1.y, r1p2.x, r1p2.y, r1p3.x, r1p3.y, r1p4.x, r1p4.y, 
                    r2p1.x, r2p1.y, r2p2.x, r2p2.y, r2p3.x, r2p3.y, r2p4.x, r2p4.y);
            
            i = count;
            
            var d2:Date = new Date;
            while(i--)
                var collision2:Boolean = shape1.hitTestObject(shape2);
            var d3:Date = new Date;
            
            tf.text = 
                "hitTestObject: " 
                    + int(1000 / (d3.time - d2.time) * count) 
                    + " tests per second"
                + "\n"
                + "FastCollisions: " 
                    + int(1000 / (d2.time - d1.time) * count) 
                    + " tests per second";
        }
        
        private function onEnterFrame(event:Event):void
        {
            graphics.clear();
            
            // rectangle 1
            shape1.rotation++;
            r1p1 = shape1.localToGlobal(rect1);
            r1p2 = shape1.localToGlobal(new Point(rect1.x + rect1Width, rect1.y));
            r1p3 = shape1.localToGlobal(new Point(rect1.x + rect1Width, rect1.y + rect1Height));
            r1p4 = shape1.localToGlobal(new Point(rect1.x, rect1.y + rect1Height));
            
            // rectangle 2
            shape2.x = mouseX;
            shape2.y = mouseY;
            r2p1 = shape2.localToGlobal(rect1);
            r2p2 = shape2.localToGlobal(new Point(rect2.x + rect2Width, rect2.y));
            r2p3 = shape2.localToGlobal(new Point(rect2.x + rect2Width, rect2.y + rect2Height));
            r2p4 = shape2.localToGlobal(new Point(rect2.x, rect2.y + rect2Height));
            
            // collision
            var collision:Boolean = FastCollisions.rectangles(
                r1p1.x, r1p1.y, r1p2.x, r1p2.y, r1p3.x, r1p3.y, r1p4.x, r1p4.y, 
                r2p1.x, r2p1.y, r2p2.x, r2p2.y, r2p3.x, r2p3.y, r2p4.x, r2p4.y);
            
            shape1.alpha = shape2.alpha = collision ? 1 : 0.5;
            
            // projections
            drawProjections(0xff0000, r1p1, r1p2, r2p1, r2p2, r2p3, r2p4);
            drawProjections(0x00ff00, r1p2, r1p3, r2p1, r2p2, r2p3, r2p4);
            drawProjections(0x0000ff, r2p1, r2p2, r1p1, r1p2, r1p3, r1p4);
            drawProjections(0xff00ff, r2p2, r2p3, r1p1, r1p2, r1p3, r1p4);
        }
        
        private function drawProjections(color:uint,
            r1p1:Point, r1p2:Point, 
            r2p1:Point, r2p2:Point,
            r2p3:Point, r2p4:Point):void
        {
            var b1:Point = new Point(r1p1.x, r1p1.y);
            var b2:Point = new Point(r1p2.x, r1p2.y);
            
            graphics.lineStyle(2, color);
            graphics.moveTo(b1.x, b1.y);
            graphics.lineTo(b2.x, b2.y);
            
            graphics.lineStyle(0, color, 0.3);
            drawProjectionLine(b1, b2, r2p1);
            drawProjectionLine(b1, b2, r2p2);
            drawProjectionLine(b1, b2, r2p3);
            drawProjectionLine(b1, b2, r2p4);
        }
        
        private function drawProjectionLine(b1:Point, b2:Point, p:Point):void
        {
            graphics.moveTo(p.x, p.y);
            graphics.lineTo(
                Math2D.projectX(b1.x, b1.y, b2.x, b2.y, p.x, p.y), 
                Math2D.projectY(b1.x, b1.y, b2.x, b2.y, p.x, p.y));
        }
    }
}

class FastCollisions
    {
        public function FastCollisions()
        {
        }
        
        public static function rectangles(
            r1p1x:Number, r1p1y:Number, r1p2x:Number, r1p2y:Number,
            r1p3x:Number, r1p3y:Number, r1p4x:Number, r1p4y:Number,
            r2p1x:Number, r2p1y:Number, r2p2x:Number, r2p2y:Number,
            r2p3x:Number, r2p3y:Number, r2p4x:Number, r2p4y:Number):Boolean
        {
            if(!isProjectedAxisCollision(r1p1x, r1p1y, r1p2x, r1p2y, 
                r2p1x, r2p1y, r2p2x, r2p2y, r2p3x, r2p3y, r2p4x, r2p4y))
                return false;
            
            if(!isProjectedAxisCollision(r1p2x, r1p2y, r1p3x, r1p3y, 
                r2p1x, r2p1y, r2p2x, r2p2y, r2p3x, r2p3y, r2p4x, r2p4y))
                return false;
            
            if(!isProjectedAxisCollision(r2p1x, r2p1y, r2p2x, r2p2y, 
                r1p1x, r1p1y, r1p2x, r1p2y, r1p3x, r1p3y, r1p4x, r1p4y))
                return false;
            
            if(!isProjectedAxisCollision(r2p2x, r2p2y, r2p3x, r2p3y, 
                r1p1x, r1p1y, r1p2x, r1p2y, r1p3x, r1p3y, r1p4x, r1p4y))
                return false;
            
            return true;
        }
        
        public static function isProjectedAxisCollision(
            b1x:Number, b1y:Number, b2x:Number, b2y:Number,
            p1x:Number, p1y:Number, p2x:Number, p2y:Number,
            p3x:Number, p3y:Number, p4x:Number, p4y:Number):Boolean
        {
            var x1:Number, x2:Number, x3:Number, x4:Number;
            var y1:Number, y2:Number, y3:Number, y4:Number;
            if(b1x == b2x)
            {
                x1 = x2 = x3 = x4 = b1x;
                y1 = p1y;
                y2 = p2y;
                y3 = p3y;
                y4 = p4y;
                
                if(b1y > b2y)
                {
                    if((y1 > b1y && y2 > b1y && y3 > b1y && y4 > b1y) || 
                        (y1 < b2y && y2 < b2y && y3 < b2y && y4 < b2y))
                        return false;
                }
                else
                {
                    if((y1 > b2y && y2 > b2y && y3 > b2y && y4 > b2y) ||
                        (y1 < b1y && y2 < b1y && y3 < b1y && y4 < b1y))
                        return false;
                }
                return true;
            }
            else if(b1y == b2y)
            {
                x1 = p1x;
                x2 = p2x;
                x3 = p3x;
                x4 = p4x;
                y1 = y2 = y3 = y4 = b1y;
            }
            else
            {
                var a:Number = (b1y - b2y) / (b1x - b2x);
                var ia:Number = 1 / a;
                var t1:Number = b2x * a - b2y;
                var t2:Number = 1 / (a + ia);
                
                x1 = (p1y + t1 + p1x * ia) * t2;
                x2 = (p2y + t1 + p2x * ia) * t2;
                x3 = (p3y + t1 + p3x * ia) * t2;
                x4 = (p4y + t1 + p4x * ia) * t2;
                
                y1 = p1y + (p1x - x1) * ia;
                y2 = p2y + (p2x - x2) * ia;
                y3 = p3y + (p3x - x3) * ia;
                y4 = p4y + (p4x - x4) * ia;
            }
            
            if(b1x > b2x)
            {
                if((x1 > b1x && x2 > b1x && x3 > b1x && x4 > b1x) ||
                    (x1 < b2x && x2 < b2x && x3 < b2x && x4 < b2x))
                    return false;
            }
            else
            {
                if((x1 > b2x && x2 > b2x && x3 > b2x && x4 > b2x) ||
                    (x1 < b1x && x2 < b1x && x3 < b1x && x4 < b1x))
                    return false;
            }
            return true;
        }
    }

class Math2D
    {
        public function Math2D()
        {
        }
        
        public static function calcA(x1:Number, y1:Number, x2:Number, y2:Number)
            :Number
        {
            return (y1 - y2) / (x1 - x2);
        }
        
        public static function projectX(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            pointX:Number, pointY:Number):Number
        {
            if(boundary1X == boundary2X)
                return boundary1X;
            if(boundary1Y == boundary2Y)
                return pointX;
            var a:Number = calcA(boundary1X, boundary1Y, boundary2X, boundary2Y);
            return (pointY - boundary2Y + boundary2X * a + pointX / a) /
                   (a + 1 / a);
        }
        
        public static function projectY(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            pointX:Number, pointY:Number):Number
        {
            if(boundary1X == boundary2X)
                return pointY;
            if(boundary1Y == boundary2Y)
                return boundary1Y;
            var a:Number = calcA(boundary1X, boundary1Y, boundary2X, boundary2Y);
            var x:Number = projectX(boundary1X, boundary1Y,
                boundary2X, boundary2Y, pointX, pointY)
            return pointY + (pointX - x) / a;
        }
        
        public static function isUnderBoundaries(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            projectedX:Number, projectedY:Number):Boolean
        {
            if(boundary1X == boundary2X)
                return projectedY <= 
                    (boundary1Y > boundary2Y ? boundary1Y : boundary2Y);
            return projectedX <= 
                (boundary1X > boundary2X ? boundary1X : boundary2X);
        }
        
        public static function isOverBoundaries(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            projectedX:Number, projectedY:Number):Boolean
        {
            if(boundary1X == boundary2X)
                return projectedY >= 
                    (boundary1Y < boundary2Y ? boundary1Y : boundary2Y);
            return projectedX >= 
                (boundary1X < boundary2X ? boundary1X : boundary2X);
        }
        
        public static function isProjectedUnderBoundaries(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            pointX:Number, pointY:Number):Boolean
        {
            var x:Number = projectX(boundary1X, boundary1Y,
                boundary2X, boundary2Y, pointX, pointY);
            var y:Number = projectY(boundary1X, boundary1Y,
                boundary2X, boundary2Y, pointX, pointY);
            return isUnderBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, x, y);
        }
        
        public static function isProjectedOverBoundaries(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            pointX:Number, pointY:Number):Boolean
        {
            var x:Number = projectX(boundary1X, boundary1Y,
                boundary2X, boundary2Y, pointX, pointY);
            var y:Number = projectY(boundary1X, boundary1Y,
                boundary2X, boundary2Y, pointX, pointY);
            return isOverBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, x, y);
        }
        
        public static function isAxisCollision(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            projected1X:Number, projected1Y:Number,
            projected2X:Number, projected2Y:Number,
            projected3X:Number, projected3Y:Number,
            projected4X:Number, projected4Y:Number):Boolean
        {
            return hasOneUnderBoundaries(boundary1X, boundary1Y,
                    boundary2X, boundary2Y,
                    projected1X, projected1Y,
                    projected2X, projected2Y,
                    projected3X, projected3Y,
                    projected4X, projected4Y) &&
                hasOneOverBoundaries(boundary1X, boundary1Y,
                    boundary2X, boundary2Y,
                    projected1X, projected1Y,
                    projected2X, projected2Y,
                    projected3X, projected3Y,
                    projected4X, projected4Y);
        }
        
        public static function isProjectedAxisCollision(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            point1X:Number, point1Y:Number,
            point2X:Number, point2Y:Number,
            point3X:Number, point3Y:Number,
            point4X:Number, point4Y:Number):Boolean
        {
            return isAxisCollision(boundary1X, boundary1Y, 
                boundary2X, boundary2Y,
                projectX(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point1X, point1Y),
                projectY(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point1X, point1Y),
                projectX(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point2X, point2Y),
                projectY(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point2X, point2Y),
                projectX(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point3X, point3Y),
                projectY(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point3X, point3Y),
                projectX(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point4X, point4Y),
                projectY(boundary1X, boundary1Y, boundary2X, boundary2Y, 
                    point4X, point4Y));
        }
        
        public static function hasOneUnderBoundaries(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            projected1X:Number, projected1Y:Number,
            projected2X:Number, projected2Y:Number,
            projected3X:Number, projected3Y:Number,
            projected4X:Number, projected4Y:Number):Boolean
        {
            if(isUnderBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected1X, projected1Y))
                return true;
            if(isUnderBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected2X, projected2Y))
                return true;
            if(isUnderBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected3X, projected3Y))
                return true;
            if(isUnderBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected4X, projected4Y))
                return true;
            return false;
        }
        
        public static function hasOneOverBoundaries(
            boundary1X:Number, boundary1Y:Number,
            boundary2X:Number, boundary2Y:Number,
            projected1X:Number, projected1Y:Number,
            projected2X:Number, projected2Y:Number,
            projected3X:Number, projected3Y:Number,
            projected4X:Number, projected4Y:Number):Boolean
        {
            if(isOverBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected1X, projected1Y))
                return true;
            if(isOverBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected2X, projected2Y))
                return true;
            if(isOverBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected3X, projected3Y))
                return true;
            if(isOverBoundaries(boundary1X, boundary1Y, 
                boundary2X, boundary2Y, projected4X, projected4Y))
                return true;
            return false;
        }
    }

Code Fullscreen

Preview Fullscreen