A simple QuadTree implementation
So basically here I've got a bunch of objects all
colliding with each other using a QuadTree to optimise
the process
I'm pretty certain this isn't the fastest implementation
though. I can only push about 500 around
Plus you'll notice that when on intersections, things
get pretty piss poor. But it's much faster than a straight
comparison between all objects on screen, so there you
go...
@author Aaron Steed, nitrome.com
/**
* Copyright DuncanConroy ( http://wonderfl.net/user/DuncanConroy )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/hdE7B
*/
// forked from st33d's QuadTree
package
{
import __AS3__.vec.Vector;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Rectangle;
import flash.display.Graphics;
import flash.geom.Point;
import flash.geom.Rectangle;
/**
* A simple QuadTree implementation
*
* So basically here I've got a bunch of objects all
* colliding with each other using a QuadTree to optimise
* the process
*
* I'm pretty certain this isn't the fastest implementation
* though. I can only push about 500 around
*
* Plus you'll notice that when on intersections, things
* get pretty piss poor. But it's much faster than a straight
* comparison between all objects on screen, so there you
* go...
*
* @author Aaron Steed, nitrome.com
*/
[SWF(frameRate="30", backgroundColor = "#CCCCCC")]
public class FlashTest extends Sprite {
private var particles :Vector.<Particle>,
intParticleCount :int;
public static var quad_tree:QuadTree;
public static var shape:Shape;
public static var frame_count:int;
public static const WIDTH:Number = 465;
public static const HEIGHT:Number = 465;
public function FlashTest() {
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e:Event = null):void {
removeEventListener(Event.ADDED_TO_STAGE, init);
addEventListener(Event.ENTER_FRAME, loop);
stage.addEventListener(MouseEvent.CLICK, click);
shape = new Shape();
addChild(shape);
frame_count = -1;
quad_tree = new QuadTree(new Rectangle(0, 0, WIDTH, HEIGHT), 5);
particles = new <Particle>[];
var item:Particle,
i :int = int(0 - 1);
while(++i < 30)
{
item = new Particle((WIDTH - 50) * Math.random(), (HEIGHT -50) * Math.random(), Math.random() * 50, Math.random() * 50, -2 + Math.random() * 4, -2 + Math.random() * 4);
this.particles[this.intParticleCount++] = item;
quad_tree.addItem(item);
}
}
private function loop(e:Event = null):void {
FlashTest.shape.graphics.clear();
this.updateParticles();
++FlashTest.frame_count;
}
private function updateParticles():void{
this.graphics.clear();
var i :int = int(0 - 1),
len :int = this.particles.length;
while(++i < len) {
particles[i].main();
}
i = int(0 - 1);
while(++i < len) {
graphics.beginFill(particles[i].colliding == frame_count ? 0xFF0000 : 0xFFFFFF);
particles[i].draw(graphics);
graphics.endFill();
}
}
public function click(e:MouseEvent = null):void{
var item:Particle = new Particle(mouseX, mouseY, 5 + Math.random() * 10, 5 + Math.random() * 10, -1 + Math.random() * 2, -1 + Math.random() * 2);
this.particles[this.intParticleCount++] = item;
FlashTest.quad_tree.addItem(item);
}
}
}
class Particle extends flash.geom.Rectangle{
public var vx:Number, vy:Number;
public var colliding:int;
public var current_quadtree:QuadTree;
public var best_depth:Boolean;
public static var test_against:Vector.<Particle>;
function Particle(x:Number = 0, y:Number = 0, width:Number = 0, height:Number = 0, vx:Number = 0, vy:Number = 0) {
super(x, y, width, height);
this.vx = vx;
this.vy = vy;
this.colliding = 0;
}
public function main():void{
this.collision();
x += vx;
y += vy;
if(x < 0) vx = -vx;
if(y < 0) vy = -vy;
if(x + width > FlashTest.WIDTH) vx = -vx;
if(y + height > FlashTest.HEIGHT) vy = -vy;
this.current_quadtree.itemMoved(this);
FlashTest.shape.graphics.lineStyle(0, 0x00FF00, .25);
FlashTest.shape.graphics.drawRect(current_quadtree.bounds.x, current_quadtree.bounds.y, current_quadtree.bounds.width, current_quadtree.bounds.height);
FlashTest.shape.graphics.lineTo(x, y);
}
public function draw(gfx:flash.display.Graphics):void{
gfx.drawRect(x, y, width, height);
}
/* For collision we peer down into our current quad tree to see what we're colliding with below
* we need not worry about items above us because they will peer down and tell us when they collide with us */
final public function collision():void{
Particle.test_against = current_quadtree.getItems();
var i :int = int(0 - 1),
len :int = Particle.test_against.length;
while(++i < len)
{
//FlashTest.shape.graphics.lineStyle(0, 0xFFFF00);
//FlashTest.shape.graphics.moveTo(x, y);
//FlashTest.shape.graphics.lineTo(test_against[i].x, test_against[i].y);
if(Particle.test_against[i] === this) continue;
if(super.intersects(Particle.test_against[i]))
{
this.colliding = FlashTest.frame_count;
Particle.test_against[i].colliding = FlashTest.frame_count;
}
}
}
}
class QuadTree
{
public var nw:QuadTree;
public var ne:QuadTree;
public var sw:QuadTree;
public var se:QuadTree;
public var parent:QuadTree;
public var root:QuadTree;
public var blnIsLeaf:Boolean;
public static var max_items:int = 5;
public var bounds:flash.geom.Rectangle;
public var items :Vector.<Particle>;
private var fltQuarterWidth :Number,
fltQuarterHeight :Number;
function QuadTree(bounds:flash.geom.Rectangle, depth:int, root:QuadTree = null) {
this.items = new <Particle>[];
this.bounds = bounds;
this.fltQuarterWidth = bounds.x + bounds.width * .5;
this.fltQuarterHeight = bounds.y + bounds.height * .5
if(!root)
{
root = this;
}
this.root = root;
if(depth)
{
var fltNewWidth :Number = (bounds.width * .5) * 2.5,
fltNewHeight :Number = (bounds.height * .5) * 2.5;
nw = new QuadTree(new flash.geom.Rectangle(bounds.x, bounds.y, bounds.width * 0.5, bounds.height * 0.5), depth - 1, root);
ne = new QuadTree(new flash.geom.Rectangle(bounds.x + bounds.width * 0.5, bounds.y, bounds.width * 0.5, bounds.height * 0.5), depth - 1, root);
sw = new QuadTree(new flash.geom.Rectangle(bounds.x, bounds.y + bounds.height * 0.5, bounds.width * 0.5, bounds.height * 0.5), depth - 1, root);
se = new QuadTree(new flash.geom.Rectangle(bounds.x + bounds.width * 0.5, bounds.y + bounds.height * 0.5, bounds.width * 0.5, bounds.height * 0.5), depth - 1, root);
this.blnIsLeaf = false;
}
else
{
this.blnIsLeaf = true;
}
}
/* Hopefully does a sort of recursive dive into all the contents of the quad */
final public function getItems():Vector.<Particle>
{
if(this.blnIsLeaf)//if(this.type === QuadTree.LEAF)
{
return this.items;
}
return this.items.concat(this.nw.getItems(), this.ne.getItems(), this.sw.getItems(), this.se.getItems());
}
/* Try to dive down to the smallest quad that can fit the item */
final public function addItem(item:Particle):QuadTree
{
if(!this.blnIsLeaf)//if(this.type === QuadTree.BRANCH)
{
if(this.nw.bounds.containsRect(item)) this.nw.addItem(item);
else if(this.ne.bounds.containsRect(item)) this.ne.addItem(item);
else if(this.sw.bounds.containsRect(item)) this.sw.addItem(item);
else if(this.se.bounds.containsRect(item)) this.se.addItem(item);
else
{
item.best_depth = !(item.width <= bounds.width * 0.5 && item.height <= bounds.height * 0.5);
item.current_quadtree = this;
this.items[this.items.length] = item;
}
return this;
}
item.best_depth = true;
item.current_quadtree = this;
this.items[this.items.length] = item;
return this;
}
/* Tells the QuadTree we've moved an item and determines if we need to re-allocate it */
final public function itemMoved(item:Particle):void
{
if(!this.bounds.containsRect(item))
{
this.items = this.items.splice(this.items.indexOf(item), int(1));
this.root.addItem(item);
}
else if(!item.best_depth)
{
// this particle could possibly fit into a smaller quad, but we need to check
// whether it's still on the cross-section that kept it out of the best sized quad
if(
!((this.fltQuarterWidth >= item.x && this.fltQuarterWidth <= item.right) ||
(this.fltQuarterHeight >= item.y && this.fltQuarterHeight <= item.bottom))
)
{
this.items = this.items.splice(this.items.indexOf(item), int(1));
this.root.addItem(item);
}
}
}
}