Quadtree detects collision inaccurately

Question

Hi,

I am trying to implement a quadtree of rectangles (instead of points) to be used for collision detection.

For some reason, overlap/intersection/collision is not always detected. I suspect this has something to do with the way an inserted collider looks for nearby colliders (see the "COLLISION A" and "COLLISION B" sections of Quadtree.as). Can anyone identify why this happens?

Below is my code for the quadtree, and several other classes that, when compiled together, will show you what I mean when I say that the "quadtree" is "inaccurate". You only really need to look at Quadtree.as, but compiling it together with the other classes should help you understand my problem.

Thanks!

Quadtree.as:

package
{
    import flash.geom.Rectangle;
    import flash.display.Sprite;

    public class Quadtree
    {
        private var root:Node;

        public function Quadtree( width:Number, height:Number, depth:int )
        {
            root = new Node( 0, 0, width, height, depth );
        }

        public function insert( collider:Collider ) : void
        {
            var current:Node = root;
            var colliderRectangle:Rectangle = collider.colliderRectangle;

            // Insertion is not recursive, to reduce function calls and make the tree faster.
            // A break is called when the collider is inserted into a particular node.
            while( true )
            {
                // BEGIN COLLISION A
                // Collide the collider being inserted with the colliders already present in the tree.
                // At least, it will see all of the colliders it passes by as it goes down.
                var colliders:Array = current.colliders;
                var max:int = colliders.length;
                for( var i:int = 0; i < max; i++ )
                {
                    // Narrow collision detection (and response) is performed by the Collider.collide() function.
                    var other:Collider = colliders[i];
                    collider.collide( other );
                    other.collide( collider );
                }
                // END COLLISION A

                // If the current node is at the maximum depth (lower is higher),
                // insert the collider into the current node.
                if( current.depth == 0 )
                {
                    current.colliders.push( collider );
                    break;
                }

                // Determine which quadrants the collider intersects with.
                var currentX:Number = current.x;
                var currentY:Number = current.y;
                var halfWidth:Number = current.halfWidth;
                var halfHeight:Number = current.halfHeight;
                var onLeft:Boolean = ( currentX + current.width ) - colliderRectangle.right >= halfWidth;
                var onTop:Boolean = ( currentY + current.height ) - colliderRectangle.bottom >= halfHeight;
                var onRight:Boolean = colliderRectangle.left - currentX >= halfWidth;
                var onBottom:Boolean = colliderRectangle.top - currentY >= halfHeight;

                // If the collider is not completely contained in one quadrant of the current node,
                // insert the collider into the current node, then check if the collider collides with
                // any of the colliders in the descendants of the current node (see COLLISION B).
                if( ( !onTop && !onBottom ) || ( !onLeft && !onRight ) )
                {
                    current.colliders.push( collider );

                    // BEGIN COLLISION B
                    var tl:Node = current.tl;
                    var tr:Node = current.tr;
                    var bl:Node = current.bl;
                    var br:Node = current.br;
                    if( tl )
                    {
                        tl.collideDescendants( collider );
                    }
                    if( tr )
                    {
                        tr.collideDescendants( collider );
                    }
                    if( bl )
                    {
                        bl.collideDescendants( collider );
                    }
                    if( br )
                    {
                        br.collideDescendants( collider );
                    }
                    // END COLLISION B

                    break;
                }
                // If the collider does not span more than one quadrant, determine which of the quadrants contain it.
                else if( onTop && onLeft )
                {
                    if( !current.tl )
                    {
                        current.tl = new Node( currentX, currentY, halfWidth, halfHeight, current.depth );
                    }
                    current = current.tl;
                }
                else if( onTop && onRight )
                {
                    if( !current.tr )
                    {
                        current.tr = new Node( currentX + halfWidth, currentY, halfWidth, halfHeight, current.depth );
                    }
                    current = current.tr;
                }
                else if( onBottom && onLeft )
                {
                    if( !current.bl )
                    {
                        current.bl = new Node( currentX, currentY + halfHeight, halfWidth, halfHeight, current.depth );
                    }
                    current = current.bl;
                }
                else if( onBottom && onRight )
                {
                    if( !current.br )
                    {
                        current.br = new Node( currentX + halfWidth, currentY + halfHeight, halfWidth, halfHeight, current.depth );
                    }
                    current = current.br;
                }
            }
        }

        public function clear() : void
        {
            root.clear();
        }
    }
}

import flash.display.Sprite;
import flash.geom.Rectangle;

class Node
{
    public var extent:Rectangle;
    public var tl:Node;
    public var tr:Node;
    public var bl:Node;
    public var br:Node;
    public var colliders:Array;
    public var depth:int;

    public var x:Number;
    public var y:Number;
    public var width:Number;
    public var height:Number;
    public var halfWidth:Number;
    public var halfHeight:Number;

    public function Node( x:Number, y:Number, width:Number, height:Number, depth:int )
    {
        extent = new Rectangle( x, y, width, height );
        halfWidth = width * 0.5;
        halfHeight = height * 0.5;
        this.depth = depth - 1;
        colliders = [];

        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
    }

    public function collideDescendants( collider:Collider ) : void
    {
        var max:int = 0;
        var other:Collider;
        for( var i:int = 0; i < max; i++ )
        {
            other = colliders[i];
            collider.collide( other );
            other.collide( collider );
        }

        if( depth == 0 )
        {
            return;
        }

        var colliderRectangle:Rectangle = collider.colliderRectangle;
        var left:Number = colliderRectangle.left;
        var right:Number = colliderRectangle.right;
        var top:Number = colliderRectangle.top;
        var bottom:Number = colliderRectangle.bottom;
        if( tl && !( bottom < tl.y || tl.y + tl.height < top || right < tl.x || tl.x + width < left ) )
        {
            tl.collideDescendants( collider );
        }
        if( tr && !( bottom < tr.y || tr.y + tr.height < top || right < tr.x || tr.x + width < left ) )
        {
            tr.collideDescendants( collider );
        }
        if( bl && !( bottom < bl.y || bl.y + bl.height < top || right < bl.x || bl.x + width < left ) )
        {
            bl.collideDescendants( collider );
        }
        if( br && !( bottom < br.y || br.y + br.height < top || right < br.x || br.x + width < left ) )
        {
            br.collideDescendants( collider );
        }
    }

    public function clear() : void
    {
        colliders.splice( 0, colliders.length );

        if( tl )
        {
            tl.clear();
        }
        if( tr )
        {
            tr.clear();
        }
        if( bl )
        {
            bl.clear();
        }
        if( br )
        {
            br.clear();
        }
    }
}

Main.as:

package 
{
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.text.TextField;
    import flash.text.TextFormat;
    public class Main extends Sprite 
    {
        public function Main()
        {
            if (stage) init();
            else addEventListener( Event.ADDED_TO_STAGE, init );
        }
        private function init( e:Event = null ) : void 
        {
            removeEventListener( Event.ADDED_TO_STAGE, init );

            var objects:Array = [];
            var quadtree:Quadtree = new Quadtree( 640, 480, 5 );
            var max:int = 50;
            for( var i:int = 0; i < max; i++ )
            {
                var object:TestObject = new TestObject();
                addChild( object );
                objects.push( object );
            }

            var bruteMsg:String = "Using BRUTE FORCE! Click to switch to QUADTREE";
            var quadMsg:String = "Using QUADTREE! Click to switch to BRUTE FORCE";

            var text:TextField = new TextField();
            text.text = quadMsg;
            text.selectable = false;
            text.width = 300;
            text.defaultTextFormat = new TextFormat( "Arial" );
            text.setTextFormat( text.defaultTextFormat );
            addChild( text );

            var last:Date = new Date();
            var useQuadtree:Boolean = true;

            addEventListener( Event.ENTER_FRAME, function( f:Event ) : void {
                var now:Date = new Date();
                var deltaTime:Number = ( now.getTime() - last.getTime() ) * 0.001;
                last = now;
                for( i = 0; i < max; i++ )
                {
                    object = objects[i];
                    object.update( deltaTime );
                }
                if( useQuadtree )
                {
                    quadtree.clear();
                    for( i = 0; i < max; i++ )
                    {
                        object = objects[i];
                        quadtree.insert( object.collider );
                    }
                }
                else
                {
                    for( i = 0; i < max; i++ )
                    {
                        var a:TestObject = objects[i];
                        for( var j:int = i + 1; j < max; j++ )
                        {
                            var b:TestObject = objects[j];
                            a.collider.collide( b.collider );
                            b.collider.collide( a.collider );
                        }
                    }
                }
            } );
            stage.addEventListener( MouseEvent.CLICK, function( f:Event ) : void {
                text.text = useQuadtree ? bruteMsg : quadMsg;
                useQuadtree = !useQuadtree;
            } );
        }
    }
}

TestObject.as:

package
{
    import flash.display.Sprite;
    import flash.geom.Point;

    public class TestObject extends Sprite
    {
        private static const WIDTH:int = 20;
        private static const HEIGHT:int = 30;
        private static const SPEED:Number = 100;
        private static const CANVAS_WIDTH:Number = 640;
        private static const CANVAS_HEIGHT:Number = 480;
        public var direction:Point;
        public var collider:TestCollider;
        public function TestObject()
        {
            super();
            graphics.lineStyle( 1, 0x0000FF );
            graphics.drawRect( 0, 0, WIDTH, HEIGHT );
            x = Math.random() * ( CANVAS_WIDTH - WIDTH );
            y = Math.random() * ( CANVAS_HEIGHT - HEIGHT );
            direction = new Point( Math.random() - 0.5, Math.random() - 0.5 );
            direction.normalize( 1 );
            collider = new TestCollider( this, x, y, width, height );
        }
        public function update( deltaTime:Number ) : void
        {
            var displacement:Number = SPEED * deltaTime;
            x = x + direction.x * displacement;
            y = y + direction.y * displacement;

            if( x < 0 )
            {
                x = 0;
                direction.x *= -1;
            }
            else if( x + WIDTH > CANVAS_WIDTH )
            {
                x = CANVAS_WIDTH - WIDTH;
                direction.x *= -1;
            }
            if( y < 0 )
            {
                y = 0;
                direction.y *= -1;
            }
            else if( y + HEIGHT > CANVAS_HEIGHT )
            {
                y = CANVAS_HEIGHT - HEIGHT;
                direction.y *= -1;
            }

            collider.colliderRectangle.x = x;
            collider.colliderRectangle.y = y;
        }
    }
}

Collider.as:

package  
{
    import flash.geom.Rectangle;

    public class Collider
    {
        virtual public function get colliderRectangle() : Rectangle { return null; };
        virtual public function collide( collider:Collider ) : void { /* NARROW COLLISION DETECTION AND COLLISION RESPONSE CODE HERE */ }
    }
}

TestCollider.as:

package  
{
    import flash.geom.Rectangle;

    public class TestCollider extends Collider
    {
        private var rectangle:Rectangle;
        private var parent:TestObject;

        public function TestCollider( parent:TestObject, x:Number, y:Number, width:Number, height:Number )
        {
            this.parent = parent;
            rectangle = new Rectangle( x, y, width, height );
        }

        override public function get colliderRectangle() : Rectangle
        {
            return rectangle;
        }

        override public function collide( collider:Collider ) : void 
        {
            var otherRect:Rectangle = collider.colliderRectangle;
            if( rectangle.intersects( otherRect ) )
            {
                var intersection:Rectangle = rectangle.intersection( otherRect );
                if( intersection.width < intersection.height )
                {
                    parent.x += intersection.width * 0.5 * ( rectangle.x < otherRect.x ? -1 : 1 );
                }
                else
                {
                    parent.y += intersection.height * 0.5 * ( rectangle.y < otherRect.y ? -1 : 1 );
                }
                parent.direction.x *= ( ( parent.direction.x > 0 && otherRect.x > rectangle.x ) || ( parent.direction.x < 0 && otherRect.x < rectangle.x ) ? -1 : 1 );
                parent.direction.y *= ( ( parent.direction.y > 0 && otherRect.y > rectangle.y ) || ( parent.direction.y < 0 && otherRect.y < rectangle.y ) ? -1 : 1 );
            }
        }
    }
}

Answer 1

This is such an embarrassing and clumsy mistake. If you look at Node.collideDescendants() under Quadtree.as, you will notice that the first line is

var max:int = 0;

When it should be

var max:int = colliders.length;

No wonder that a newly inserted collider will not be able to see the colliders that belong to the nodes below it (nodes that belong to the descendants of the node this collider was inserted into).

Embarassing, really.