Space Partitioning

The primary bottleneck in the boid code from lab 1 was the GetNeighbors method. This method was called by each boid n number of times, where n is the number of boids. This made the combined complexity of the GetNeighbors call O(n2). Naturally this does not scale well when we increase the number of boids. Fortunately it is possible to improve this performance by taking advantage of the fact that all the interactions are limited to only occur within a set radius from any given boids. Any boid outside this radius is guaranteed to not have an impact on the simulation and can thus safely be ignored. 

For this approach to work in practice we need a data structure which is able to represent the relative proximity of two boids. In this project we used a grid implemented as a 3D matrix, but there are a number of other possible data structures. The grid works by partitioning the simulation space into a number of cubes. During the simulation each boid is assigned to one of these cubes. The assignment is based on the position of the boid, and updated accordingly as the boid moves during the simulation. For instance if a boid is located in the center of the simulation space it is going to be assigned to the center cube. To find the potential neighbors of a given boid we only have to check for boids in the current and adjacent cubes. It is important to note that this only works if our cubes are large enough, otherwise we are going to run the risk of ignoring possible neighbors. If we choose the cube dimension to be the largest of our interaction-radii we ensure that we will never miss a potential neighbor. The partition grid works the same way in 2D as in 3D. Below is a simple 2D illustration of how the partition grid works:

		B3
B2	B0
	B1

Boid0 is the one calling the new GetNeighbors method. The method is only ever going to iterate through the squares in the figure and return Boid1, Boid2, Boid3, regardless of how large our total simulation space is. Given that our square dimension is set to the largest interaction-radius we can see that Boid1 and Boid2 are going to have some form of interaction with Boid0. Only Boid3 is returned unnecessarily, i.e. it is returned even though it is not going to interact with Boid0. If we imagine that our simulation space consists of hundreds or thousands of squares with a large number of boids in them it is clear that this grid approach is a significant improvement over the old GetNeighbors method.