DogTree -- A collision quad tree for flixel

[DogInLake]

Note: New Version: Last updated on 30th of July

Code:

//Author: Johannes Pauw
//Released under the MIT license (to match Adam Atomic, since this quadtree is built specifically for flixel).
//Go look the license up on the internets if you want specifics, but the basic idea is that you can do absolutely anything
//you want with it, without restriction, for commercial or private use.

package com.doginlake.quadtree
{
import com.adamatomic.flixel.FlxArray;
import com.adamatomic.flixel.FlxCore;
import com.adamatomic.flixel.FlxG;
import com.adamatomic.flixel.FlxSprite;

//@desc The primary node class for the quadtree
public class DogTree
{
private var x:Number;
private var y:Number;
private var width:Number;
private var height:Number;
private var NE:DogTree;
private var NW:DogTree;
private var SE:DogTree;
private var SW:DogTree;
private var parent:DogTree;
private var objects:FlxArray;
private var boundingArray:FlxArray;
private var removalArray:FlxArray;

public function DogTree(depthLeft:int, x:Number, y:Number, width:Number, height:Number, parent:DogTree = null, boundingArray:Array = null)
{
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.parent = parent;
this.removalArray = new FlxArray();
if (parent == null)
{
this.boundingArray = new FlxArray();
}
this.objects = new FlxArray();
depthLeft--;
if (depthLeft > 0)
{
NW = new DogTree(depthLeft, x, y, width / 2, height / 2, this, boundingArray);
NE = new DogTree(depthLeft, x + width / 2, y, width / 2, height / 2, this, boundingArray);
SW = new DogTree(depthLeft, x, y + height / 2, width / 2, height / 2, this, boundingArray);
SE = new DogTree(depthLeft, x + width / 2, y + height / 2, width / 2, height / 2, this, boundingArray);
}
}

//Check if this node has children. If it does, see if the object will fit completely within the bounds of one of the children. If not, add to this node.
public function add(core:FlxCore):void
{
if (NE != null)
{
if (core.x > NW.x && core.y > NW.y && core.x + core.width < NW.x + NW.width && core.y + core.height < NW.y + NW.height)
{
NW.add(core);
}
else if (core.x > NE.x && core.y > NE.y && core.x + core.width < NE.x + NE.width && core.y + core.height < NE.y + NE.height)
{
NE.add(core);
}
else if (core.x > SW.x && core.y > SW.y && core.x + core.width < SW.x + SW.width && core.y + core.height < SW.y + SW.height)
{
SW.add(core);
}
else if (core.x > SE.x && core.y > SE.y && core.x + core.width < SE.x + SE.width && core.y + core.height < SE.y + SE.height)
{
SE.add(core);
}
else
{
objects.add(core);
core._dogNode = this;
}
}
else
{
objects.add(core);
core._dogNode = this;
}
}

//Check if this object needs to go to a new node
public function update(core:FlxCore):void
{
if (NE != null)
{
if (core.x > NW.x && core.y > NW.y && core.x + core.width < NW.x + NW.width && core.y + core.height < NW.y + NW.height)
{
objects.remove(core, true);
NW.add(core);
}
else if (core.x > NE.x && core.y > NE.y && core.x + core.width < NE.x + NE.width && core.y + core.height < NE.y + NE.height)
{
objects.remove(core, true);
NE.add(core);
}
else if (core.x > SW.x && core.y > SW.y && core.x + core.width < SW.x + SW.width && core.y + core.height < SW.y + SW.height)
{
objects.remove(core, true);
SW.add(core);
}
else if (core.x > SE.x && core.y > SE.y && core.x + core.width < SE.x + SE.width && core.y + core.height < SE.y + SE.height)
{
objects.remove(core, true);
SE.add(core);
}
else if (core.x > x && core.y > y && core.x + core.width < x + width && core.y + core.height < y + height)
{
}
else if (parent != null)
{
objects.remove(core, true);
parent.secondaryUpdate(core);
}
}
else if (core.x > x && core.y > y && core.x + core.width < x + width && core.y + core.height < y + height)
{
}
else if (parent != null)
{
objects.remove(core, true);
parent.secondaryUpdate(core);
}
}


public function secondaryUpdate(core:FlxCore):void
{
if (NE != null)
{
if (core.x > NW.x && core.y > NW.y && core.x + core.width < NW.x + NW.width && core.y + core.height < NW.y + NW.height)
{
NW.add(core);
}
else if (core.x > NE.x && core.y > NE.y && core.x + core.width < NE.x + NE.width && core.y + core.height < NE.y + NE.height)
{
NE.add(core);
}
else if (core.x > SW.x && core.y > SW.y && core.x + core.width < SW.x + SW.width && core.y + core.height < SW.y + SW.height)
{
SW.add(core);
}
else if (core.x > SE.x && core.y > SE.y && core.x + core.width < SE.x + SE.width && core.y + core.height < SE.y + SE.height)
{
SE.add(core);
}
else if (core.x > x && core.y > y && core.x + core.width < x + width && core.y + core.height < y + height)
{
core._dogNode = this;
objects.add(core);
}
else
{
if (parent != null)
{
parent.secondaryUpdate(core);
}
else
{
core._dogNode = this;
objects.add(core);
}
}
}
else if (core.x > x && core.y > y && core.x + core.width < x + width && core.y + core.height < y + height)
{
core._dogNode = this;
objects.add(core);
}
else
{
if (parent != null)
{
parent.secondaryUpdate(core);
}
else
{
core._dogNode = this;
objects.add(core);
}
}
}

//Find objects that may collide with the inputted variables.
public function findBoundingCollisions(boundingX:Number, boundingY:Number, boundingHeight:Number, boundingWidth:Number, array:FlxArray = null):FlxArray
{
var core:FlxCore;
if (array == null)
{
boundingArray.clear();
array = boundingArray;
}
if (objects.length > 0)
{
for (var i:int = 0; i < objects.length; i++)
{
core = objects[i] as FlxCore;
if (!core.dead)
{
array.add(core);
}
}
}
if (NE != null)
{
if (!(boundingX + boundingWidth < NW.x || boundingX > NW.x + NW.width || boundingY + boundingHeight < NW.y || boundingY > NW.y + NW.height))
{
array = NW.findBoundingCollisions(boundingX, boundingY, boundingHeight, boundingWidth, array);
}
if (!(boundingX + boundingWidth < NE.x || boundingX > NE.x + NE.width || boundingY + boundingHeight < NE.y || boundingY > NE.y + NE.height))
{
array = NE.findBoundingCollisions(boundingX, boundingY, boundingHeight, boundingWidth, array);
}
if (!(boundingX + boundingWidth < SW.x || boundingX > SW.x + SW.width || boundingY + boundingHeight < SW.y || boundingY > SW.y + SW.height))
{
array = SW.findBoundingCollisions(boundingX, boundingY, boundingHeight, boundingWidth, array);
}
if (!(boundingX + boundingWidth < SE.x || boundingX > SE.x + SE.width || boundingY + boundingHeight < SE.y || boundingY > SE.y + SE.height))
{
array = SE.findBoundingCollisions(boundingX, boundingY, boundingHeight, boundingWidth, array);
}
}
return array;
}

//Check if this single FlxCore object collides with any of the objects in the tree
public function singleCollision(core:FlxSprite, Collide:Function = null ):void
{
FlxG.collideArray(findBoundingCollisions(core.x, core.y, core.height, core.width), core, Collide);
}

//Check if anything in this array of FlxCore objects collides with any of the objects in the tree
public function arrayCollision(array:FlxArray, Collide:Function = null):void
{
var core:FlxSprite;
for (var i:uint = 0; i < array.length; i++)
{
core = array[i];
if (!core.dead)
{
FlxG.collideArray(findBoundingCollisions(core.x, core.y, core.height, core.width), core, Collide);
}
}
}

//Check if this single FlxCore object overlaps with any of the objects in the tree
public function singleOverlap(core:FlxCore, Collide:Function):void
{
FlxG.overlapArray(findBoundingCollisions(core.x, core.y, core.height, core.width), core, Collide);
}

//Check if anything in this array of FlxCore objects overlaps with any of the objects in the tree
public function arrayOverlap(array:FlxArray, Collide:Function):void
{
var core:FlxCore;
for (var i:uint = 0; i < array.length; i++)
{
core = array[i];
if (!core.dead)
{
FlxG.overlapArray(findBoundingCollisions(core.x, core.y, core.height, core.width), core, Collide);
}
}
}
}
}

Test program to play around with. Use your 'B' key to switch between standard and quadtree collision detection. It'll notify you in the logs which one you're using.

Code:

package collidetest
{
import com.adamatomic.flixel.*;
import com.doginlake.quadtree.DogTree;
import flash.geom.Point;

public class Test extends FlxState
{
private var _tileTree:DogTree;
private var _tileArray:FlxArray;
private var _fieldWidth:Number;
private var _fieldHeight:Number;
private var _useTree:Boolean;
private var _numSprites:int;
private var _spriteBaseSize:int;
private var _spriteSizeRange:int;

function Test():void
{
super();

_fieldWidth = 1500;
_fieldHeight = 1500;
_numSprites = 250;
_spriteBaseSize = 1;
_spriteSizeRange = 20;

_tileTree = new DogTree(9, 0, 0, _fieldWidth, _fieldHeight);
_tileArray = new FlxArray();
_useTree = true;

var sprite:FlxSprite;
var spriteXLoc:Number;
var spriteYLoc:Number;
var spriteSize:Number;
for (var i:int = 0; i < _numSprites; i++)
{
spriteSize = Math.random() * _spriteSizeRange+_spriteBaseSize;
spriteXLoc = Math.random() * (_fieldWidth-spriteSize);
spriteYLoc = Math.random() * (_fieldHeight-spriteSize);
sprite = new FlxSprite(null, spriteXLoc, spriteYLoc, false, false, spriteSize, spriteSize, 0xff777777);
sprite.velocity.x = Math.random() * 50;
sprite.velocity.y = Math.random() * 50;
if (Math.random() > .5)
{
sprite.velocity.x = -sprite.velocity.x
}
if (Math.random() > .5)
{
sprite.velocity.y = -sprite.velocity.y
}
this.add(sprite);
_tileTree.add(sprite);
_tileArray.add(sprite);
}
}

override public function update():void
{
var sprite:FlxSprite;

for (var i:int = 0; i < _tileArray.length; i++)
{
sprite = _tileArray[i] as FlxSprite;
if (sprite.x < 0 || sprite.x + sprite.width > _fieldWidth)
{
sprite.velocity.x = -sprite.velocity.x;
}
if (sprite.y < 0 || sprite.y + sprite.height > _fieldHeight)
{
sprite.velocity.y = -sprite.velocity.y;
}
}

if (FlxG.justPressed(FlxG.B))
{
_useTree = !_useTree;
if (_useTree)
{
FlxG.log("Using DogTree");
}
else
{
FlxG.log("Not Using DogTree");
}
}
if (_useTree)
{
for (var j:int = 0; j < _tileArray.length; j++)
{
sprite = _tileArray[j] as FlxSprite;
sprite._dogNode.update(sprite);
}
_tileTree.arrayOverlap(_tileArray, overlaps);
}
else
{
FlxG.overlapArrays(_tileArray, _tileArray, overlaps);
}
super.update();
}

public function overlaps(core1:FlxCore, core2:FlxCore):void
{
core1.flicker(.1);
core2.flicker(.1);
}
}
}

Finally, you have to add
public var _dogNode:DogTree;
to FlxCore

Make sure to only call the update method on objects that are in the tree if they are able to move.

I haven't tested it very extensively, so there could still be bugs.
It showed moderate speed increases for me when implemented in MODE -- I think the increases were more significant when I was working in haXe (which is what I built Polygonal Fury with, where I took this code from) because I was able to inline methods, which reduced the number of calls dramatically.
It's also likely that there are ways that you could speed this up more. If anyone cares to, go right ahead. For my purposes, this is fast enough.

Update: 30th July
I've heavily modified the quadtree, it's somewhat faster now. I've gotten *very* mixed results with it -- In the example program I supplied, the settings that it starts with show a significant increase in performance over the standard collision detection. However, if you set the size of the field much smaller, or increase the size of the sprites, or do a variety of other things, standard collision detection starts to be faster.
It says on PolygonalLabs.de (a fantastic site mentioned later in this thread as well) at http://lab.polygonal.de/ds/ under the 'Linked List' heading that object access in AS3 is faster than array access. Taking that into account, along with *much* faster object insertion/removal, it seems likely that linked list would be a better way to go to store objects in the quadtree itself. I used linked lists after reading that bit on that site for Polygonal Fury, and I definitely saw speed increases when using it on there. I'm currently working on implementing a simple linked list that stores flxcore objects, and integrating it into DogTree. I still hope to keep the changes in other flixel files down to that one line in flxcore though.

[ahref]

Could anyone explain quadtree collision detection. All the websites ive found have gone too far into it.

[GustoGaiden]

Heres a decent explanation.  It basically only runs hit detection on objects close to one another.  The idea is to cut down on total number of collision checks to speed up your game.

http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

[DogInLake]

I'll give it my best... but it's a pretty wonky structure (as most recursive structures usually are). Also, I'll go from the ground up as much as possible. If you know some of this stuff, sorry for wasting your time .

A common method to cull collisions in 2d games is to build a 2-dimensional array, where each index in the array represents an area of a virtual 'grid'. So (1,1) in the array would be from pixels (1, 1) to (10, 10) in the world. As long as no object is larger than 10 x 10, each object can only potentially be in a maximum of four of these virtual grid spaces at the same time (if the object was sitting at the cross-section of where the grid is). If you keep track of which grid spaces the objects are in as they move, then when you're checking collisions you only have to check if a collision happens with objects that share the same grid spaces as the object itself. So your total collision checks go from every object against anything it can collide with, to every object only against things that are potentially close to them.

Maintaining this grid takes some time, but usually the gains are well worth it. If you can make sure that many objects won't move (and so don't need to be maintained), then it takes even less time to maintain. This is the kind of collision detection used in N. It's obviously tile based, each tile takes up exactly one grid space, each object takes up less than one tile.

But there are problems with this kind of strategy: If objects are much smaller than the grid spaces, then you'll be wasting time doing too many checks. If objects are much larger than the grid spaces, then you'll be wasting time as you update many many grid spaces per tick. Using the previous example, if an object was 100 pixels by 100 pixels, and it was capable of movement, then it would be in somewhere near 100 grid spaces simultaneously.

In a game like N, this isn't a problem -- everything is sized correctly. However, if you want to make a game where objects are dramatically larger or smaller than each other, you need a different strategy. Quadtrees are one possible solution (one of the easier solutions, which is why I went with one) to this problem. The problem is that like most recursive structures, it's difficult to describe a quadtree conceptually. I'll step through the algorithm in some detail, and you can ask more questions if you want.

A quadtree uses a tree structure instead of a 2d grid to store approximately where objects are. In a quadtree, each node contains information describing its location and size:

x = 0, y = 0, width = 640, height = 480

As well as references to four child objects, each of which represent one quadrant of the current tree.

NW (x = 0, y = 0, width = 320, height = 240)
NE (x = 320, y = 0, width = 320, height = 240)
SW (x = 0, y = 240, width = 320, height = 240)
SE (x = 320, y = 240, width = 320, height = 240)

Each of those child objects have four children of their own, and each of those have four, etc, etc, however far down you want it to go.

If you're with me so far, node1 describes an area, and also references four nodes each of which describe an area equivalent to one quadrant of node1.

Nodes have one important additional thing: Each node has an array that can store objects that will be checked against for collisions.

Ok, on to the important part: How it works.

The add method basically works like this:

Can the object I'm trying to add exist completely within another the boundaries of one of my child nodes?

If yes, add it to that node instead. (That child node will do the same thing, trying to add the object to one of its children instead)

If no, append it to my object array.

Now after you do this for each object, every object is in the *smallest* node that *completely* encloses it.

The 'find possible collisions' method works like this:

Append all of my objects to the array we're passing back as 'possible' collisions.

Does the object I'm checking for collide with the boundaries of any of my child nodes? If so, pass the array we're gonna be passing back down to that child node, and have it check as well.

And that's pretty much it.

Sorry if it isn't very clear, quadtrees are difficult to explain. Ask more questions if you'd like, I'll try and answer them.

[lechuckgl]

This looks superb. Thanx !

[DogInLake]

Hmmm... there's an obvious bug in the update method. It appears that I hadn't tested it at all  . I'm working on fixing it, but just to let people know that it's currently broken.

Ok, fixed it. See first post.

[lechuckgl]

object access in AS3 is faster than array access. Taking that into account, along with *much* faster object insertion/removal, it seems likely that linked list would be a better way to go to store objects

Well, this is interesting. Maybe Flixel could use a linked list to handle FlxArray instead of flash Array ? This could be a neat upgrade for 1.3

[DogInLake]

In most cases I think you're probably pretty unlikely to see significant improvement -- the thing about a quadtree is that it's adding and removing stuff from arrays (or whatever it uses internally), many many times literally every frame. Most of the time arrays aren't splicing themselves up quite so constantly.

As far as this quadtree goes -- I've decided that the fully recursive method is too slow (too many method calls, which are especially slow in flash), so I'm trying to rewrite it procedurally. Right now I'm thinking I want to use bit-shifting to build a code that can be used by a single array to store the entire tree. Kind of like a dictionary, but at array-access speed. It might be a pipe dream, but I'm sure that I can get this thing running a lot faster than it is right now.

[Adam Atomic]

just wanted to say thanks again for posting this and for the nice clear writeup of how quad trees work!  I'm working on integrating quadtrees into flixel officially and this helped a lot