next »

[st33d]

Just been porting some QuadTree code from XNA:

http://forums.xna.com/forums/p/28936/162992.aspx#162992

So far I've got this mess (I'll upload sauce and a demo when I get home):

Main.as

Code:

package {
	import flash.display.Shape;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.geom.Rectangle;
	
	/**
	 * ...
	 * @author Aaron Steed, nitrome.com
	 */
	
	[SWF(width = "480", height = "480", frameRate="30", backgroundColor = "#CCCCCC")]
	
	public class Main extends Sprite {
		
		private var particles:Vector.<Particle>;
		public static var quad_tree:QuadTree;
		public static var shape:Shape;
		private var frame_count:int;
		
		public static const WIDTH:Number = 480;
		public static const HEIGHT:Number = 480;
		
		public function Main():void {
			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));
			particles = new Vector.<Particle>();
			var item:Particle;
			for(var i:int = 0; i < 1000; i++) {
				item = new Particle((WIDTH - 50) * Math.random(), (HEIGHT -50) * Math.random(), 5 + Math.random() * 10, 5 + Math.random() * 10, -1 + Math.random() * 2, -1 + Math.random() * 2);
				particles.push(item);
				quad_tree.addItem(item);
			}
		}
		
		private function loop(e:Event = null):void {
			shape.graphics.clear();
			collision();
			updateParticles();
			frame_count++;
		}
		
		private function updateParticles():void{
			graphics.clear();
			for(var i:int = 0; i < particles.length; i++) {
				particles[i].main();
				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);
		}
		
		public function collision():void{
			var leaves_inside_bounds:Vector.<QuadTree> = quad_tree.getLeavesInsideBounds(null);
			var i:int, j:int;
			for(i = 0; i < leaves_inside_bounds.length; i++) {
				itemCollision(leaves_inside_bounds[i], leaves_inside_bounds[i].items);
			}
		}
		
		public function itemCollision(tree:QuadTree, list:Vector.<Particle>):void{
			shape.graphics.lineStyle(0);
			shape.graphics.drawRect(tree.bounds.x, tree.bounds.y, tree.bounds.width, tree.bounds.height);
			var i:int, j:int, item1:Particle, item2:Particle;
			for(i = 0; i < list.length; i++) {
				item1 = list[i];
				shape.graphics.moveTo(tree.bounds.x, tree.bounds.y);
				shape.graphics.lineTo(item1.x, item1.y);
				for(j = i + 1; j < list.length; j++) {
					item2 = list[j];
					if(item1.intersects(item2)){
						item1.colliding = frame_count;
						item2.colliding = frame_count;
					}
				}
			}
		}
	}
}

QuadTree.as

Code:

package  {
	import flash.display.Graphics;
	import flash.geom.Point;
	import flash.geom.Rectangle;
	/**
	 * ...
	 * @author Aaron Steed, nitrome.com
	 */
	public class QuadTree{
		
		public var bounds:Rectangle;
		public var nodes:Vector.<QuadTree>;
		public var items:Vector.<Particle>;
		
		public static var max_items:int = 5;
		
		public function QuadTree(bounds:Rectangle) {
			this.bounds = bounds;
			items = new Vector.<Particle>();
		}
		
		public function addItem(item:Particle):Boolean{
			if(bounds.contains(item.x + item.width * 0.5, item.y + item.height * 0.5)){
				if(!nodes){
					if(items.length < max_items){
						items.push(item);
						return true;
					}
					split();
					
					if(!nodes){
						max_items *= 2;
						return addItem(item);
					}
				}
				if(!nodes[0].addItem(item))
					if(!nodes[1].addItem(item))
						if(!nodes[2].addItem(item))
							nodes[3].addItem(item);
				return true;
			}
			return false;
		}
		
		public function itemMoved(item:Particle, prev_pos:QuadTree):Boolean{
			if(bounds.contains(item.x + item.width * 0.5, item.y + item.height * 0.5)){
				if(!nodes){
					if(this != prev_pos){
						if(prev_pos){
							prev_pos.items.splice(prev_pos.items.indexOf(item), 1);
						}
						addItem(item);
					}
					return true;
				}
				if(!nodes[0].itemMoved(item, prev_pos))
					if(!nodes[1].itemMoved(item, prev_pos))
						if(!nodes[2].itemMoved(item, prev_pos))
							nodes[3].itemMoved(item, prev_pos);
				return true;
			}
			return false;
		}
		
		public function findLeaf(rect:Rectangle):QuadTree{
			if(bounds.contains(rect.x + rect.width * 0.5, rect.y + rect.height * 0.5)){
				if(!nodes){
					return this;
				} else {
					var result:QuadTree;
					if(!(result = nodes[0].findLeaf(rect)))
						if(!(result = nodes[1].findLeaf(rect)))
							if(!(result = nodes[2].findLeaf(rect)))
								result = nodes[3].findLeaf(rect);
					return result;
				}
			}
			return null;
		}
		
		private static var leaves_inside_bounds:Vector.<QuadTree> = new Vector.<QuadTree>();
		
		public function getLeavesInsideBounds(bounds:Rectangle):Vector.<QuadTree>{
			leaves_inside_bounds = new Vector.<QuadTree>();
			addLeavesInsideBounds(bounds);
			return leaves_inside_bounds;
		}
		
		public function addLeavesInsideBounds(bounds:Rectangle):void{
			if(!nodes){
				leaves_inside_bounds.push(this);
			} else {
				nodes[0].addLeavesInsideBounds(bounds);
				nodes[1].addLeavesInsideBounds(bounds);
				nodes[2].addLeavesInsideBounds(bounds);
				nodes[3].addLeavesInsideBounds(bounds);
			}
		}
		
		public function split():void{
			nodes = new Vector.<QuadTree>(4, true);
			nodes[0] = new QuadTree(new Rectangle(bounds.x, bounds.y, bounds.width * 0.5, bounds.height * 0.5));
			nodes[1] = new QuadTree(new Rectangle(bounds.x + bounds.width * 0.5, bounds.y, bounds.width * 0.5, bounds.height * 0.5));
			nodes[2] = new QuadTree(new Rectangle(bounds.x, bounds.y + bounds.height * 0.5, bounds.width * 0.5, bounds.height * 0.5));
			nodes[3] = new QuadTree(new Rectangle(bounds.x + bounds.width * 0.5, bounds.y + bounds.height * 0.5, bounds.width * 0.5, bounds.height * 0.5));
			reassignItems();
			items = new Vector.<Particle>();
		}
		
		public function reassignItems():void{
			for(var i:int = 0; i < items.length; i++) {
				if(!nodes[0].addItem(items[i]))
					if(!nodes[1].addItem(items[i]))
						if(!nodes[2].addItem(items[i]))
							nodes[3].addItem(items[i]);
			}
		}
	}
}

Particle.as

Code:

package  {
	import flash.display.Graphics;
	import flash.geom.Point;
	import flash.geom.Rectangle;
	/**
	 * ...
	 * @author Aaron Steed, nitrome.com
	 */
	public class Particle extends Rectangle{
		
		public var prev_pos:Point;
		public var vx:Number, vy:Number;
		public var colliding:int;
		
		public 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;
			prev_pos = new Point(x + width * 0.5, y + height * 0.5);
		}
		
		public function main():void{
			var prev_node:QuadTree = Main.quad_tree.findLeaf(this);
			x += vx;
			y += vy;
			if(x < 0) vx = -vx;
			if(y < 0) vy = -vy;
			if(x + width > Main.WIDTH) vx = -vx;
			if(y + height > Main.HEIGHT) vy = -vy;
			Main.quad_tree.itemMoved(this, prev_node);
			//Main.shape.graphics.lineStyle(0);
			//Main.shape.graphics.drawRect(prev_node.bounds.x, prev_node.bounds.y, prev_node.bounds.width, prev_node.bounds.height);
			//Main.shape.graphics.lineTo(x, y);
		}
		
		public function draw(gfx:Graphics):void{
			gfx.drawRect(x, y, width, height);
		}
		
	}

}

So it works - basically. But there's two major issues:

• A split QuadTree never collapses when empty
• Membership of a QuadTree is determined by the center point - making the bounding box increasingly useless as the Tree divides

So I've just ported a half-arsed implementation, that would cause more problems that it solved if I put it to work.

Now I'm certain I followed that code correctly. I've looked around for other QuadTree code, but it seems that no one wants to share, or worse, posts a half complete tutorial that ends with, "I haven't quite figured out the rest, you know, the stuff that would actually make it work."

My aim for this thread is to have some usable, commented and portable QuadTree code instead of a demo with no source or a half arsed tutorial saying how great it would be to use QuadTrees but I'm buggered if I know how to do it.

I know this is an AS3 thread, but I quite happy to trawl through C code if anyone can point to any.

Thanks in advance.

[grapefrukt]

I know motor2 has a quadtree implementation, maybe you can take a peek at that.

[st33d]

Okay, didn't take a look at the motor one but I did come up with my own idea of how it should work - and it's open sauce for all:

http://wonderfl.net/c/hSXX

The major disadvantage I see with a QuadTree is that it's fuck all use when you have all the particles in one Quad or even worse when they're all on the intersections of the QuadTree divisions, preventing them from residing in smaller containers.

I'm not sure I've done the implementation quite right, but it's on Wonderfl, so people can grab the code and play with it or fork it.

[jotapeh]

Neat. Thanks for open-sourcing this - I will poke around it later but I think this will be helpful to the community.

[Zaphos]

The major disadvantage I see with a QuadTree is that it's fuck all use when you have all the particles in one Quad or even worse when they're all on the intersections of the QuadTree divisions, preventing them from residing in smaller containers.

Hmm, maybe try using a loose quadtree or hierarchical grid?

[Falmil]

Hmmm, I don't know much about QuadTrees either yet, but if a Particle ended up on an intersection, couldn't you just add the same Particle reference to each smaller QuadTree? Not sure how messy this would be, though.
Also, could you collapse a QuadTree if the number of unique Particles in the 4 child QuadTrees totals to less than a certain value?

[muku]

or even worse when they're all on the intersections of the QuadTree divisions, preventing them from residing in smaller containers.

I don't understand your issue here. If your quadtree is divided at, say center_x, and your object has coordinate x, just define it to go into the "left" quadtree if x <= center_x and into the "right" if x > center_x. So it's always well-defined into which child it should go, there is no such thing as "on intersections". Or did I miss your point?

[st33d]

Hmmm, I don't know much about QuadTrees either yet, but if a Particle ended up on an intersection, couldn't you just add the same Particle reference to each smaller QuadTree?

A QuadTree is a recursive structure. If it doesn't fit into a smaller QuadTree then it bubbles up to a higher QuadTree. The higher QuadTree contains all the QuadTrees that fit into it.

If your quadtree is divided at, say center_x, and your object has coordinate x, just define it to go into the "left" quadtree if x <= center_x and into the "right" if x > center_x. So it's always well-defined into which child it should go, there is no such thing as "on intersections". Or did I miss your point?

I'm using a bounding box to test for collision - not a point. My object does not just have coordinate x,y it has all the coordinates that it's height and width encompass as well. Making the intersections an issue.

Hmm, maybe try using a loose quadtree or hierarchical grid?

I'm not saying the technology is useless. If you have a lot of objects of varying size, then it's quite useful.

I think for creating a hierachical grid, having a working QuadTree implementation is good to look at.

It's also worth mentioning that I'm not sure I've got the implementation 100% right. Most explanations of QuadTrees I've seen have dynamically resizing trees and limits on tree contents. Maybe that's just for point collision.

[muku]

If your quadtree is divided at, say center_x, and your object has coordinate x, just define it to go into the "left" quadtree if x <= center_x and into the "right" if x > center_x. So it's always well-defined into which child it should go, there is no such thing as "on intersections". Or did I miss your point?

I'm using a bounding box to test for collision - not a point. My object does not just have coordinate x,y it has all the coordinates that it's height and width encompass as well. Making the intersections an issue.

Ah yes, that makes sense.

Just glanced over your code: I have a hunch that your QuadTree.getItems() method might be a major source of inefficiency. For every check, you concatenate all the elements of all child nodes into a list. This creates lots of garbage, keeping the garbage collector busy, plus concatenating lists will probably require lots of reallocations. I'd reckon this is quite slow.

What you really want is just to iterate over all the elements. My first idea would be creating a method like forEach() or something like that which takes a function which is then applied to every child element. Something like this (treat this as pseudocode because I haven't used AS in a long time):

Code:

public function forEach(func:Function):void {
  for each (var p:Particle in items)
    func(p);

  if (type != LEAF) {
    // recurse into child nodes
    nw.forEach(func);
    ne.forEach(func);
    sw.forEach(func);
    se.forEach(func);
  }
}

Then for your collision check pass a closure which checks for collisions against the current object into forEach(). If you see what I mean?

Or alternatively some kind of iterator scheme, though I guess it would be more of a hassle to implement.

Would be interesting to see if that speeds things up.

[Falmil]

I know that a QuadTree is a recursive structure that contains 4 additional QuadTrees along with an object list. I was just wondering what the consequences would be of sending a reference of any objects that are on the dividing lines down the QuadTree so that you only have to check each leaf by itself because the branches are all empty, instead of checking all the branches for big objects that don't fit completely into one of the QuadTree areas along with each leaf. Obviously, the lower branches of the QuadTree would contain duplicate objects between them, but I have no idea if this would provide any additional overhead or reduce it.

[raigan]

Just for the sake of argument: do you need to use a quadtree? I haven't yet come across a scene that required one, a grid or hierarchical grid is almost always sufficient (and much simpler to implement).

[st33d]

I was just wondering what the consequences would be of sending a reference of any objects that are on the dividing lines down the QuadTree so that you only have to check each leaf by itself because the branches are all empty, instead of checking all the branches for big objects that don't fit completely into one of the QuadTree areas along with each leaf.

The way I tackled the collision is that each object looks down only to collide with things. That way there's only one collision check per object. Sending more references down the QuadTree would remove the benefits of checking against less things. Although perhaps you could use the structure for something else.

do you need to use a quadtree? I haven't yet come across a scene that required one

In short no. But people will bang on about them the same way they will about things like Neural Nets and Genetic Algorithms. Because it sounds cool there's a load of internet pages with half arsed suggestions saying they're brilliant, but no source code to illustrate why.

So along comes me to have a go and spread my disenchantment.

These things do remain useful computer-science excercises though. I've more of an idea how to implement a hierarchical grid now and the problems inherent with putting bounding boxes on to them.

[Falmil]

I'm not understanding how you have it so there's only one collision check per object. Do you mean one SET of collision checks per object?
I admit that I didn't think of just checking the large objects against the smaller objects down the tree and then moving on because you only need to check object A against object B and not B against A again. That might have been what I wasn't thinking of before as to how they would work.

[st33d]

Think of all of the objects as people and they are all facing one way. The result is that if they say someone is in front of them, then the person in front never knows, they can only see who is in front of themselves.

There is indeed one set of checks per object, but that object only ever looks down into the quadtree. If anything behind it is colliding with it, then that object tells the object in front that it has been touched.

I've commented on this in the source code.