Boids/ Simple Flocking

Hi, lately I ran into a new topic I wasn't familar with, it's called boids, basically I assume it's a simple method AI for group of random motion behavior.

it includes: Cohesion(where they attract eachother), Alignment(Adjustment of each invidual velocity according to rest of the flock's velocity) and Seperation The avoidance of any direct collusion with other boids.

Basically I am trying to simulate an under sea enviorment where fishes behave in groups using this method.

Does anybody have pointers or site on how the method works in technical details with Unity scripting?

Thanks!

 

The first place to look may be UnitySteer.

http://www.arges-systems.com/articles/35/unitysteer-steering-components-for-unity

This is an implementation of OpenSteer which builds on Craig Reynold's steering behaviours.

 

I find flocking to be rather interesting. I'm experimenting with it myself. Here's something I literally threw together on the train this evening (netbook ftw!). It doesn't have alignment yet, and it currently sums together the forces, rather than trying to modify the velocity to the desired velocity (that's the next phase of development). It already has some interesting boids-like behaviour but it's still pretty raw; without alignment I'd describe it more as "swarming"; it's much more chaotic than flocking.

My little netbook has a rather puny processor, so this code is written so that I can tweak the update rate in the Editor and spread the processing load as evenly as possible so it isn't choking on massive updates. If anyone knows any good ways of lightening or spreading the load better, then I'd be glad to hear them!

Tweak sightRadius, separationPriority, and cohesionPriority for different results. You can probably handle a higher value for flockUpdatesPerSecond than I can, but I'm considering making that dynamically adjust itself based on timing the refresh rate.

Code (csharp):

1.  
2. /////////////////////////////////
3. // Flock.js                    //
4. /////////////////////////////////
5.  
6.  
7. // Requires
8. @script RequireComponent(Rigidbody)
9.  
10. // Public variables
11. // Roughly how long between updates
12. var flockUpdatesPerSecond : float = 5;
13. var spread : float = 5;
14. // How far do the Flockers look for their kin?
15. var sightRadius : float = 10;
16.  
17. var maxAcceleration : float = 5;
18.  
19. private var steerToCentre : Vector3 = Vector3.zero;
20. private var steerToSeparate : Vector3 = Vector3.zero;
21.  
22. private var neighbourhood : Collider[];
23.  
24. var cohesionPriority : float = 5.0;
25. var separationPriority : float = 5.0;
26. var id : int;
27.  
28. // Init
29. function Awake() {
30.  
31.     id = Random.Range(0, 1000);
32.  
33. }
34.  
35. // Set off the coroutine
36. function Start() {
37.  
38.     DoFlock();
39.  
40. }
41.  
42. // Coroutine
43. function DoFlock() {
44.  
45.     while (true) {
46.    
47.         neighbourhood = Physics.OverlapSphere( transform.position, sightRadius );
48.        
49.         // Wait. We've already used a lot of processing power this update.
50.         yield WaitForSeconds(SpreadUpdates());
51.        
52.         DoSeparationAndCohesion();
53.        
54.         // We're done with flocking for this update! Come back next update!
55.         yield WaitForSeconds(SpreadUpdates());
56.    
57.     } // end while (true)
58.  
59. } // End function DoFlock()
60.  
61. function SpreadUpdates() {
62.  
63.     // We're going to take targetTime and return a number binomially distributed about it.
64.     var offset = ( Random.value - Random.value ) / spread;
65.     return  ( 1 / flockUpdatesPerSecond ) + offset;
66.    
67. }
68.  
69. function DoSeparationAndCohesion() {
70.    
71.     var flockDirection : Vector3 = Vector3.zero;
72.     var closestFlockerDirection : Vector3 = Vector3.zero;
73.     var flockCentre : Vector3 = Vector3.zero;
74.    
75.     var shortestDistance : float = Mathf.Infinity;
76.     var closestLocation : Vector3;
77.    
78.     for ( var otherFlocker in neighbourhood ) {
79.        
80.    
81.         if (otherFlocker.rigidbody  otherFlocker.GetComponent(Flock).id != id) {
82.        
83.             flockDirection += otherFlocker.transform.forward;
84.             flockCentre += otherFlocker.transform.position;
85.             var testDist = Vector3.Distance( transform.position, otherFlocker.transform.position );
86.             if (testDist < shortestDistance ) {
87.            
88.                 shortestDistance = testDist;
89.                 closestLocation = otherFlocker.transform.position;
90.            
91.             }
92.         }
93.     }  
94.    
95.     flockDirection /= neighbourhood.length - 1;
96.    
97.     flockCentre /= neighbourhood.length - 1;
98.    
99.     if (shortestDistance != Mathf.Infinity) {
100.         // Get a steering force away from the closest otherFlocker
101.         steerToSeparate = transform.position - closestLocation;
102.     }
103.     else {
104.         steerToSeparate = Vector3.zero;
105.     }
106.    
107.     // Steer towards flockCentre
108.     steerToCentre = Vector3.Normalize(flockCentre - transform.position) * maxAcceleration;
109.     steerToSeparate = Vector3.Normalize(steerToSeparate) * maxAcceleration;
110.    
111. }
112.  
113. function FixedUpdate() {
114.  
115.     var accelToAdd : Vector3 = steerToCentre * cohesionPriority + steerToSeparate * separationPriority;
116.     accelToAdd = Vector3.Normalize(accelToAdd) * maxAcceleration;
117.  
118.     rigidbody.AddForce(accelToAdd, ForceMode.Acceleration);
119.  
120. }

Sorry for The Post That Ate New York.

 

@TMJ - This interests me as the other flocking scripts I've tried are huge cpu hogs, drops my frame rates down 50%. I tried your script but there's an error in line 75:

Code (csharp):

1.       if (otherFlocker.rigidbody  otherFlocker.GetComponent(Flock).id != id) {
2.  

which is looking for a component named Flock but one doesn't exist.

I'd love to get this working and boid orientation would be excellent.

 

Sorry, I should probably have said that that entire script is Flock.js, attached as a component to a GameObject with a Rigidbody.

So far that script just applies dumb forces for separation and cohesion. Phase II will be treating the net vector (currently used as the AddForce vector) as a desired velocity and calculating the acceleration needed to achieve it.

Phase III: I'm going to add some code to make the flocker "look where it's going" so that it faces in the direction of its velocity, and then for Phase IV I plan to add code to calculate and turn towards the local average heading.

When I have some progress I'll post it back here, and I'd enjoy seeing what you come up with too.

As far as CPU load lightening goes, I broke DoFlock up into two stages, one which uses the Physics system to find nearby flockers (Physics.Overlap()), and one which does the rest. I have a deep mistrust of collision detection algorithms' efficiency (especially when they check against the whole world) so I try to avoid doing them whenever possible. I also broke the entire thing out of Update() into a coroutine because I don't want to do collision detection 50+ times per second! I will have to tighten up the discrimination in "neighbourhood", because I want to include non-flockers in the world and I'm going to need to have some way of making sure that they only flock with other flockers, not with... say... trees

Despite this it would still choke the processor every update, so I gave a small random variance on the yield WaitForSeconds(). I made it binomial (Random.value - Random.value) because I wanted the update delays to be clustered fairly tightly around the same value but they should all gradually drift out of sync and spread the load after a few seconds. The binomial bit is probably either redundant, overkill, or useless, but it seemed like a good idea at the time.

If you have any questions I'm happy to answer them. I'm not presenting that code as the ultimate solution, I'm just offering something I worked on for an hour that works to a certain standard, that I believe I can make into something decent with time.

 

@DMJ - I tried that and can't seem to get it to work. Can you post a package or project folder? It's interesting that you seem to be using physics for the boid movements, I don't think I've seen that before.

 

I didn't know other people didn't tend to use physics for this. How interesting. Maybe I'm going about it the wrong way?

Anyway, here's my package. It contains a simple test scene, complete with a flocker spawner which will gradually fill the bounding area with flocking (well, swarming at the moment - flocking soon!) cubes.

There's no fancy camera code, so I'm afraid you'll have to watch it in Scene view.

The behaviour looks nicely chaotic, but I'm looking forward to making it flock properly. A further refinement to the flocking behaviour (once I've made this work properly) will be to restrict the flockers' vision to a tweakable cone instead of a sphere and see what effects that will have.

EDIT: Okay, it looks like the test scene didn't make it. Just put a FlockerSpawner into the scene and it'll add new flockers every three seconds (tweakable value). If you want to keep the flockers from flying off into the distance put a "Boundaries" in the scene, and set boxSize to the size of the box you want. Otherwise when a flocker loses sight of all the others it will drift on forever. Alone. Doomed. Boundaries not only makes the enclosed volume wrap, but it also counts as a permanently-in-range rigidbody which means that each flocker always has a force pulling it back in towards the centre if it flies out from the mass.

I guess adding a maximum velocity would be nice, perhaps adding some drag to the prefab's Rigidbody would be a start.

Another edit: Drag doesn't seem to be a good idea. I added a touch of drag and they all spiralled in towards the centre of the swarm. Not exactly desired behaviour!

 

Got it working, thanks. Your script is very interesting. Most of the flocking scripts I've seen create a fixed number of boids to start and then move them around following or avoiding within a boundary. Yours, on the other hand, adds a new boid every x seconds, and as they reach the edge of the boundary, it immediately is moved back towards the inside of the bounding box. I haven't seen a flocking script behave that way before, but as you say, it definitely looks more like a swarming bee hive than a flock of birds or school of fish.

Keep working on it, I'll be interested in seeing how this progresses.

 

Hi

How did you get around the following assertion:

Assets/Scripts/Flock.js(77,80): BCE0019: "id" is not a member of 'UnityEngine.Component.'

Assets/Scripts/KeepWithinBounds.js (23,61): BCE0019: "id" is not a member of 'UnityEngine.Component'.

 

Update: New attachment removed, I'm still working on this.

 

Sympa,

I like how simple and fast the script is.

I have questions:

Can you explain why the the binomial distribution of update time slice impacts how spread out the boids are?
(or maybe spread is a name for time spread)

 

I just got it, this spread randomize the tick incrementation so that boids spawned at the same time eat up the cpu at different time.

 

There's also something on the Wiki that I've used in a project, and it worked fine:

http://www.unifycommunity.com/wiki/index.php?title=Flocking

 

Nice behavior, I sliced in my own solution because I needed something modular.
By the way, did you see this awesome shepherd dog pathing ?

http://www.youtube.com/watch?v=Mu6XPdxmsnI