QuadTree

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

st33d

forked:6
favorite:18
lines:170
license : MIT License
modified : 2010-04-15 02:17:09

Embed: Tweet

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);
			}
		}
	}
	
}

Code Fullscreen

Preview Fullscreen