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.