Monday, 22 December 2008

Flocking Boids C#

Note: The code supporting this post can be found on GitHub.

In this post, I shall demonstrate an example of swarm intelligence, which is based on the Boids model. In my ecosystem, two different types of Boids exist, namely Regular Boids and Zombie Boids. The Regular Boids are very social, fast moving creatures, which like to flock together. The Zombie Boids are solitary soles, whose single reason for living is to chase after Regular Boids, albeit very slowly.

There is no real problem I am trying to solve here, other than to enjoy watching the carnage that emerges! It would be very easy to add nicer graphics, or even turn this simulation into a screen saver. As usual, the full C# source code to generate this application is listed below.

Before I go into detail about the code, some background on Boids. In 1986, Craig Reynolds developed a computer model that simulated animal movement, such as flocks of birds and schools of fish. He called the simulated flocking creatures Boids.

As with most artificial life simulations, Boids is an example of emergent behaviour. The complexity of Boids arises from the interaction of individual agents complying with a simple set of rules. Reynolds basic flocking model consisted of three simple steering behaviours that determined how individual Boids should manoeuvre based on their velocity and position within the flock:

Separation: steer to avoid crowding local flock-mates
Cohesion: steer to move toward the average position of local flock-mates
Alignment: steer towards the average heading of local flock-mates

To provide even more life like effects, further rules could be added, such as obstacle avoidance and goal seeking.

The flocking algorithm requires that each Boid only react to flock-mates within its local neighbourhood. This neighbourhood is defined by the Boid’s field of view relative to the rest of the flock. Flock-mates outside of this neighbourhood are ignored.

The video below shows an example of the behaviour you can expect to emerge.


To implement Boids, I have used three classes, which are EcoSystem, Swarm and Boid. The EcoSystem class contains the entry point of the application, handles the graphics and serves as a container for the swarm. The Swarm class is responsible for creating and managing the entire the collection of Boids, known as the swarm. The Boid class encapsulates all logic pertaining to Boid behaviours, which, in this simulation, include separation, cohesion, alignment, avoidance and hunting.

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Drawing;
  4. using System.Drawing.Drawing2D;
  5. using System.Windows.Forms;
  6.  
  7. public class Boids : Form
  8. {
  9.     private Timer timer;
  10.     private Swarm swarm;
  11.     private Image iconRegular;
  12.     private Image iconZombie;
  13.  
  14.     [STAThread]
  15.     private static void Main()
  16.     {
  17.         Application.Run(new Boids());
  18.     }
  19.  
  20.     public Boids()
  21.     {
  22.         int boundary = 640;
  23.         SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.DoubleBuffer, true);
  24.         FormBorderStyle = FormBorderStyle.FixedToolWindow;
  25.         StartPosition = FormStartPosition.CenterScreen;
  26.         ClientSize = new Size(boundary, boundary);
  27.         iconRegular = CreateIcon(Brushes.Blue);
  28.         iconZombie = CreateIcon(Brushes.Red);
  29.         swarm = new Swarm(boundary);
  30.         timer = new Timer();
  31.         timer.Tick += new EventHandler(this.timer_Tick);
  32.         timer.Interval = 75;
  33.         timer.Start();
  34.     }
  35.  
  36.     protected override void OnPaint(PaintEventArgs e)
  37.     {
  38.         foreach (Boid boid in swarm.Boids)
  39.         {
  40.             float angle;
  41.             if (boid.dX == 0) angle = 90f;
  42.             else angle = (float)(Math.Atan(boid.dY / boid.dX) * 57.3);
  43.             if (boid.dX < 0f) angle += 180f;
  44.             Matrix matrix = new Matrix();
  45.             matrix.RotateAt(angle, boid.Position);
  46.             e.Graphics.Transform = matrix;
  47.             if (boid.Zombie) e.Graphics.DrawImage(iconZombie, boid.Position);
  48.             else e.Graphics.DrawImage(iconRegular, boid.Position);
  49.         }
  50.     }
  51.  
  52.     private static Image CreateIcon(Brush brush)
  53.     {
  54.         Bitmap icon = new Bitmap(16, 16);
  55.         Graphics g = Graphics.FromImage(icon);
  56.         Point p1 = new Point(0, 16);
  57.         Point p2 = new Point(16, 8);
  58.         Point p3 = new Point(0, 0);
  59.         Point p4 = new Point(5, 8);
  60.         Point[] points = { p1, p2, p3, p4 };
  61.         g.FillPolygon(brush, points);
  62.         return icon;
  63.     }
  64.  
  65.     private void timer_Tick(object sender, EventArgs e)
  66.     {
  67.         swarm.MoveBoids();
  68.         Invalidate();
  69.     }
  70. }
  71.  
  72. public class Swarm
  73. {
  74.     public List<Boid> Boids = new List<Boid>();
  75.  
  76.     public Swarm(int boundary)
  77.     {
  78.         for (int i = 0; i < 15; i++)
  79.         {
  80.             Boids.Add(new Boid((i > 12), boundary));
  81.         }
  82.     }
  83.  
  84.     public void MoveBoids()
  85.     {
  86.         foreach (Boid boid in Boids)
  87.         {
  88.             boid.Move(Boids);
  89.         }
  90.     }
  91. }
  92.  
  93. public class Boid
  94. {
  95.     private static Random rnd = new Random();
  96.     private static float border = 100f;
  97.     private static float sight = 75f;
  98.     private static float space = 30f;
  99.     private static float speed = 12f;
  100.     private float boundary;
  101.     public float dX;
  102.     public float dY;
  103.     public bool Zombie;
  104.     public PointF Position;
  105.  
  106.     public Boid(bool zombie, int boundary)
  107.     {
  108.         Position = new PointF(rnd.Next(boundary), rnd.Next(boundary));
  109.         this.boundary = boundary;
  110.         Zombie = zombie;
  111.     }
  112.  
  113.     public void Move(List<Boid> boids)
  114.     {
  115.         if (!Zombie) Flock(boids);
  116.         else Hunt(boids);
  117.         CheckBounds();
  118.         CheckSpeed();
  119.         Position.X += dX;
  120.         Position.Y += dY;
  121.     }
  122.  
  123.     private void Flock(List<Boid> boids)
  124.     {
  125.         foreach (Boid boid in boids)
  126.         {
  127.             float distance = Distance(Position, boid.Position);
  128.             if (boid != this && !boid.Zombie)
  129.             {
  130.                 if (distance < space)
  131.                 {
  132.                     // Create space.
  133.                     dX += Position.X - boid.Position.X;
  134.                     dY += Position.Y - boid.Position.Y;
  135.                 }
  136.                 else if (distance < sight)
  137.                 {
  138.                     // Flock together.
  139.                     dX += (boid.Position.X - Position.X) * 0.05f;
  140.                     dY += (boid.Position.Y - Position.Y) * 0.05f;
  141.                 }
  142.                 if (distance < sight)
  143.                 {
  144.                     // Align movement.
  145.                     dX += boid.dX * 0.5f;
  146.                     dY += boid.dY * 0.5f;
  147.                 }
  148.             }
  149.             if (boid.Zombie && distance < sight)
  150.             {
  151.                 // Avoid zombies.
  152.                 dX += Position.X - boid.Position.X;
  153.                 dY += Position.Y - boid.Position.Y;
  154.             }
  155.         }
  156.     }
  157.  
  158.     private void Hunt(List<Boid> boids)
  159.     {
  160.         float range = float.MaxValue;
  161.         Boid prey = null;
  162.         foreach (Boid boid in boids)
  163.         {
  164.             if (!boid.Zombie)
  165.             {
  166.                 float distance = Distance(Position, boid.Position);
  167.                 if (distance < sight && distance < range)
  168.                 {
  169.                     range = distance;
  170.                     prey = boid;
  171.                 }
  172.             }
  173.         }
  174.         if (prey != null)
  175.         {
  176.             // Move towards closest prey.
  177.             dX += prey.Position.X - Position.X;
  178.             dY += prey.Position.Y - Position.Y;
  179.         }
  180.     }
  181.  
  182.     private static float Distance(PointF p1, PointF p2)
  183.     {
  184.         double val = Math.Pow(p1.X - p2.X, 2) + Math.Pow(p1.Y - p2.Y, 2);
  185.         return (float)Math.Sqrt(val);
  186.     }
  187.  
  188.     private void CheckBounds()
  189.     {
  190.         float val = boundary - border;
  191.         if (Position.X < border) dX += border - Position.X;
  192.         if (Position.Y < border) dY += border - Position.Y;
  193.         if (Position.X > val) dX += val - Position.X;
  194.         if (Position.Y > val) dY += val - Position.Y;
  195.     }
  196.  
  197.     private void CheckSpeed()
  198.     {
  199.         float s;
  200.         if (!Zombie) s = speed;
  201.         else s = speed / 4f;
  202.         float val = Distance(new PointF(0f, 0f), new PointF(dX, dY));
  203.         if (val > s)
  204.         {
  205.             dX = dX * s / val;
  206.             dY = dY * s / val;
  207.         }
  208.     }
  209. }

I hope you enjoy Boids and much as I do – I find them strangely addictive to watch.

As always, if you have any comments or suggestions, please comment.

Cheers
John