Quadtree for moving objects

Performance Tuning
#41

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. :slight_smile:

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.

#42

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

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 :slight_smile:

#44

The beauty of microbenchmarks is the fact that if you don’t show it, it didn’t happen :slight_smile:

#45

[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.

#46

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 :slight_smile:

#47

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.

#48

Hi, I was playing around a bit with this matter the other day and I found “kinetic data structures” to be very interesting for something like this. I’m short on time right now, but as a brief explanation: For each entry calculate the distance to the border of the quadtree node it’s in. Then from the distance and the (maximal) movement speed calculate when the next update might be possible. Simulate on and just check the time if there’s any need to update. If no update is required you’re done, otherwise you just need to update a few entities (usually).
I have tried to implement it and it seems to work so far, but I neither have any benchmarks nor any real tests I made about stability etc. …I just liked the idea ;D
What do you think about this approach?

Greetings,
Mene

#49

I am perhaps coming into this a little late. But anyway, since i just finished my quad tree implementation for a RTS game I though I would give my experiences and suggestions. Feel free to ignore or otherwise pipe to /dev/null.

My current Quad tree is dynamic and gets 100 game frames per second with 20K units in a type of “boid” simulation. 60% of the CPU usage is updating the boids. Not the quad tree. Given that my target game frame per second is 5-10. This is basically done until it pops up on a profiler.

I use a few tricks that have already been suggested. The only “tricky” thing I do is keep track of adjacent nodes at the same level (or higher). Then when i call revalidate and I find a unit that has moved out of the current leaf, I can send it directly to the adjacent node (which may or may not be a leaf). This provides O(1) performance average case per unit thats moved, and O(ln n) worst case. rather than re add from the root that gives O(ln n) average case. It made quite a big difference and it means that increasing the time between game ticks does not increase the work needed per tick (too much).

Now i can do 2 fast queries on this structure. k nearest neighbor and “area queries”. Both work in about O(ln n) time but the kNN has a larger over head that area queries. Note that about O(ln n) time here means we are ignoring the size of the returned result. This does affect performance. I don’t use these for collision detection, but rather “unit” sensors… ie what airplane is closest to me.

For collision I do an “internal” area query. This still has expected performance O(ln n) for very large units. But average O(1) for smaller units. Since we expect large units to be rare and move slower than small units, so this works pretty good.

In practice I am getting less than a 5% cpu overhead for all these features and can burn CPU time on AI and rendering.

However I have not got to the “what is visible” bit yet. And I use massive vision distance for units, I hope that area queries are more than good enough (should be since I don’t need to have a regular area).

Also just one other comment. Insertion sort has performance O(n^2) not O(n) as some post claimed. The best any sort can do is O(n) on a sorted list. Since it must take O(n) comparison just to show that a list is sorted. (merge sort and insertion sort gets O(n) for sorted lists. Basic Quick sort degenerates to O(n^2) ) . You can only do better with radix sorts (not a comparison sort). In fact I did collision detection with a sweep whatever using radix sort. It was fast.

#50

Thanks for posting this - lots of good information and ideas :slight_smile:

I think the post that referred to insertion sort as being O(n) was working with uniformly distributed slow moving entities. So the list is known to be mostly in order at each step. While in reality I’m sure that the number of crossing entities is relative to n (probably sqrt(n) ?) , in the simulation he posted - with so few crossings per time step - it’s seems reasonable to refer to it as O(n).