• Advertisement

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

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

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
2 hours ago, PSvils said:

but set it to TempInt + 1, and then process 2 boids at the same time:

I considered loop unrolling at the start but the problem is that zombie packs can be any size from 4 to 84. I don't know if there is a way to do loop unrolling with code during runtime; or if it would be faster than just using a for/while loop.

Currently my code isn't doing badly. I have a pack leader that decides overall movement and only updates it'self and pack members. Then when near a other zombie pack they will share the list of zombies to avoid each other.

Packs < 51% zombies of a large pack merges with the new pack and solo zombies always merge with a pack. All zombies respond to the NavMesh for now.

Here is a quick sketch of how it works.

BoiadsProgress.jpg.2af1716db8c9dd9bccdd477def89c3eb.jpg

 

I am making good progress on the game and I am thinking of making a gamedev blog for it, but I want to work on it a bit more before revealing to the public.

Share this post


Link to post
Share on other sites
21 minutes ago, Scouting Ninja said:

I considered loop unrolling at the start but the problem is that zombie packs can be any size from 4 to 84. I don't know if there is a way to do loop unrolling with code during runtime; or if it would be faster than just using a for/while loop.

Not sure what you mean by loop unrolling. You're currently unnecessarily processing boid interactions twice, when you could visit each pair only once:

void Seperation (float MaxDistance){
	int TempInt = 0;
	//HiveMind is the parent of all the zombies
	while (TempInt < HiveMind.transform.childCount) {//So this will run once each child
		int SubCount = TempInt + 1;
		while (SubCount < 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.
				AvoidFlockMember(HiveMind.transform.getChild(TempInt));//This moves away from the flock member.
			}
			SubCount +=1;
		}
		TempInt +=1;
	}
}

But maybe I'm assuming incorrectly about how your code works outside of this function (for example how the AvoidFlockMember function works)

Share this post


Link to post
Share on other sites
29 minutes ago, PSvils said:

float Distance = GetDistanceOf(HiveMind.transform.getChild(TempInt),HiveMind.transform.getChild(SubCount));

This only checks the member after the other and only in the array or list.

The boids needs to compare it self with all the other boids near it, not just one member.

31 minutes ago, PSvils said:

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

This looks promising because you move two at once, but how would you prevent the original loop affecting the ones that already calculated there avoid.

If I used something like this I could half my loops.

 

 

For those who wants to know how it all works:

Spoiler

 

Here is a example of my code back when I was still prototyping it. Here I was using rule sets and combining them to find the effect I liked.


	//Avoid others
	Vector3 RuleTwo(GameObject[] InZombieHord, GameObject InZombieBoid){
		Vector3 Avoid = new Vector3 (0f, 0f, 0f);
		foreach (GameObject Zombie in InZombieHord) {
			Vector3 Diffirence = Zombie.transform.position -InZombieBoid.transform.position;
			if (Diffirence.magnitude != 0 && Diffirence.magnitude < ViewDistance) {
				Avoid -= Diffirence;
				Avoid = Avoid * Time.deltaTime;
			}
		}
		return Avoid;
	}

So this made the boid check all other boids and then if they where in view distance it would move away from them.  This is how it was used:


	void UpdateAllBoids(GameObject[] InZombieHord){

		foreach (GameObject Zombie in InZombieHord) {
			Vector3 NewPosition = new Vector3 (0f, 0f, 0f);
			NewPosition += RuleOne (InZombieHord, Zombie); //This has a loop inside
			NewPosition += RuleTwo (InZombieHord, Zombie); //So does this
			NewPosition += ThreeTwo (InZombieHord, Zombie); //etc.
			NewPosition += FourTwo (InZombieHord, Zombie);
          
			Zombie.transform.position += NewPosition;

			WrapAround (Zombie);
		}
	}

 

My new code still follows this but the rules have all been worked into one:

[I decided to remove the main rule it is to bloated for the forum.]


foreach (GameObject Zombie in InPack) {
  TheFourZombieRules(Zombie); //This has a single loop inside that does all 4 rules I want, it's also a void now.
  }

The whole point of this loop is so that the new rules is done once for every zombie to compare it'self to the others.

A rule like this is also done by the pack leader but it moves to a goal instead of the perceived average.

MoreInDepth.jpg.8157a3533563a9c903a9a54da4b5f3e6.jpg

This sketch shows a bit in more depth how it works.

First pass all pack leaders are compared with all pack leaders, this is done using Broad Phase, so most of the time even if there is a 1000 pack leaders I get around 96 loops per update cycle (10-15 min) for the pack leaders.

In the second pass the zombie pack is calculated and if the zombie pack leaders are in the same zone they share there lists of zombies.

If the total zombies in a pack or combined pack is more than 24 a relative Broad Phase is used instead of just brute force loops. Leaders are also added to the Broad Phase loops because with so many zombies in such a small place they often try to overlap.

When off screen only the Pack leaders update and only there positions.

 

My math is also as optimal as I can get it, for example instead of calculating the perceived avrrage, the leader is the average position. So PerceivedAvrrage = Leader.transform.position - ( self.transform.position / PackList.length);

 

I am still looking for ways to improve this because it still consumes a lot of resources just to move the packs around.

I did reach my goal of a millions zombies so it is in working condition.

Share this post


Link to post
Share on other sites

I'm simply talking about optimizing array comparison between elements, outside of any context. Think about it, if you have an array with length N, you only need to do !N comparisons, instead of N^N.

[1, 2, 3]

You have 2 loops, the first goes through each element, and an inner loop, which will compare this element with the other ones. If you start the inner loop at index 0 every time (as you are currently doing), you are comparing every single element twice instead of once. By visiting the first element in the outer loop, you will have compared that element to all other elements, which means when visiting the second element, the inner loop only needs to start with the third element, because comparing elements 1 and 2 already happened when visiting the first element.

I just thought I should explain this because either you're not understanding it, or I don't understand the current code / logic you have happening. The example function I wrote WILL visit and compare all elements, except only once instead of many times. :)

Share this post


Link to post
Share on other sites
Posted (edited)
On 1/5/2018 at 12:47 AM, PSvils said:

I just thought I should explain this because either you're not understanding it, or I don't understand the current code / logic

My thanks, I remember seeing this in one of the Broad Phase explanations but didn't understand it so I skipped it. After you explained it I tried it and it helps a ton.

I just got home and tried it. Really thanks for this, now I have a neat little trick to help boost performance.

Edited by Scouting Ninja

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
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By Manuel Berger
      Hello fellow devs!
      Once again I started working on an 2D adventure game and right now I'm doing the character-movement/animation. I'm not a big math guy and I was happy about my solution, but soon I realized that it's flawed.
      My player has 5 walking-animations, mirrored for the left side: up, upright, right, downright, down. With the atan2 function I get the angle between player and destination. To get an index from 0 to 4, I divide PI by 5 and see how many times it goes into the player-destination angle.

      In Pseudo-Code:
      angle = atan2(destination.x - player.x, destination.y - player.y) //swapped y and x to get mirrored angle around the y axis
      index = (int) (angle / (PI / 5));
      PlayAnimation(index); //0 = up, 1 = up_right, 2 = right, 3 = down_right, 4 = down

      Besides the fact that when angle is equal to PI it produces an index of 5, this works like a charm. Or at least I thought so at first. When I tested it, I realized that the up and down animation is playing more often than the others, which is pretty logical, since they have double the angle.

      What I'm trying to achieve is something like this, but with equal angles, so that up and down has the same range as all other directions.

      I can't get my head around it. Any suggestions? Is the whole approach doomed?

      Thank you in advance for any input!
       
    • By Alexander Nazarov
      Hello. I'm newby in Unity and just start learning basics of this engine. I want to create a game like StackJump (links are below). And now I wondering what features do I have to use to create such my game. Should I use Physics engine or I can move objects changing transform manually in Update().
      If I should use Physics can you in several words direct me how can I implement and what I have to use. Just general info, no need for detailed description of developing process.
      Game in PlayMarket
      Video of the game
    • By Dave Haylett
      Hi all. My project is coming along wonderfully, and am starting to consider alpha deployment, and would like your advice.
      My project need access to 10,000 small PNG image files at runtime, each is only a few kilobytes each, which during development I used to load in directly from a fixed path on my HDD whenever one was needed (obviously not a solution for go-live), using something like this:
      img = new WriteableBitmap(new BitmapImage(new Uri(@screenshotsPath + filename)));
      The image would then be blitted onto a buffer screen, etc. etc. At a time, a few dozen would be being used.
      Now I'm thinking about deployment, and also when I produce an update to my app, there could be more images to add to the folders. So I'm considering the best way of a) deploying the images to the user as part of the project, and b) how to most easily handle updates to the app, whereby more images will be added.
      I have just experimented with adding them all as a Resource (!). This inflated the exe from 10mb to 100mb (not a major problem), increased the compile time from 3 secs to 30 secs (annoying), increased RAM usage from 500mb to 1.5gb (not a major problem either), but means that it solves my fixed directory issue, distribution issue, and update issue, simply by having the files all stuck into the executable. Here's the new code I'm using:
      img = BitmapFactory.FromResource("Shots/" + filename);
      The next thing I was going to try was to mark them as Content > Copy if Newer. This would resolve the executable size and RAM usage (and also the directory issue as well), however it seems that I'd need to highlight them all, and move them from Resource to Content. As an up-front job this isn't too bad, but as I add new images to the project, I'll need to go in and do this every time, which gets annoying, as the VS2015 default is Resource. Also, I'm not sure how this would work in terms of updates. Would something like ClickOnce deployment recognise new PNGs and install them to the users?
       
      I also have 3,000 ZIP files (~500kb each) which also need deploying and updating in the same way. These are currently read directly from my HDD until I can find a permanent solution for adding these to the project as well.
      Can anyone thing of a better way of doing what I'm trying to achieve?
      Thanks for any help folks.
       
    • By Felis Nigripes
      I'm doing a test quest.
      The player gets a quest from an NPC to bring him fish.

      Once the player picks up the fish, the original NPC gets replaced by a new one with a new conversation trigger. The NPC tells the Player "Well done" and should give 200xp.

      The script tells the xp counter to go up by making a reference to the gameobject that holds the text component
       
      But it throws this error:
       

       
      I'm aware that the error may hide in plain sight. I just have to sort this out, since I'm writing the AI at the same time, and the time it takes to resolve everyone of these errors is tremendous.
      Plus, I think I'll learn something. I've been having trouble with some basic functionalities recently. There might be something wrong with my understanding on how programming works.
       
      Glad if someone could help (:
       
       
       
      Edit: I'm fully aware that the update function requires an input. I call the function in the editor when the dialogue ends, it still doesn't work.
       
    • By Vu Chi Thien
      Hi fellow game devs,
      With the help of  @CombatWombat in my previous post about clutch modeling, I now have a solid direction for the modeling the clutch. The way I'm doing it is having 2 clutch states: locked and unlocked. EngineRPM and torque will be calculated separately in each state. My problem right now is the logic and code for specifying locking and unlocking.
      The condition for locking is when (engineSpeed - drivetrainSpeed) in previous update cross zero (different sign) with the current update (to determine if engineSpeed = drivetrainSpeed or not in-between updates) and engineTorque <= clutchTorque.
      The condition for unlocking is when engineTorque > clutchTorque.
      The diagram looks roughly like this (taken from matlab website with the similar implementation):

       
      However, the 2 conditions are triggers for switching states, not for determine the current state to be in, so in the end my clutch state just jumped around. I don't have a lot of experience in doing state machine, so can some one give me rough code of how to implement this? Below is my rough code:
      speedError = engineSpeed - drivetrainSpeed; if ((Math.Sign(speedError) != Math.Sign(deltaW) && currentTotalEngineTorque <= clutchReactTorque)) { clutchLocked = true; } else clutchLocked = false; deltaW = speedError; //end of update I think the main struggle is the cross zero. Because cross zero is the "trigger condition" to check if the clutch should lock when it is slipping, not the condition for continuous locking, while the code I have above is the "continuous condition" saying "this condition is true then it is locked/unlocked". Another word, if the clutch is slipping, the condition above would decide if it's locked or not, but once it is locked, the cross zero condition is not true anymore (since speedError and deltaW have same sign as engineSpeed == drivetrainSpeed when clutch is locked). I'm sorry that I cannot explain this better as English is not my first language.
  • Advertisement