Jump to content
  • Advertisement
Scouting Ninja

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.:P

 

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!