Boids in C#, XNA

This post will discuss an implementation of the Boids algorithm, originally developed by Craig Reynolds in 1986. Its’ purpose is to mimic the flocking behaviour of a swarm of birds and as we can see when running this sample, it does a pretty good job at that.

The algorithm is based on three rather simple rules:

  • Separation – Avoiding collisions within the flock
  • Alignment – Keeping a somewhat common direction
  • Cohesion – Staying together

We’ll create a world inhabiting two types of birds, the first type being the flocking birds, let’s call them sparrows, the other type will be hunting the flock, we’ll call them ravens. Both will derive from a common abstract class named Bird. This class will contain some fields and properties common to both types of birds, as well as a base constructor and methods to update, handle edge detection and an averaging method to support the alignment and cohesion parts of the algorithm, NormalizeOffset(), which will be discussed shortly.

The Bird class should look like this:

    public abstract class Bird
    {
        protected static Random rand = new Random();
        protected static Vector2 border = new Vector2(100f, 100f);
        protected static float sight = 75f;
        protected static float separation = 30f;
        protected float speed;
        protected Vector2 boundary;
              
        protected Flock flock;
        protected Texture2D texture;

        protected Vector2 position;
        public Vector2 Position
        {
            get { return position; }
        }

        protected Vector2 offSet;
        public Vector2 Offset
        {
            get { return offSet; }
        }

        public Bird(Vector2 boundary, Texture2D texture)
        {
            position = new Vector2(rand.Next((int)boundary.X), rand.Next((int)boundary.Y));
            this.boundary = boundary;
            this.texture = texture;
         }

        public virtual void Update()
        {
            HandleEdgeCollision();
            NormalizeOffset();
            position += offSet;
        }

        private void HandleEdgeCollision()
        {
            //Left and top
            if (position.X < border.X)
            {
                offSet.X += border.X - position.X;
            }

            if (position.Y < border.Y)
            {
                offSet.Y += border.Y - position.Y;
            }

            //Right and bottom
            Vector2 farEnd = boundary - border;
            
            if (position.X > farEnd.X)
            {
                offSet.X += farEnd.X - position.X;
            }

            if (position.Y > farEnd.Y)
            {
                offSet.Y += farEnd.Y - position.Y;
            }
        }

        protected void NormalizeOffset()
        {
            float offSetLength = offSet.Length();
         
            if (offSetLength > speed)
            {
                offSet = offSet * speed / offSetLength;
            }
        }

        public abstract void Draw(SpriteBatch spriteBatch);
    }

Make sure to add the necessary references to the project and the according usings to the class; we need both Microsoft.Xna.Framework and Microsoft.Xna.Framework.Graphics.

The first class deriving from the abstract Bird class will be the Sparrow class which will implement the flocking behaviour. It will override the base Update() method and implement the abstract Draw() method. The Update() method will call a private method named Flock(), which implements the flocking rules described earlier:

    class Sparrow : Bird
    {
        public Sparrow(Vector2 boundary, Flock flock, Texture2D texture)
            : base(boundary, texture)
        {
            this.flock = flock;
            speed = 10f;
        }

        public override void Update()
        {
            Flock();

            base.Update();
        }

        private void Flock()
        {
            foreach (Bird bird in flock.Birds.Where(b => b is Sparrow && b != this))
            {
                float distance = Vector2.Distance(position, bird.Position);

                if (distance < separation)
                {
                    offSet += position - bird.Position;
                }
                else if (distance < sight)
                {
                    offSet += (bird.Position - position) * 0.025f;
                }

                if (distance < sight)
                {
                    offSet += bird.Offset * 0.5f;
                }
            }

            foreach (Bird raven in flock.Birds.Where(b => b is Raven && b != this))
            {
                float distanceRaven = Vector2.Distance(position, raven.Position);
                if (distanceRaven < sight) // Flee
                {
                    offSet += (position - raven.Position) * 1.5f;
                }
            }       
        }

        public override void Draw(SpriteBatch spriteBatch)
        {
            spriteBatch.Draw(texture, position, Color.White);
        }
    }

Now, the Flock() method will calculate an offset to satisfy the rules for separation, cohesion and alignment with respect to each flocking member withing the “visual” range, which is set by the Bird’s class protected sight field. Then it scans for any raven in sight and if present, will steer away from it, completing the Flock() method. And this is where the Bird class’s NormalizeOffset() comes in, as it calculates the added offset vectors average according to the current speed.

Next we’ll implement the Raven class. The raven’s task is to scare the sparrows and as such disturbing the flock. Its’ implementation is about the same as the sparrows’, apart from its’ Hunt() method, to have it hunting instead of flocking. The hunting algorithm is a rather crude “algorithm” using Linq to find the nearest sparrow: first we find the sparrows in sight, then we order by distance, then we select the nearest.

The Raven class should look like this:

    class Raven : Bird
    {
        public Raven(Vector2 boundary, Flock flock, Texture2D texture)
            : base(boundary, texture)
        {
            this.flock = flock;
            speed = 6f;
        }

        public override void Update()
        {
            Hunt();

            base.Update();
        }

        private void Hunt()
        {
            var l = flock.Birds.Where(b => b is Sparrow && Vector2.Distance(position, b.Position) < sight);
            var m = l.OrderBy(b => Vector2.Distance(position, b.Position));
            var n = m.FirstOrDefault();
            Bird p = ((Bird)n);

            // and move towards to attack...
            if (p != null)
                offSet += p.Position - position;
        }

        public override void Draw(SpriteBatch spriteBatch)
        {
            spriteBatch.Draw(texture, position, Color.Brown);
        }

    }

The rest of the code is trivial: we’ll create a Flock class managing all our feathered friends, both the sparrows and the ravens. Although, ornithology-wise this will probably not be entirely correct, code-wise it renders a coherent approach. The class contains a list of Bird objects, a constructor creating the specified amount of each type of birds and an Update() and Draw() method to handle the respective behaviours and the drawing:

    public class Flock
    {
        public List<Bird> Birds = new List<Bird>();

        public Flock(Vector2 boundary, int nofSparrows, int nofRavens, Texture2D texture)
        {
            for (int i = 0; i < nofSparrows; i++)
            {
                Birds.Add(new Sparrow(boundary, this, texture));
            }

            for (int i = 0; i < nofRavens; i++)
            {
                Birds.Add(new Raven(boundary, this, texture));
            }
        }

        public void Update()
        {
            foreach (Bird bird in Birds)
            {
                bird.Update();
            }
        }

        public void Draw(SpriteBatch spriteBatch)
        {
            foreach (Bird bird in Birds)
            {
                bird.Draw(spriteBatch);
            }            
        }
    }

Finally, we need to implement the Game class to load, update and render the birds. As we also need something to actually draw to the screen, let’s add some programmers art first:

This image should be added to the Content project of the solution.

The Game class should look like this:

 
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;

        Flock flock;

        float elapsed;

        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }

        protected override void Initialize()
        {
            graphics.PreferredBackBufferWidth = 960;
            graphics.PreferredBackBufferHeight = 640;
            graphics.IsFullScreen = false;
            graphics.ApplyChanges();

            base.Initialize();
        }

        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);

            flock = new Flock(new Vector2(960, 640), 70, 3, Content.Load("bird"));
        }

        protected override void Update(GameTime gameTime)
        {
            elapsed += (float)gameTime.ElapsedGameTime.TotalMilliseconds;

            if (elapsed > 30f)
            {
                flock.Update();
                elapsed = 0f;
            }

            base.Update(gameTime);
        }

        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.Black);

            spriteBatch.Begin();

            flock.Draw(spriteBatch);

            spriteBatch.End();

            base.Draw(gameTime);
        }
    }

That’s it. A word of caution: running this program may be induce a somewhat hallucinating experience ;-)

Click here to dowload a video of the program running. (Why can’t I embed the video in this post?)

The project source is available here.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s