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 
Cas
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.
Hm, seems to work just fine here though. For the simplicity I’d go for my solution every time
Cas
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.
Dead right
Cas
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:
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
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. I wouldn’t mind writing a loose quad tree variant and seeing how it compares.
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.
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
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:
Are there some missing libraries? Does this require Slick?
$ java org.game.CollisionTest
Exception in thread "main" java.lang.NoClassDefFoundError: org/newdawn/slick/BasicGame
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.
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?
Unfortunately my internet connection is incredibly slow right now (stupid data caps). I’ll get the slick libraries in a few days when I’m back up and running properly again. Hopefully I’ll find time next week to have a play with some implementations.
A couple of thoughts though: can the drawing of Entities be moved out of the datastructure? Perhaps there could be an method to get an Iterator instead which can be used externally to draw them. If debug information needs to be included then this could be provided by the datastructure as a String, or some predefined Debug class.
As a side note, your life might have been easier with sweep and prune if you’d just made a Comparitor and used standard Collections/Arrays sort methods. I believe those methods use quicksort on large arrays, and move to insertion sort once partitions are small enough to not warrant the overhead.
I’ve downloaded slick and run the test. I’m not sure of the value of the visualisation though, since once I raise the number of entities to 10k it drops to under 1 fps (it’s rendering about once every 15 updates - each timed update and render takes less than 100ms).
With 1k or fewer entities any naive implementation will be fine (say, <1ms for updates and collision detection), so the visualisation doesn’t seem all that useful. Here’s a test class “CollisionTest2” that drops any graphical output - still using your existing interfaces apart from one extra method in ISpatialDataStructure:
public void clear();
I prints the mean and standard deviation of 50 update+collide calls. Your baseline implementations give:
Reference datastructure using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
1000 entities takes 192ms +/- 109.10838878372223
Reference datastructure using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
10000 entities takes 4909ms +/- 244.99901555071327
Reference datastructure using sweep and prune strategy(insertion sort) by Olli-Pekka Valtonen
1000 entities takes 152ms +/- 56.00231144306528
Regular Quadtree using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
1000 entities takes 28860ms +/- 677.3654851916602
package org.game;
import org.game.collision.Collision;
import org.game.collision.datastructures.*;
import org.game.collision.strategies.*;
import org.game.collision.strategies.SweepAndPruneStrategy.SortingAlgorithm;
import java.util.Random;
import java.util.ArrayList;
public class CollisionTest2{
public static void test(ISpatialDataStructure dataStructure, int entityCount){
Entity[] entities = new Entity[entityCount];
ArrayList<Collision> collisions = new ArrayList<Collision>();
Random random = new Random();
float maxWidth = dataStructure.getWidth();
float maxHeight = dataStructure.getHeight();
//run 20x50 test updates
int runs = 20;
int updatesPerRun = 50;
long[] times = new long[runs];
long mean = 0;
for(int i = 0; i < runs; i++){
dataStructure.clear();
//create the entities
for(int j = 0; j < entityCount; j++) {
float radius = 10 + random.nextFloat() * 90f;
float x = (-dataStructure.getWidth() + radius) / 2 + random.nextFloat() * (dataStructure.getWidth() - 2*radius);
float y = (-dataStructure.getHeight() + radius) / 2 + random.nextFloat() * (dataStructure.getHeight() - 2*radius);
x = Math.max(x,-maxWidth/2);
x = Math.min(x,maxWidth/2);
y = Math.max(x,-maxHeight/2);
y = Math.min(x,maxHeight/2);
float velX = random.nextFloat() * 10;
float velY = random.nextFloat() * 10;
Entity entity = new Entity(dataStructure, x, y, velX, velY, radius);
entities[j] = entity;
dataStructure.add(entity);
}
//do a run
long startTime = System.nanoTime();
for(int j = 0; j < updatesPerRun; j++){
dataStructure.update(10);
dataStructure.collide(collisions);
collisions.clear();
}
times[i] = System.nanoTime()-startTime;
mean += times[i];
if((i & 1) == 0){
System.out.print(".");
System.out.flush();
}
}
System.out.println("\n"+dataStructure.getInfo());
mean /= runs;
long variance = 0;
for(int i = 0; i < runs; i++)
variance += (mean-times[i])*(mean-times[i]);
variance /= runs;
double standardDeviation = Math.sqrt(variance);
System.out.println(entityCount+" entities takes "+(mean/1000000)+"ms +/- "+(standardDeviation/1000000));
}
public static void main(String[] args){
int width = 20000;
int height = 20000;
//ISpatialDataStructure dataStructure = new ReferenceDataStructure(width, height,new BruteforceStrategy());
ISpatialDataStructure dataStructure = new ReferenceDataStructure(width, height, new SweepAndPruneStrategy(SortingAlgorithm.InsertionSort));
//ISpatialDataStructure dataStructure = new RegularQuadtree(width, height, 7, new SweepAndPruneStrategy(SortingAlgorithm.Quicksort));
test(dataStructure,1000);
}
}
The perils of microbenchmarks! You’re saying a regular quadtree approach to collision detection takes 28 seconds for 50 updates and just 1,000 entities? The whole reason I switched to quadtrees for my game “engine” is that I needed to do about 2,000 entities in a millisecond!
Cas
The beauty of microbenchmarks is the fact that if you don’t show it, it didn’t happen
[quote]The perils of microbenchmarks!
[/quote]
I wouldn’t call these micro-benchmarks, since they create 20 complete situations and run them for 50 iterations. This is a benchmark for roughly uniformly distributed, slowly moving objects in an area 200 times their maximum radius.
I think I didn’t make the quad tree’s extra “clear()” method properly (realised after going to bed last night). I’ll check that and repost its time.
Edit: Ok, the correct timing is:
Regular Quadtree using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
1000 entities takes 2700ms +/- 271.007926407224
Cas, we’re only saying that that implementation takes that long. If you looked at the code you’d see it was completely unoptimised (lots of unnecessary method calls), not to mention the fact that the tree gets rebuilt from scratch each update. As far as I can tell it was just supposed to be a baseline.
I added a print out of the average number of collisions. That quad tree implementation gives double the number of collisions as sweep and prune - so I’m guessing there’s also a bug in there somewhere.
Finally, when using a sort method for sweep and prune that makes use of the fact that entities are mostly ordered it carves about 20% (at 10k entities) of that time off. Most of the remaining time is spent comparing entities so it looks like moving to some form of 2D sorting (like quad trees) would make sense at that point.
50 iterations isn’t up to much… that’s not even 1 second of game play! I’d run them for a lot longer, and also plonk things of varying sizes in there, and also have them move in a bit less of a random way perhaps, such as flocking.
Cas
There’s definitely a bug in there. I’ll attempt to fix this once I have more time. I am planning on extending the test bench to some queries: query against a circle (point & radius) and a rectangle, since those are pretty important in my game.