So I am using Boids to create flocking behavior for  large amount of zombies.The problem I have is in my Separation pass I check the distance of each zombie compared to each zombie. I think this is wrong.

void Seperation (float MaxDistance){
	int TempInt = 0;
	int SubCount = 0;
	//HiveMind is the parent of all the zombies
	while (TempInt < HiveMind.transform.childCount) {//So this will run once each child

		while (TempInt < HiveMind.transform.childCount){//The problem is now I need to run every zombie again to check there distance
			float Distance = GetDistanceOf(HiveMind.transform.getChild(TempInt),HiveMind.transform.getChild(SubCount));

			if (Distance < MaxDistance){
				AvoidFlockMember(HiveMind.transform.getChild(SubCount));//This moves away from the flock member.
			}
			SubCount +=1;
		}
		TempInt +=1;
	}
}

This causes a exponential cost. 10 Zombies need to check all of the zombies 10*10 = 100 loops. Not bad but 1 000 *1 000 = 1 000 000 loops. So I am getting a power of two amount of loops.

I feel that there is some thing simple I am missing?

You can use a spatial-partitioning method (e.g. quadtrees or kd-trees) to quickly discard most of the N^2 possible interactions. "Broad phase collision detection" could be a useful thing to search the web for.

1 hour ago, alvaro said:

"Broad phase collision detection" could be a useful thing to search the web for.

This does look like what I need. Why is the answers always this difficult.

Thanks very much for the help.

The most famous of flocking birds, starlings, only pay attention to their 7 nearest neighbors and yet the group, as a whole, makes for a spectacular display.

9 hours ago, IADaveMark said:

The most famous of flocking birds, starlings, only pay attention to their 7 nearest neighbors

I did this whole roundabout thing where I tried assigning colors to the zombies to group them, then I realized that I was just adding extra vectors and could use the position instead. Then I realized the positions where grid spaces.

After wasting a lot of time, I implemented Broad Phase.

Now zombies have packs with one leader zombie who holds a list of the zombies in the pack. The larger the pack the less distance is used to assign packs, smaller packs use large distances.

The way it looks from above is like a ocean. The zombies gather in groups then split and regroup. When in a city it looks like they are checking every alleyway for food. It's amazing how interesting they act considering how simple this code is.

I have 10 000 zombies now. To reach my goal of 1 000 000 zombies I will batch some zombies. So 1 zombie is a 100 zombies visually.

Remember you don't need full flocking computations for every zombie at every frame: they can decide periodically (go straight for N frames unless they hit a wall), abandon flocking for a variable time while they follow a fixed path (e.g. from the beginning to the end of a narrow alley), spread computations over multiple frames.

Actually, I usually update my behaviors (of all types) about every 250-400ms. If you set each zombie's next check at a range about that big, the randomness will spread their updates out automatically so they aren't all on the same frame. Also, the variability leads to a more organic feel on a per zombie basis.

18 hours ago, IADaveMark said:

the randomness will spread their updates out automatically so they aren't all on the same frame.

This is a great idea thanks. I was looking for a way to make them more jittery, the move way too smooth for zombies.

I have been messing with the final vector to get things to be random; that isn't working. Making the update times random would result in better movement.

Also, just because the tick time is 250-500ms, doesn't mean you should necessarily change your vector that often. There's all sorts of things you can do to make them seem... er... less than capable.

Perhaps some tips on randomness in here:

http://www.gdcvault.com/play/1014496/Using-Randomness-in-AI-Both

FYI, you're inner while loop is infinite, I assume it should be:

while (SubCount < HiveMind.transform.childCount){

And you should be reseting SubCount to 0 every loop. This will get you N^2 loops and distance calculations. An easy optimization is don't reset SubCount to 0, but set it to TempInt + 1, and then process 2 boids at the same time:

				AvoidFlockMember(HiveMind.transform.getChild(SubCount));//This moves away from the flock member.
				AvoidFlockMember(HiveMind.transform.getChild(TempInt));//This moves away from the flock member.