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

  • Popular Now

  • Advertisement
  • Similar Content

    • By bojanzarnoski@gmx.de
      Hello,
      I want to get into coding again by programming a 2D platformer to get started, but i don't know if i should use Java or C# with the unity engine.
      I am pretty fit with Java, but with c# i have to start from scratch. What do you recommend and why?
    • By SickTwistGames
      Ok, firstly, Hi.
       
      This is my first post on this forum. I am an Indie Dev making my first game so bear with me when I say dumb stuff, I'm on a huge learning curve.
       
      My first question is about inventory systems for unity. I am trying to make a survival type game with crafting. I have purchased Inventory manager pro by devdog from the unity asset store and it seems like a pretty powerful assett but for an intermediate coder its a little tough to use.  I'm beginning to wonder if it was the right purchase.
      So my question is.... does anyone have any experience of inventory plugins / systems for unity and can anyone reccomend a system to me?
      It needs to have the following: Loot system, crafting system, character sheet, blueprint system,  character stats system. Ideally with as little coding as possible.
       
      Thanks
    • By ethancodes
      I've got a bug with my brick breaker style game. The bricks move down one line at a time ever 1.5 seconds. What appears to be happening is occasionally the ball will be just about to hit the brick when the brick moves down a line, and now the ball is behind it. I'm not sure how to fix this. I have two ideas but I'm not sure of implementation. 1 solution would be to check where they were and where they are going to be before rendering the frame. Then if they crossed paths, then register the brick as hit. Solution 2 would be change how the bricks move. I could maybe slide them down line by line, instead of a jump down. I'm not sure of this will fix the issue or not. Any ideas?
    • By Scouting Ninja
      Once again Unity is frustrating me to the point of insanity.
      What I am looking for is a way to find a ray intersect with the edges of the mesh, using Unity's already made collision system. I want to point out that I know how to do a line intersect, what I want to know is if Unity supports this already.

      The image above shows how I sweep a ray,intersecting the mesh. The top green image shows what I want and the red shows what Unity is giving me.
      I want to know if there is some way, to find the edges in Unity without creating a custom line intersection tool.
      Most engines I know don't use rays for this but instead use a plane like this:

      I checked the Unity "Plane intersection" but it is just a ray cast. It will still need me to find the vertices on the collision mesh to cast the ray from; if I am doing that then making my own line intersection tool is better.
       
      I looked online and can find anything on this. Also I don't want to cut the mesh, so I don't need a way to know what side is what.
      Does Unity even have collisions that support edge only detection?
    • By JuliaAxt
      Please help me with this code, this error is currently stopping my project 
      using System.Collections;
      using System.Collections.Generic;
      using UnityEngine;
      [RequireComponent(typeof(Rigidbody2D))]
      public class TapController : MonoBehaviour {
          public float tapForence = 10;
          public float tiltSmooth = 5;
          public Vector3 startPos;
          Rigidbody2D Rigidbody;
          Quaternion downRotation;
          Quaternion forwardRotation;
          private void Start() {
              Rigidbody = GetComponent<Rigidbody2D>();
              downRotation = Quaternion.Euler(0, 0, -90);
              forwardRotation = Quaternion.Euler(0, 0, 35);
        
          }
          private void Update() {
              if (Input.GetMouseButtonDown(0))
              {
                  transform.rotation = forwardRotation;
                  Rigidbody.AddForce(Vector2.up * tapForce, ForceMode2D.Force);   (The name `tapForce`does not exist in current context)
              }
              transform.rotation = Quaternion.Lerp(transform.rotation, downRotation, tiltSmooth * Time.deltaTime);
          }
      }
          void OnTriggerEnter2D(Collider2D col){
          if (col.gameObject.tag == "scoreZone")
          {
              // register a score event
              // play a sound
          }
          if (col.gameObject.tag == "deadZone")
          {
              Rigidbody.simulated = false;   (`Rigidbody` does not contain a definition for `simulated´) 
              //register a dead event
              //play a sound
          }
           }

      }
       
  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!