Seriously, I did a lot of such simulations (in graduate school) and usually the simplest thing is the best.
-----
[1] Let's say your world is 100x100 units. You create 2D array of 10x10 cells (preallocate each cell to be able to hold max number of agents, so that you don't fragment memory and waste time on allocations/garbage collection/etc.).
In each step of the simulation, you go through all agents and place them in the correct cell (that's O(N) and constant is actually really cheap => cell[0.1 x agent.x][0.1 x agent.y]).
Then for the interactions, just check agents in your cell and also 8 neighboring ones (that's practically O(N) because of repulsion forces).
Huh, I had thought about that, but because the bins aren't dynamic, like they are with trees, I figured it would give some odd aberrations. I'll try this first since it's the simplest. Thanks. I didn't know that Craig Reynolds tried it out this way also.
Interaction with Groups of Autonomous Characters
http://www.red3d.com/cwr/papers/2000/pip.html
Big Fast Crowds on PS3
http://www.red3d.com/cwr/papers/2006/PSCrowdSandbox2006.html
Seriously, I did a lot of such simulations (in graduate school) and usually the simplest thing is the best.
-----
[1] Let's say your world is 100x100 units. You create 2D array of 10x10 cells (preallocate each cell to be able to hold max number of agents, so that you don't fragment memory and waste time on allocations/garbage collection/etc.).
In each step of the simulation, you go through all agents and place them in the correct cell (that's O(N) and constant is actually really cheap => cell[0.1 x agent.x][0.1 x agent.y]).
Then for the interactions, just check agents in your cell and also 8 neighboring ones (that's practically O(N) because of repulsion forces).