I'm doing a simulation of flying birds for my thesis.

I am using the usual steering behaviors: Cohesion, Separation, Velocity Match and Obstacle Avoidance (to avoid terrain).

The program is written in C# and uses Unity3D. I have disabled physics for the boids.

I'm also using alglib to calculate K-nearest neighbors using AKNN. alglib uses k-d trees for this.

So here are the fps I get:

100 boids = 60 fps

200 boids = 35 fps

300 boids = 23 fps

500 boids = 13 fps

1000 boids = 5 fps

As the number of boids increases, performance degrades rapidly. I'd like to do something to improve it, but sadly I am using the free version of unity3D, which does not have a profiler.

Is the performance I'm getting good? I haven't found results online for this.

Should I find another library instead of alglib?

By the way, you can see the program online here. Requires unity3d plugin.

I have made some measurements using the StopWatch class of the .net framework.

When using the following steering behaviors I had the results below - using 500 boids.

Time to build K-D tree: 2.34ms. So this is not the problem.

Time to update boid steerings (all 500 boids, average time of N frames)

Behaviors used: Cohesion, Separation, VelocityMatch, ObstacleAvoidance => 46.77ms

Behaviors used: Cohesion, Separation, VelocityMatch, ObstacleAvoidance => 39.55ms

Behaviors used: Cohesion, Separation, VelocityMatch, ObstacleAvoidance => 24.44ms

So by not using some behaviors the time dropped significantly. The difference from not using VelocityMatch to not using Cohesion was bigger because Cohesion uses k = 30 for aknn while velocity match uses k = 10. When I set k = 10 for cohesion the time dropped as well.

This is the code that behaviors use to get k-nearest neighbors:

public class Flock
{
	List<Entity> boids;
	alglib.kdtree kdt;

	public Flock(params Entity[] _boids)
	{
		boids = new List<Entity>();

		Add(_boids);
	}
	
	public int GetNeighborhoodInfo(Entity character, int maxNeighbors, float maxDistance, float minDotProduct, double aknnApproxVal, out Vector3 center, out Vector3 avgVeL) 
	{
		var point = new double[3]{character.position.x, character.position.y, character.position.z};

		var results = new double[0, 0]; // the array containing the results (points of the k nearest neighbors)

		int neighbors = (maxNeighbors == 0 ? 0 : alglib.kdtreequeryaknn(kdt, point, maxNeighbors, aknnApproxVal));

		// get the results
		alglib.kdtreequeryresultsxy(kdt, ref results);

		center = avgVeL = Vector3.zero;

		// where is the character looking
		var look = character.transform.forward;

		int count = 0;
		for (int i = 0; i < neighbors; ++i)
		{
			var pos = new Vector3((float)results[i, 0], (float)results[i, 1], (float)results[i, 2]);
			var vel = new Vector3((float)results[i, 3], (float)results[i, 4], (float)results[i, 5]);

			if (pos == character.position)
				continue;


			if( Vector3.Distance(character.position, pos) <= maxDistance )
			{
				// check for angle
				if( minDotProduct > -1.0f )
				{
					var offset = pos - character.position;
					if( Vector3.Dot(look, offset.normalized) < minDotProduct )
						continue;
				}
				
				center += pos;
				avgVeL += vel;
				++count;
			}
		}

		center /= count;
		avgVeL /= count;


		return count;
	}
}

I think it's pretty straight-forward... So I guess the only solution is to search for another library for aknn? I read somewhere that akkn could be made more efficient when using octrees instead of k-d trees.

I see what you guys mean, but the problem is that alglib expects the array to be of this type. And even If allocate earlier it will still be re-allocated by alglib (that's why it takes the array by reference) as you can see below:

// get the results
alglib.kdtreequeryresultsxy(kdt, ref results);

Also as far as I'm aware dynamic memory allocation in C# is fast (I read it's just a pointer increment, not sure how it works).

I can't switch to C++, it's too late now :P Also Unity doesn't support C++ so...

The last not so obvious problem you might have is colliders. You wrote above you "disabled" physics on your agents. Does this mean you removed the RigidBody component or do you set it to isKinematic? Do you still have colliders attached to the objects?

The agents do have rigidbodies attatched to them because I use them to set the velocity of the agents. However they do not have colliders attatched to them.