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 st33d ( http://wonderfl.net/user/st33d )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/hSXX
*/
package {
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>;
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 Vector.<Particle>();
var item:Particle;
for(var i:int = 0; i < 300; i++) {
item = new Particle((WIDTH - 50) * Math.random(), (HEIGHT -50) * Math.random(), 5 + Math.random() * 10, 5 + Math.random() * 10, -2 + Math.random() * 4, -2 + Math.random() * 4);
particles.push(item);
quad_tree.addItem(item);
}
}
private function loop(e:Event = null):void {
shape.graphics.clear();
updateParticles();
frame_count++;
}
private function updateParticles():void{
graphics.clear();
var i:int, j:int;
for(i = 0; i < particles.length; i++) {
particles[i].main();
}
for(i = 0; i < particles.length; i++) {
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);
particles.push(item);
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:Array;
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;
colliding = 0;
}
public function main():void{
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;
current_quadtree.itemMoved(this);
FlashTest.shape.graphics.lineStyle(0, 0x00FF00);
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 */
public function collision():void{
test_against = current_quadtree.getItems();
for(var i:int = 0; i < test_against.length; i++) {
//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(test_against[i] != this && intersects(test_against[i])){
colliding = FlashTest.frame_count;
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 type:int;
public static var max_items:int = 5;
public static const LEAF:int = 1;
public static const BRANCH:int = 2;
public var bounds:flash.geom.Rectangle;
public var items:Array;
function QuadTree(bounds:flash.geom.Rectangle, depth:int, root:QuadTree = null) {
items = [];
this.bounds = bounds;
if(!root){
root = this;
}
this.root = root;
if(depth){
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);
type = BRANCH;
} else {
type = LEAF;
}
}
/* Hopefully does a sort of recursive dive into all the contents of the quad */
public function getItems():Array{
if(type == LEAF){
return items;
} else {
return items.concat(nw.getItems(), ne.getItems(), sw.getItems(), se.getItems());
}
}
/* Try to dive down to the smallest quad that can fit the item */
public function addItem(item:Particle):QuadTree{
if(type == BRANCH){
if(nw.bounds.containsRect(item)) nw.addItem(item);
else if(ne.bounds.containsRect(item)) ne.addItem(item);
else if(sw.bounds.containsRect(item)) sw.addItem(item);
else if(se.bounds.containsRect(item)) se.addItem(item);
else{
item.best_depth = !(item.width <= bounds.width * 0.5 && item.height <= bounds.height * 0.5);
item.current_quadtree = this;
items.push(item);
}
return this;
} else {
item.best_depth = true;
item.current_quadtree = this;
items.push(item);
return this;
}
}
/* Tells the QuadTree we've moved an item and determines if we need to re-allocate it */
public function itemMoved(item:Particle):void{
if(!bounds.containsRect(item)){
items.splice(items.indexOf(item), 1);
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(
!((bounds.x + bounds.width * 0.5 >= item.x && bounds.x + bounds.width * 0.5 <= item.right) ||
(bounds.y + bounds.height * 0.5 >= item.y && bounds.y + bounds.height * 0.5 <= item.bottom))
){
items.splice(items.indexOf(item), 1);
root.addItem(item);
}
}
}
}