# Boids, a way not to check flock every update?

## Recommended Posts

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.

Spoiler


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 isn't exact but should give an idea.

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?

##### Share on other sites

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.

##### Share on other sites
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.

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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:

##### Share on other sites

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.

## Create an account

Register a new account

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 12
• 16
• 9
• 14
• 10
• ### Forum Statistics

• Total Topics
632657
• Total Posts
3007680
• ### Who's Online (See full list)

There are no registered users currently online

×