Optimize this
Published April 7th, 2006 in ITP, blog, p5, teaching_
If you look at my nature of code flocking example, you’ll notice that the algorithm involves calculating the distance between all of the system’s elements, i.e. for every “boid”, check and see how far away it is from every other boid. This works quite well for, say, around 100 elements.
100 x 100 = 10,000 cycles. No problem.
To check 1,000 elements:
1,000 x 1,000 = 1,000,000 cycles. Ok, but getting a bit slow. . .
Let’s try 2,000 elements:
2,000 x 2,000 elements = 4,000,000 cycles. Now, we’re really getting slow. Really, see how slow it is.
What if we could divide the screen into a grid of arbitrary size, take all 2,000 elements, and each object’s location within that grid? Then, we could simply test the objects that were in the same relative area at any given moment. Imagine a 10 x 10 grid. In a system of 2,000 elements, on average, approximately 20 elements would be found in each cell (20 x 10 x 10 = 2,000).
Each cell would then require 20 x 20 = 400 cycles. With 100 cells, we’d have 100 x 400 = 40,000 cycles, a massive savings over 4,000,000.
Here’s an example that implements this optimization. It’s a great deal more efficient than this slow, pathetic version. The code could use some fixing up and could be improved to be more modular / object oriented, but it’s a nice start for solving these types of problems. We could also use a potentially more efficient data structure than an ArrayList for every cell.
Yeah, this is the best way, craig reynolds calls it bin-lattice spatial subdivision.
I used it on echo chamber (www.chrisoshea.org/projects/echochamber/), craigs paper is here:
http://www.red3d.com/cwr/papers/2000/pip.pdf
If you’re on a slower machine (like me, e.g. on a Mac PB 1GhZ), the drawing seems to be the performance bottleneck. In your flocking example, 1000 boids are already impossible for me, even if I comment the flock() method (i.e. no location calculations).
If spatial considerations are of importance, I would consider using a Voronoi diagram. As far as I know, Fortune’s algorithm is the fastest. (see here http://www.cip.informatik.uni-muenchen.de/~viermetz/cg/index.html). In my experience, it’s much faster than bin-lattice subdivision.
A frends of Ed book (Making things move) taught me you dont need to check every element against very other. Theese loops checks everything against everything.
for(int i = 0; i
Dont know why my post was cut short but lets try again.
psudo code to check everything against everything.
for(i=0; i
You can get a boost with a minor change to the loops starting on line 73:
int s = temp.size();
for (int n = 0; n < s; n ) {
Thing t = (Thing) temp.get(n);
// Against every other Thing after the current thing
for (int m = n 1; m < s; m ) {
Thing other = (Thing) temp.get(m);
// As long as its not the same one
float d = dist(t.x,t.y,other.x,other.y);
if (d < t.r/2 other.r/2) {
t.highlight = true;
other.highlight = true;
}
}
}
Setting m=n 1 restricts the comparisons to only check the current item against everything after it in the array so each comparison only happens once. However, this will only work for symmetrical tests like intersection, notice that you set the highlight on t and other to true when there is an intersection.
Wordpress managed to remove all of my plus signs. They should be in the for() loops and the distance test.