What are your thoughts on this new boid code?

[GoogleCodeExporter]

Branch name: boids

Purpose of code changes on this branch:

Make boid neighbor computations faster.  This is accomplished by overlaying a 
grid on the world, putting the boids into the grid cells.  Only boids in cells 
that are within the given radius of the target boid are considered to be 
neighbors.

Here's some benchmarks comparing to the default branch:

Before:

% go test -i ./ai && go test -'test.bench=.*' ./ai
testing: warning: no tests to run
PASS
BenchmarkUpdateBoids100     2000       1,259,838 ns/op
BenchmarkUpdateBoids500      100      16,465,980 ns/op
BenchmarkUpdateBoids1000          50      61,628,240 ns/op
ok      code.google.com/p/min-game/ai   8.756s

After:

% hg update boids
8 files updated, 0 files merged, 0 files removed, 0 files unresolved
% go test -i ./ai && go test -'test.bench=.*' ./ai
PASS
BenchmarkUpdateBoids100    10000        226,759 ns/op
BenchmarkUpdateBoids500     1000       1,745,865 ns/op
BenchmarkUpdateBoids1000         500       5,106,948 ns/op
ok      code.google.com/p/min-game/ai   7.716s

When reviewing my code changes, please focus on:

This modification needs some cleanup, but I am sick of it for now.

Well, I dislike the fact that the Boids interface needed to change.  I made the 
Boid() method return a pointer instead of a value, because I need to test for 
equality with the current boid so that it does not consider itself a neighbor 
of itself.  (See the continue statements in the loops in matchVel, moveCenter, 
and avoidOthers.)

If the ai.Boid field of Herbivore could be unnamed then this wouldn't be as 
ugly of a change.  Apparently, however, JSON won't marshal unnamed fields, so 
everything had to be named.

After the review, I'll merge this branch into:
default

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

[GoogleCodeExporter]

OK, the previous "before" benchmark was unfair because the boids were 
accidentally set to avoid *all* of the terrain in the world (this lead to extra 
distance computations for each boid).  Here's the fair "before" results:

% go test -i ./ai && go test -'test.bench=.*' ./ai
testing: warning: no tests to run
PASS
BenchmarkUpdateBoids100     5000        589,871 ns/op
BenchmarkUpdateBoids500      100      12,945,180 ns/op
BenchmarkUpdateBoids1000          50      55,335,560 ns/op
ok      code.google.com/p/min-game/ai   8.338s

Still better.

Original comment by burns.ethan@gmail.com on 31 Dec 2012 at 8:57

[GoogleCodeExporter]

Rev 4cf4bb6d9246 has too much going on in it for my ill brain to comprehend. 
There's a lot of noise in ai/boid.go from the changes related to the Boids 
interface and the Boid struct's Body field, and that's keeping me from 
following the important changes to the logic. I'm fine with named fields, but 
those should've been separate commits. If you could split it up for me, I'd be 
able to give better feedback.

The grid stuff seems good, aside from a bad comment for grid.index() and I 
don't understand what wrap() is doing in the negative n case. Also, it seems 
like the bound <= 0 test should be first.

Original comment by Mcco...@gmail.com on 31 Dec 2012 at 11:18

[GoogleCodeExporter]

Wrap is copy/paste from world.go.  We've been using it for a long time now; but 
you are right, the bound <= 0 test should be first (see issue 138).

Sorry about the noise, but I made the grid change before realizing that I 
needed to make the other annoying change, so I didn't undo my grid fix first.  
I am not sure how to split this up now.  Should I just open a new branch and do 
it again?  Seems annoying.

Original comment by burns.ethan@gmail.com on 31 Dec 2012 at 11:28

[GoogleCodeExporter]

In the boids branch:

hg update -r 944988d6a00a # before the big change
# make boids change, then
hg commit -m 'blah blah'
# make field change, then
hg commit -m 'blee blee'
hg merge # will probably have conflicts, but should be easy to resolve

Original comment by Mcco...@gmail.com on 31 Dec 2012 at 11:53

[GoogleCodeExporter]

I forgot:

hg commit -m 'Boid logic changes on their own.'

Original comment by Mcco...@gmail.com on 31 Dec 2012 at 11:55

[GoogleCodeExporter]

Interesting, but as far as I can tell, that would make the commits to the 
default branch.  Can you see a way to do it to the boids branch, or maybe you 
don't care about the branch?

Original comment by burns.ethan@gmail.com on 1 Jan 2013 at 4:39

[GoogleCodeExporter]

I see, it will just make an anonymous branch that I can merge into boids.

Original comment by burns.ethan@gmail.com on 1 Jan 2013 at 4:51

[GoogleCodeExporter]

OK, sorry for the spam, but this isn't working as I suspected.

I started from c26ffe6a3618 because I wanted the two changes after 
944988d6a00a, as they fix things that (both of these changes appear in the 
boids branch, though one of them was re-done by hand).  I wanted to split the 
change into three commits: 1) change Boids.Boid to return a pointer, 2) Change 
Boid to contain a Body not a *Body, and 3) add the grid.  I have #1 and #2 done 
from c26ffe6a3618, but hg wants to commit them both to the default branch, and 
they have moved tip.  This is really not the desired behavior, in my opinion.  
I think that we want tip to remain at 6fa5b88572e6, with these changes forming 
a new unnamed branch that will soon be merged into boids.  Correct?  If so, 
what am I doing wrong?

Original comment by burns.ethan@gmail.com on 1 Jan 2013 at 5:16

[GoogleCodeExporter]

I thought of a much less invasive way to implement the grid change without 
requiring embedded Boids and *Boids everywhere.  It shouldn't be too 
controversial of a change so I plan to commit it right to default.

Original comment by burns.ethan@gmail.com on 1 Jan 2013 at 3:53

• Changed state: WontFix