Quadtree for moving objects

Performance Tuning
#21

I’m going to go off on a tangent and ask: Is a quadtree even necessary?

Note: I’m assuming boids are points, or can be approximated as such.

Boids are apparently only interested in their immediate neighbours and so the query area is going to be fixed and pretty small. Drilling through layers of tree nodes to find out which leaves we should be looking at seems silly when we can directly address into a simple grid of linked lists.
This also gives you back fine-grained (non-power-of-two) control over the number of leaf boxes, so you can experiment with the size of the grid boxes and find the sweet-spot where the false-positive cost of large boxes balances the cost of examining lots of little (probably empty) boxes.

Happily, the degenerate case where all boids are clustered in one box is something that they are specifically trying to avoid.
Unhappily, you’ll fall foul of the no-arrays-of-generic-collections annoyance.

#22

I have recently solved this in a situation where everything is 2d:

The best solution I’ve found is to combine 2d array of cells and a quadtree that perfectly matches the 2d grid so that each leaf node is also a cell of the 2d array. I will post code once I get back home after work.

The datastructure consists of:

  • 2d array that contains cells containing the objects.
  • A quadtree where each cell forms a leaf node.
    (- A multimap which stores all the objects in iterable form by cell.)

Ideal requirements:

  • Fast neighbor finding.
  • Fast proximity finding.
  • No wasted ascending or descending the tree (ideally only when inserting, removing objects or intersection tests).
  • No going through empty cells.

Limitations:

  • The game area width in cells must be a power of two.
  • Only leaf nodes can contain objects.
  • Each object is contained by only one cell even if it intersects multiple cells.
  • All objects must be smaller than one cell.

The data structure has:
-addition O(Log n) if added from root node (vs O(n^2) of 2d grid), addition to a cell is O(1);
-remove O(Log n) if removed from a cell, O(n^2) otherwise;
-No ascending the tree when moving objects. In worst case if neighbors aren’t found initialization time you have to ascend to root node and then descend back;
-No need to clear the tree and reinsert objects after each update;
-Fast proximity finding O(1) vs ascending and descending of quadtree or complicated initialization algorithms.

Further optimization:
-Holding all your game objects in a MultiMap where each cell index(j * size + i) works as a key to the objects eliminates the need to go through a 2d array to update empty cells.
-Using HashSets inside the cells instead of ArrayLists removes the need to copy or move memory when removing objects from leaf nodes (not sure if this happens).


       Node
    /    \    \ \
   /     |     |  \
Cell Cell Cell cell

Quadtrees alone aren’t very good for moving objects. A 2d grid isn’t very good for inserting and removing objects at random places. Quadtree is good for deciding whether objects intersect, 2d grid isn’t. I am using this for boid movement as well and so far it has been working great.

Comments? Improvements?

#23

Ouch, those are pretty harsh limitations. You’re going to be limiting your gameplay considerably with those. And if those limitations are acceptable then why bother with the quadtree bit at all? A simple 2d array which you index into by position would do the job just as well but with less overhead. IMHO you’ve violated one of the fundamental principles (nodes should entirely contain their children, otherwise hierarchical culling breaks down), at which point you’ve not got a proper quad tree. It’s not surprising that you’d conclude that “quad trees” (or rather, your hacked approximation) are unsuitable for moving objects.

I’m also surprised that no-one has suggested sweep-and-prune yet. It handles the edge case that Phear was worred about (all objects bunching up in a single quad tree node), and is nicely parallisable too.

#24

First things first: with a any game you are going to end up with multiple data structures for multiple purposes once you start having performance problems. There isn’t a one single solution that optimally satisfies all requirements set out by multiple different problems such as: collision detection, path finding, proximity finding and hierarchial culling.

Because quadtree essentially complements a 2d grid nicely. Why combine sweep and prune and a Quadtree? Because they work well together. I don’t see how those limitations are going to effect the gameplay.

Still, in worst case you’d be going through the array in n^2. This would come to reality when doing intersection tests over large areas.

There’s absolutely nothing wrong in restricting object ownership to a single node. Note that an object intersecting multiple leaf nodes can still be tested against more objects than the ones in the same leaf.

While I did not state that quadtrees are unsuitable for moving objects I firmly hold the opinion that quadtrees are not an optimal solution to collision detection of moving objects. Quadtrees have much better uses in storing, representing and manipulating static 2d geometry.

Yes, it is a good improvement over brute force testing in almost all situations. On gamedev.net Someone had taken the time to create performance comparisons in between 2d grid, quadtree and prune and sweep. Unfortunately I can’t find this at the moment.

#25

Sooner or later you’re going to want to have entities of substantially different sizes. The obvious example would be boss characters in most shooters or platformers. If you’re going to impose such crude limitations then you don’t need a quad tree. If you are going to want entities of grossly different sizes then your “quad tree” is useless.

[quote]Still, in worst case you’d be going through the array in n^2. This would come to reality when doing intersection tests over large areas.
[/quote]
No-one said anything about looping over the whole array.

[quote]There’s absolutely nothing wrong in restricting object ownership to a single node. Note that an object intersecting multiple leaf nodes can still be tested against more objects than the ones in the same leaf.
[/quote]
Nothing wrong with it, but you’re no longer doing a quad tree, you’re doing a custom hacked solution which may or may not be more appropriate for a certain, constrained set of usage in your game. And yes, you can test against more object than in the current leaf, but you have to know in advance how many surrounding leafs around you to check - again you’re imposing an arbitrary upper bound on the size of your entities.

#26

The simple quadtree solution is loads more elegant and very simple and theoretically as fast as possible with no constraints on position other than efficient collisions can only occur within the coordinate space defined by the root node. Why not stick with that?

Cas :slight_smile:

#27

Because it’s not fastest.

Besides that, in your algorithm, a LOT of items will end up in the ‘catch all’ list – for example: every item in the middle of the map would end up being rejected all the time. Also, the ‘parents’ will have way too many items, which could otherwise be put in half-cell-shifted-grids – see below:

The obvious solution is to create another abstraction, with a translation of the ‘grid’ by half a cell size on each axis at each level (recursion depth). That way, if it fits the parent, but not entirely fits in any of its children, you can try the shifted cells, which have a high probability of accepting the item.

You’d have to leave the regular OO way of designing your tree. It should merely be a View on your grids for each level. Let’s say your root-node has a (cell)size of 256.0f, the 4 children would have cellsizes of 128.0f, and would be positioned to exactly fit inside the parent. Every item that has its boundingbox intersecting the cell-boundaries would put in the parent (recursively). If you’d add another grid (at level 1 – root is level 0) of 3x3 cells, shifted (-cell/2, -cell/2) you could catch all those edge-cases in the right level of your tree.

In the next level (#2) you’d have 4x4 cells with a dimension of 64.0f units. The ‘shifted grid’ would have 5x5 cells of 64.0f units, shifted (-32, -32) to (again) catch all edge-cases.

etc. etc. etc.

In the end, you have all items in their proper level / depth, instead of pushing them up the tree in edge-cases. This obviously yields in better performance, as you have less items in each node.

#28

Hm I suppose it may not be always the fastest. I do know about the boundary cases where things fall directly in the middle of a node boundary and end up right in the root node - but you have to generally assume that for 99.9% of the time not everything occupies this area. And indeed doesn’t, because they collide and generally blow up :slight_smile:

Cas :slight_smile:

#29

The problem is not only that quite a few end up at the root node (not only the middle, but also the center axes) but for every level, this problem exists, causing the item to be pushed to the parent. So it’s definitly not 0.1%, because when the cells get smaller, the ‘boundingbox hitting center axes’-problem grows exponentially.

With my shifted grids, you approach 0.0% as there are no edge-cases, at all.

#30

Hm, seems to work just fine here though. For the simplicity I’d go for my solution every time :slight_smile:

Cas :slight_smile:

#31

If it works and the performance is not a problem, don’t change it. Premature optimisation is bad.

It just won’t scale well, for culling zillions of items, like when you’re rendering forests with millions of trees. Let’s say you’d have 1% in your ‘catch all’ node, that would be 10K items. That will really grind your physics engine to a hold.

With 1000 items in the world that 1% is not going to affect performance noticably.

#32

Dead right :slight_smile:

Cas :slight_smile:

#33

Because of this thread I am planning on implementing some tests. I am also planning on releasing the source for everyone to see and review.

So far I am planning to test two collision strategies for each data structure:
-bruteforce (O(n^2) for reference)
-sweep and prune with circles or axis aligned boxes (with insertion sort for O(n), perhaps quicksort for O(n log n)

and the following cases of datastructures:
-No data structure at all
-2d grid
-Regular quadtree (create static quadtree to nth level and add objects accordingly)
-Dynamic quadtree (create static quadtree to nth level to avoid runtime allocation, add objects to nodes until the node is full. Once the node is full, redistribute the objects into child nodes)

I’ll impose no similar limitations as pointed out by Orangy Tang in my solution. This means that I probably can’t squeeze in my “hackish approximation of Quadtree”.

There is one major problem though: how do the advocates of the elegant and simple Quadtree approach handle moving objects especially now that one object may be in multiple nodes?

Do you:

  • simply remove the object when it has moved and reinsert it?
  • clear the whole tree and insert all of the objects again?
  • update the tree from within so that you only ascend only the needed amount and then add the node? How are objects that reside in multiple nodes handled?
  • calculate edge and vertex neighbors initialization time, store references to them and update the node that way? Again, how are objects that reside in multiple nodes handled?
#34

My objects only ever live in one node, and as such, they have a reference to the node that they are currently in, to enable me to very efficiently remove them from the node when they are being moved. I then simply add them back into the quadtree. Seems to work fine, especially as my objects are well distributed spatially, so I don’t run into the case where lots of them end up in bigger parent nodes than necessary, and it’s very fast.

Cas :slight_smile:

#35

Sounds very interesting. Go on - write it with a generic QuadTree interface so we can poke our own algorithms into it so they can shoot it out. :slight_smile: I wouldn’t mind writing a loose quad tree variant and seeing how it compares.

#36

I’ll have to work on this during the weekend. I implemented bruteforce and prune and sweep collision strategies (the difference is 300 fps for 10000 objects in 20kx20k area as you may imagine). I didn’t notice too big of a difference in between insertion sort and quicksort.

What do you want from a generic data structure interface?

Currently I have:


public interface ISpatialDataStructure {

	
	public void add(Entity entity);

	public void remove(Entity entity);
	
	public void collide();
	
	public void update(float dt);
	
	public void draw(Graphics graphics);
	
}

This gives tons of options to anyone developing a data structure. Is there anything else that might be needed?

I’ll probably add an intersection query function for a Rectangle (think of FPS style selection) that returns list of objects it intersects. I am going to use Slick for the testbed so I hope that’s okay for everyone.

#37

Hello (I was previously captain, but decided to change my user name to what is use normally)

I had a few extra hours during the weekend so I put together a little testbed.

So far I have implementations for

  • Prune and Sweep Strategy
  • Regular Quadtree

Regular quadtree introduces a ton of overhead at the moment because objects are re-added to it every single time. For some reason I have a gut feeling that updating objects from the leaf node they are in is not going to be efficient since you don’t know for certain where else the object also resides.

Any opinions on the implementation? I’d like to see more data structures submitted by others. The code should be free to use in open source compatible way (none of the algorithms are particularly hard), but I’d like to see any improvements made to existing implementations also if someone decides to submit their own implementation.

www.students.tut.fi/~valton22/CollisionTest.zip

Keys:

  • Mouse wheel zooms.
  • F1 toggles debug information.
  • Keys move the view.
#38

Are there some missing libraries? Does this require Slick?


$ java org.game.CollisionTest 
Exception in thread "main" java.lang.NoClassDefFoundError: org/newdawn/slick/BasicGame
#39

Yes, it requires Slick. I used Slick for convenience, since I had some existing code related to it.

I wouldn’t entirely ignore this because of Slick as it is quick to install and more than adequate for this kind of situation.

#40

I implemented LooseGrid as featured in N (http://www.metanetsoftware.com/technique/tutorialB.html#section3)

You can take the grid into use by changing the initialization of the data structure in CollisionTest.java to:


ISpatialDataStructure dataStructure = new LooseGrid(200, 200, 100, 100);

and adding the file “LooseGrid.java” with following contents:


package org.game.collision.datastructures;

import java.util.ArrayList;


public class LooseGrid implements ISpatialDataStructure {

	float cellWidth = 0;
	float cellHeight = 0;
	
	private class Cell {
		
		
		Rectangle bounds = new Rectangle(0, 0, 0, 0);
		
		ArrayList<Entity> objects = new ArrayList<Entity>();
		
		
		public Cell(int i, int j) {
			
			float xOffset = sizeX / 2 * cellWidth;
			float yOffset = sizeY / 2 * cellHeight;
			
			bounds.setBounds( -xOffset + i * cellWidth, -yOffset + j * cellWidth, cellWidth, cellHeight);
		}
		
		public void add(Entity entity) {
			objects.add(entity);
		}
		
		public void remove(Entity entity) {
			objects.remove(entity);
		}
		
		public void draw(Graphics graphics) {
			
			if(debug) {
				graphics.setColor(Color.yellow);
				graphics.draw(bounds);
			}
			
			for (Entity entity : objects) {
				entity.draw(graphics);
			}
			
		}
		
		public int getNumObjects() {
			return objects.size();
		}
		
		
		
		public void collide(ArrayList<Collision> collisions) {
			
			for (Entity entity : objects) {
				float xWorldOffset = sizeX / 2 * cellWidth;
				float yWorldOffset = sizeY / 2 * cellHeight;

				int x = (int)((xWorldOffset + entity.getPositionX()) / cellWidth);
				int y = (int)((yWorldOffset + entity.getPositionY()) / cellHeight);	
						

				for(int i = -1; i <= 1; i++ ) {
					
					int xOffset = x + i;
					
					if(xOffset < 0 || xOffset >= sizeX) break;

					for(int j = -1; j <= 1; j++ ) {
						int yOffset = y + j;

						
						if(yOffset < 0 || yOffset >= sizeY) break;
						
							ArrayList<Entity> cellObjects = cells[xOffset][yOffset].objects;
							
							for (Entity foreign : cellObjects) {
								
								if(entity == foreign) continue;
								if(entity.intersects(foreign)) {
									
									collisions.add(new Collision(entity, foreign));
								}
							}

					}			
				}
			}
			
		}
		
		public boolean intersects(Entity entity) {
			return bounds.intersects(entity.getShape());
		}
		
	}

	
	boolean debug = false;
	
	Cell[][] cells = null;

	private int sizeX = 0;
	private int sizeY = 0;
	
	ArrayList<Entity> objects = new ArrayList<Entity>();
	
	public LooseGrid(int sizeX, int sizeY, float cellWidth, float cellHeight, ICollisionStrategy collisionStrategy) {

		this.sizeX = sizeX;
		this.sizeY = sizeY;
		
		cells = new Cell[sizeX][sizeY];
		
		this.cellWidth = cellWidth;
		this.cellHeight = cellHeight;
		
		for(int i = 0; i < cells.length; i++) {
			for(int j = 0; j < cells[i].length; j++) {
				cells[i][j] = new Cell(i, j);
			}
		}	
	}
	
	
	@Override
	public void add(org.game.Entity entity) {
		
		this.objects.add(entity);
		addToCells(entity);
		
	}

	@Override
	public void collide(ArrayList<Collision> collisions) {

		for(int i = 0; i < cells.length; i++) {
			for(int j = 0; j < cells[i].length; j++) {
				if(cells[i][j].getNumObjects() > 0) {
					cells[i][j].collide(collisions);					
				}
			}
		}
		
	}

	@Override
	public void draw(Graphics graphics) {
		
		graphics.setColor(Color.blue);
		graphics.drawRect(-(sizeX/2) * cellWidth, -(sizeY/2) * cellHeight, sizeX*cellWidth, sizeY*cellWidth);
		
		for(int i = 0; i < cells.length; i++) {
			for(int j = 0; j < cells[i].length; j++) {
				if(cells[i][j].getNumObjects() > 0) {
					cells[i][j].draw(graphics);					
				}
			}
		}
		
		
	}

	@Override
	public String getInfo() {
		return "Loose grid data structure by Olli-Pekka";
	}

	@Override
	public boolean isDebugRenderMode() {
		return debug;
	}

	@Override
	public void remove(org.game.Entity entity) {
		objects.remove(entity);
		removeFromCells(entity);
	}

	@Override
	public void setDebugRenderMode(boolean debug) {
		this.debug = debug;
		
	}

	@Override
	public void update(float dt) {
		for (Entity entity : objects) {
			removeFromCell(entity);
			entity.update(dt);	
			addToCell(entity);
		}
		
	}

	@Override
	public float getHeight() {
		return sizeY * cellHeight;
	}

	@Override
	public float getWidth() {
		return sizeX * cellWidth;
	}
	

	
	private void addToCell(Entity entity) {

		float xOffset = sizeX / 2 * cellWidth;
		float yOffset = sizeY / 2 * cellHeight;

		int x = (int)((xOffset + entity.getPositionX()) / cellWidth);
		int y = (int)((yOffset + entity.getPositionY()) / cellHeight);
		
		cells[x][y].add(entity);
			
	
		
	}
	
	
	private void removeFromCell(Entity entity) {
		
		float xOffset = sizeX / 2 * cellWidth;
		float yOffset = sizeY / 2 * cellHeight;

		int x = (int)((xOffset + entity.getPositionX()) / cellWidth);
		int y = (int)((yOffset + entity.getPositionY()) / cellHeight);
		
		cells[x][y].remove(entity);
			
	}
	
	
	
}

It would be possible to make this better by incoporating prune and sweep. This would be done by changing the addToCell and removeFromCell functions to only remove and add the object if it doesn’t intersect with the square. This way the order of the objects is preserved for insertion sort. Furthermore one has to change the sorting algorithms so that they sort the other objects and not the tested object.

Anyone up for Loose Quadtree or improving my Regular Quadtree?