Author Topic: DogTree -- A collision quad tree for flixel  (Read 10746 times)

DogInLake

  • Guest
DogTree -- A collision quad tree for flixel
« on: Tue, Jul 28, 2009 »
Note: New Version: Last updated on 30th of July

Code: [Select]
//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: [Select]
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.
« Last Edit: Thu, Jul 30, 2009 by DogInLake »

ahref

  • Guest
Re: DogTree -- A collision quad tree for flixel
« Reply #1 on: Tue, Jul 28, 2009 »
Could anyone explain quadtree collision detection. All the websites ive found have gone too far into it.

GustoGaiden

  • Member
  • **
  • Posts: 11
  • Karma: +0/-0
    • View Profile
    • AndyGusto's Portfolio Page
Re: DogTree -- A collision quad tree for flixel
« Reply #2 on: Tue, Jul 28, 2009 »
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

  • Guest
Re: DogTree -- A collision quad tree for flixel
« Reply #3 on: Tue, Jul 28, 2009 »
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 :P.

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

  • Active Member
  • ***
  • Posts: 118
  • Karma: +0/-0
    • View Profile
Re: DogTree -- A collision quad tree for flixel
« Reply #4 on: Wed, Jul 29, 2009 »
This looks superb. Thanx !

DogInLake

  • Guest
Re: DogTree -- A collision quad tree for flixel
« Reply #5 on: Wed, Jul 29, 2009 »
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.
« Last Edit: Thu, Jul 30, 2009 by DogInLake »

lechuckgl

  • Active Member
  • ***
  • Posts: 118
  • Karma: +0/-0
    • View Profile
Re: DogTree -- A collision quad tree for flixel
« Reply #6 on: Thu, Jul 30, 2009 »
Quote
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

  • Guest
Re: DogTree -- A collision quad tree for flixel
« Reply #7 on: Thu, Jul 30, 2009 »
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

  • Founder
  • Key Contributor
  • *****
  • Posts: 852
  • Karma: +0/-0
  • new dad
    • View Profile
    • Adam Atomic
Re: DogTree -- A collision quad tree for flixel
« Reply #8 on: Sun, Feb 7, 2010 »
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 :)

vonWolfehaus

  • Active Member
  • ***
  • Posts: 247
  • Karma: +0/-0
    • View Profile
    • Cold Constructs
Re: DogTree -- A collision quad tree for flixel
« Reply #9 on: Tue, Feb 9, 2010 »
Adam, why did you decide to go with quadtrees rather than a static grid? All performance tests point to the static grid being more efficient than even pre-cached quadtrees..  ???
Meet Obama every day at #flixel on irc.freenode.net.
Use your favorite IRC client or  http://webchat.freenode.net/

NeoTiger

  • Guest
Re: DogTree -- A collision quad tree for flixel
« Reply #10 on: Wed, Feb 10, 2010 »
I don't think that the performance difference between a static grid and quad tree collision detection can be generalized. It depends a lot on the range of dimension variety between your colliding sprites.

Certainly, 2D games tend to have sprites of rather similar dimensions, while 3D games with their greater geometric freedom are fertile soil for quad trees. But I think the difference we're talking here is miniscule in comparison to Flixel's previous method of collision detection.

And I think any programmer that is experienced enough to even care bout that little difference should also be skilled enough to just take Flixel and implement his prefered collision detection method himself. That's why it's called a "framework" and not an "engine"

AtomicTroop

  • Member
  • **
  • Posts: 24
  • Karma: +0/-0
    • View Profile
Re: DogTree -- A collision quad tree for flixel
« Reply #11 on: Thu, Feb 11, 2010 »
Certainly, 2D games tend to have sprites of rather similar dimensions, while 3D games with their greater geometric freedom are fertile soil for quad trees.

Sorry to derail this a bit, but why/how would one even use quadtrees in 3D-games? Wouldn't that be more in the realms of octrees?

skondrk

  • Member
  • **
  • Posts: 18
  • Karma: +0/-0
    • View Profile
Re: DogTree -- A collision quad tree for flixel
« Reply #12 on: Sat, May 1, 2010 »
Certainly, 2D games tend to have sprites of rather similar dimensions, while 3D games with their greater geometric freedom are fertile soil for quad trees.

Sorry to derail this a bit, but why/how would one even use quadtrees in 3D-games? Wouldn't that be more in the realms of octrees?

You could use an octree, but they're only really useful if you're going really high on the Y-axis (flight sims, certain action games where you climb buildings, stuff like that).

For most 3D games that use a quad tree, they skip checking Y-axis dimensions and use the X instead. Imagine if you were looking straight down at a 3D game, and then cut that up into squares (or, for all intents and purposes, cubes). Using those squares is how the quad tree finds out what's close and what's not.