Nine years too late to help Iskar Jarak but I will chime in since others may find this old question in a search.
The key point is that almost anything is better than the naive O(n²) approach of looking at every pair of boids. So as Iskar suggests, any kind of tree based spatial data structure is a vast improvement, being basically O(n log n). That is: each of the n boids needs to look up its neighbors each of which is O(log n).
It should be noted that “hit detection” mentioned by Desmond Vehar is a slightly different problem, asking “is this query position ‘inside’ any of the ‘objects’ in my data structure?” In multi-agent simulations we want to find multiple neighbors. Sometimes “nearest N neighbors” or perhaps “all neighbors within a given radius of the query position.” It usually is sufficient to describe a boid as its center point and filter by distance between points, producing a “query sphere.”
In his algorithms courses Tim Roughgarden keeps asking “can we do better?” And indeed—while O(log n) is better than O(n) to look up a neighbor—the best is constant time lookup, O(1). Here hash tables (aka unsorted maps) are our friends.
These two ideas, multiple neighbors and hashing, lead to a good approach for accelerating multi-agent simulations: spatial hashing into voxels(/boxes/lattices). Each voxel contains a collection of boids/agents. The continuous space position (usually 2 or 3 floats) of the agent is converted into voxel coordinates (2 or 3 ints, by a scaled “floor” operation), which are hashed together to produce a “voxel ID” which is used as a key in a hash table of voxels. So in O(1) constant time, like an array reference, you can look up the voxel which contains a collection of all agents currently in the same voxel. The “query sphere” will normally overlap multiple voxels. These can be found by offsetting the query point by multiples of the voxel spacing distance. The contents of these several voxels are merged together to form a collection of potential neighbors, then filtered by distance. As agents/boids move, they compare their old and new “voxel ID” and if not equal, they remove themself from the data structure, then reinsert at the new position.
Query sphere in voxel space:
Resources:
There are roughly a zillion types of “spatial data structure”/“spatial database.” See this Wikipedia article for a survey: Spatial database. See also Hanan Samet’s early papers: 1989’s Hierarchical Spatial Data Structures and 1995’s Spatial Data Structures.
In my own work in the early 2000s, I used fixed sized collection of voxels, addressed with i,j,k coordinates:
Interaction with Groups of Autonomous Characters in 2000, and Big Fast Crowds on PS3 in 2006. Later, I switched to using the “spatial hashing into voxels” approach, which does not require a priori specification of the 3d voxel grid dimensions, and has zero overhead for sparse agent distribution with many empty voxels.
