AI Component - Boid Movement

In 1987 a Researcher names Craig Reyonds published a conference paper (Reynolds, 1987) that described the movements of flocks in a set of 3 simple rules. 

  1. The members of a flock tends towards its center
  2. The flock aligns its rotation
  3. The flock tries to not overcrowd its self

These were refereed to in the paper as Cohesion, Alignment and Separation respectively. The goal being to create a realistic looking emergent movement system for birds/fish/cows where each agent, called a boid, makes its own decisions. 

So you are a developer and want to have a flock system in your game! Maybe a realistic group of birds? Fish in a koi pond? DO NOT USE THIS SYSTEM. You can get 90% of the way there with a single actor containing multiple meshes. It will be easier to test as the movement is not emergent and you will be spending much less in terms of performance.  

Use Reyonds system if - 

  • you have multiple flocks that you want to interact with each other
  • you want parts of the flock to react to something and then unaware members of the flock to react to the reaction
  • you want to decentralize the spawning of flock members

Here is how we implemented it and the levers we gave the level/game designers to use.  

We started with a few principles, we wanted the performance to be scale-able, we also wanted to ensure that everything was as event driven as possible.
Querying currently overlapping actors is an alluring siren when doing work like this but that route leads you to performance issues. 
We also wanted the majority of the attributes to be editable at runtime.

Behavior Tree

Tree.png

Each of the boids runs this tree.

Of these the most expensive is easily the find FindNeighbours node. For lower performance devices or situations where the flock is going to get particularly big we can add a cooldown to the root node to decrease the tick rate.

FindNeighbours - Queries the list of currently relevant Boid and gets average rotation and location to be used in future nodes.

CollisionAvoidance - uses an Ahead method, where we see if there is a object coming up that, if we keep out current course we will overlap with. If there is it checks to the left and right of the Boid to see if there is anything stopping it from turning.

Cohesion And Separation  - Using the central location of the current Boids the boid is aware of the rotation is altered to either angle the movement towards the center, or if the Boid is suffocating, away from the center.

Alignment of Rotation - This simply sets the rotation to the average rotation of the other Boids in the area.

Alignment - This node simply updates the Actor with the calculated rotation 

Design Levers

Levers For Use.png

Most of these are self explanatory, speed & rotation speed are the easiest. Speed variance, when enabled, gives the actor a random speed in the range of the set speed. Noise introduces an intermittent wobble to the movement of the actor. Suffocation decided how many other actors the Boid can be near before it starts to move away from the center of the group. 

Hard turn rotation is the rotation speed that is used when turning to avoid collision. This should be increased if the level is particularly angular. 

 The the Rotation Detection Distance is used to decide the area a given Boid uses to find the other Boids it aligns its rotation to. The Separation Detection Distance is used for the decision making when deciding on the center point to move towards. 

The reason these are separate collisions is there is swarms that will want to stay together but not necessarily point in the same direction, think cows eating grass in a field. Other swarms will care about pointing in the same direction, but not being all that near each other, think a fleet moving through space. 

Floating.gif

This system gets a bit weird once you have areas with sharp corners or start thinking in 3D space but is a great place to start. 


Reynolds, C. W. (1987, August). Flocks, herds and schools: A distributed behavioral model. In ACM SIGGRAPH computer graphics (Vol. 21, No. 4, pp. 25-34). ACM.