Meet The Flockers.

Well, it should be more like meet the Swarmers, but you can't have as much fun with the word Swarm as you can with the word Flock. My first port of call was to do some quick research, not a good idea on a Sunday morning after a "busy" Saturday night, lets just say even plain English was reading like Egyptian Hieroglyphics ...

I found a large variety of examples on the Net, but nothing in a programming language I use or with Sunday morning syndrome could be bothered to wade through. Most, and probably all the examples I came across, were 2D, and not what I wanted. I opted for the same route I took when writing my Lua A* Scripts, just to work from a simple written definition of the rules and how they are used. With A* I used:

1) Add the starting square (or node) to the open list.
2) Repeat the following:
a) Look for the lowest F cost square on the open list. We refer to this as the current square.
b) Switch it to the closed list.
c) For each of the 8 squares adjacent to this current square …
If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
d) Stop when you:
Add the target square to the closed list, in which case the path has been found (see note below), or
Fail to find the target square, and the open list is empty. In this case, there is no path.
3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
 
And from the written description I then coded the AStar Script. I felt using this approach again would enhance the learning potential. For this new exercise I used the descriptions of the three rules Craig Reynolds uses to take this approach.


Cohesion: steer to move toward the average position of local flockmates

Alignment: steer towards the average heading of local flockmates

Separation: steer to avoid crowding local flockmates


From Conrad Parkers website :


Boids try to fly towards the centre of mass of neighbouring boids.

Boids try to keep a small distance away from other objects (including other boids).

Boids try to match velocity with near boids.

It was also my interpretation that the rules when performed on an individual boid had a limiting radial area when looking for its neighbours, which if I correctly understood was the factor that changed the overall behaviour. I took this to be the case given the graphic representations on Craigs boids page:

So my rules ended up as:


Boids try to fly towards the average position of local flockmates in a given radial volume of 3D space


Boids try to keep a small distance away from other local flockmates in a given radial volume of 3D space


Boids try to match velocity with other local flockmates in a given radial volume of 3D space

Actually I also implemented a 4th rule, which is a mathematically described harsh confinement volume, by harsh I mean zero tolerance, which currently means the boids "bounce" off an imaginary wall belonging to the volume in the same way the ball bounces in the game breakout. However when time permits I will redefine the confinement parameters to coax the boids into staying within the confinement volume as opposed to bluntly preventing them leaving the defined area. Of course, when a boid ricochets of the imaginary wall this repositioning should have a knock on effect through its neighbours and in turn their neighbours and so forth, well that was my thinking.

So 3D vector math was the first thing on the new to do list, I made a new math class to allow all the calculations to be done by a boid type, I decided to simply store all generated boids in a TList, which then could be looped through to adjust the vectors of each one. These I called my Non-corporeal boids, simple mathematical ghosts, without shape or form. Using an Entity array the physical form was generated as a copy of a mesh, in this case a cube. Thus in the draw cycle the Non-corporeal boids have their respective vectors updated based on the stipulated rules and a corresponding pre created body is then assigned to its co-ordinates.

 
Currently this is just an exercise I am using to find out more about this field of AI. It has practical game applications, one could be "wildlife" volumes, like birds in the sky over a scene. But as with all things the first part is to find out how and why it "ticks" and to try and get it working.

This is a slow motion video capture of how the rules effect the behaviour:




Demo Application Can Be Found Here

References:
http://www.red3d.com/cwr/boids/
http://www.kfish.org/boids/

Posted in: Leadwerks Engine 2