Faster, but possibly approximate neighbor computation

[GoogleCodeExporter]

For boids, we don't really care if the local neighborhood is truly the set of 
boids within the circular range defined by some radius; any rough neighborhood 
will do.  The boids can probably be much faster by using something approximate; 
hopefully, something that doesn't depend on the number of boids.  This will 
reduce the CPU load and allow us to increase the number of each boid type.  
Additionally, once we add carnivores they will probably need to be able to 
quickly find which herbivores are near them so that they can chase one.

Here's one idea:

An array with an entry for each world location.  Each entry is a slice of all 
herbivores at the corresponding location.  We can find the neighbors of a boid 
by scanning the rectangle of locations around it.  Carnivores can do the same.  
The neighborhood computation will then be constant for each boid (constant in 
the neighborhood size), instead of linear in the number of boids.  The problem 
is that this constant can be large; Cows have a neighborhood of 30 tiles and a 
rectangle of 30x30 tiles has 900 tiles that would need to be checked for each 
Cow.

Original issue reported on code.google.com by burns.ethan@gmail.com on 29 Dec 2012 at 8:30

[GoogleCodeExporter]

This paper does almost exactly what I just said: 
http://www.red3d.com/cwr/papers/2000/pip.html

Also, reading it made me think that we don't have to have one cell for each 
location, but we can use whatever granularity we want.

Original comment by burns.ethan@gmail.com on 29 Dec 2012 at 9:13

[GoogleCodeExporter]

Sounds fine, but the "hard" part is coming up with a nice way to update the 
array whenever an entity moves. Ideally it won't require adding a parameter to 
the move/update method(s).

Original comment by Mcco...@gmail.com on 29 Dec 2012 at 9:18

[GoogleCodeExporter]

Is it any slower to just recompute it each time? Pretty much everything moves 
after each frame, so might as well just compute it from scratch after 
everything moves or at the beginning of each frame before it is needed.  Right?

Original comment by burns.ethan@gmail.com on 29 Dec 2012 at 9:33

[GoogleCodeExporter]

I'm convinced.

Original comment by Mcco...@gmail.com on 30 Dec 2012 at 9:44

[GoogleCodeExporter]

This issue was closed by revision 136669ab2221.

Original comment by burns.ethan@gmail.com on 1 Jan 2013 at 9:34

• Changed state: Fixed