Lyndon Armitage

Flicking through my Java games book some more I found a chapter on flocking, a subject a university tutor of mine only managed to mention in passing on our AI module due to time constraints. As I find AI quite interesting I thought I’d look into the subject some more so I decided to write my own 2D demo application of flocking behaviour akin to the original proposed by Craig Reynolds in his paper and on his website.

The Java book itself contained it’s version of a tutorial using awt but I decided to stick with a newer library that I have worked in before called Slick2D (See my tutorial on Game States as an example of my use of it before). I also decided to stick with 2D instead of 3D as the book demonstrates so I can keep things simple.

This first post is going to be about setting up the basic game engine I will be using as the underlying driving force of the game/demo.

 Step 1: Set up Slick

Slick needs a little bit of setting up before you begin making and testing your creations with it. This is relatively simple, add the jar files as libraries and make sure to include the LWJGL native files on your library path.

See the Slick2D wiki for details if you’re unsure how to do this.

If you are working in IntelliJ then you need to make sure to add the natives to your java.library.path in your run configurations like so:

 Step 2: Extend the BasicGame and Start Coding

The next step to take is to create a new class that extends Slick’s BasicGame class.

public class BoidsGame extends BasicGame {
	public BoidsGame(String title) {
		super(title);
	}

	@Override
	public void init(GameContainer gc) throws SlickException {
		//To change body of implemented methods use File | Settings | File Templates.
	}

	@Override
	public void update(GameContainer gc, int delta) throws SlickException {
		//To change body of implemented methods use File | Settings | File Templates.
	}

	@Override
	public void render(GameContainer gc, Graphics g) throws SlickException {
		//To change body of implemented methods use File | Settings | File Templates.
	}
}

The BasicGame class basically gets rid of a lot of the coding you need to do to create a game; in the words of the JavaDoc it is: A basic implementation of a game to take out the boring bits.

As you can see it needs to have a few methods over-ridden; init() is run once when we start the game and should contain all the initialization, update() and render() are both run each game frame. update() is where you should place game logic and  render() is reserved for drawing onto the screen. You also need to implement a constructor that takes the title of your game as a parameter.

Next we need a main method that will launch the game. In Slick we do this using an AppGameContainer object. I’ve also added a few constants and fields to my class that are used here:

	private static final int WIDTH = 800;
	private static final int HEIGHT = 600;
	private static int targetFrameRate = 30;

	private AppGameContainer container = null;

	public static void main(String args[]) {
		BoidsGame game = new BoidsGame("Boids - By Lyndon Armitage");
		AppGameContainer app;
		try {
			app = new AppGameContainer(game, WIDTH, HEIGHT, false);
			app.setShowFPS(false);
			app.setTargetFrameRate(targetFrameRate);
			app.setPaused(true);
			game.container = app;
			app.start();
		} catch (SlickException e) {
			e.printStackTrace();
		}
	}

This when run will show an empty window that is 800 by 600 pixels in size.

 Step 3: A Boid Skeleton

Next on the agenda is to make a start on the individual Boid code.

First create a new Class named Boid. Being a visual and non static creature we will need to implement a way of showing and updating the Boid so will create two methods that will be called by those in the previous class, update() and render():

	public void render(GameContainer gc, Graphics g) {

	}

	public void update(GameContainer gc, int delta) {

	}

Now we need to decide what the Boid will look like on screen and what properties it needs that will be changing.

• A Boid needs:
  • A position in space. I choose to make this 2D so I opted for using a class built into Slick called Vector2f
  • A velocity. Again this is in 2D so I used Vector2f
  • A colour. Slick has a class for this called Color
  • An angle of where it is looking.
  • Height and width.
  • A shape. In keeping with the examples given on Boids I made them triangular
  • A field of view. To keep things simple I am using a whole circle around the Boid. A better way of doing this would be to chop out a section of the circle behind the boid so it cannot see behind it.

   

So what do these all look like?

	private float angle = 0f;
	private Vector2f pos;
	private Vector2f vel;
	private Color color;

	private static final float width = 8;
	private static final float height = 10;
	private static final int lineWidth = 1; // how many pixels thick the lines are

	private static final float viewDistance = 50f;

I’ve used static final values for things that I will not be changing during the simulation/game. Onto the code using these!

Firstly I implemented the basic code to update the position of the Boid based only on the velocity, this is quite simple:

		pos.x += vel.x / delta;
		pos.y += vel.y / delta;
		if (pos.x > gc.getWidth()) {
			pos.x = gc.getWidth() - pos.x;
		}
		if (pos.y > gc.getHeight()) {
			pos.y = gc.getHeight() - pos.y;
		}
		if (pos.x < 0) {
			pos.x = gc.getWidth();
		}
		if (pos.y < 0) {
			pos.y = gc.getHeight();
		}

Delta, for those who do not know what it is, is the time between frames and is used to ensure that everything is synced up and independent of the frame rate. In this example I also made the Boids play area loop round from top to bottom and left to right.

For this to work we need to initialize some of the objects we declared as variables. For this I created an init() method that I call from various constructors:

	public Boid() {
		init(0f, 0f, Color.white, 0f, 0f);
	}

	public Boid(float x, float y) {
		init(x, y, Color.white, 0f, 0f);
	}

	public Boid(float x, float y, Color color) {
		init(x, y, color, 0f, 0f);
	}

	public Boid(float x, float y, Color color, float velX, float velY) {
		init(x, y, color, velX, velY);
	}

	public Boid(float x, float y, float velX, float velY) {
		init(x, y, Color.white, velX, velY);
	}

	private void init(float x, float y, Color color, float velX, float velY) {
		pos = new Vector2f(x, y);
		vel = new Vector2f(velX, velY);
		this.color = color;
	}

These should cover all the ways I could want to create a Boid. We also need to add some getters for later use as I made all of the variables we defined private.

	public Color getColor() {
		return color;
	}

	public Vector2f getPos() {
		return pos;
	}

	public Vector2f getVel() {
		return vel;
	}

But wait, we can now update the Boids position but we still can’t see them! So we need to make the render() do something.

Below is the code I used to render the Boids, note that I made use of the graphics context given to us by Slick, a better way of drawing a triangle would of been to use LWJGL’s OpenGL methods directly  but opted to use Slick’s methods to show them off:

	public void render(GameContainer gc, Graphics g) {
		//g.drawString("boid", pos.x, pos.y);
		g.rotate(pos.x, pos.y, angle);
		g.setLineWidth(lineWidth);
		g.setColor(color);
		g.drawLine(pos.x - (width / 2), pos.y - (height / 2), pos.x + (width / 2), pos.y - (height / 2)); // bottom line
		g.drawLine(pos.x + (width / 2), pos.y - (height / 2), pos.x, pos.y + (height / 2)); // right to top
		g.drawLine(pos.x, pos.y + (height / 2), pos.x - (width / 2), pos.y - (height / 2)); // top to left
		g.resetTransform();
	}

Hopefully these method calls are pretty self explanatory; I first rotate the context, then I set the line width and colour, followed by drawing the lines and finally resetting the rotation. The lines are each drawn separately, first the bottom line of the triangle, next the right hand side line and last the left hand side line.

Step 4: Some Intelligence for the Boid

Now we have our basic Boid Skeleton code; we can see them and they can move but they have no intelligence so now we need to give them a brain just like the Scarecrow in Oz wanted!

The first thing I a Boid needs to be able to do is know the angle between itself an other Boids. To do this we can use a mathmatical function called the arctangent that when supplied with two values derived from the difference between two points will return the angle between them. In my code I implemented this function like this:

	private float getAngleToBoid(Boid target) {
		float deltaX = target.getPos().x - pos.x;
		float deltaY = target.getPos().y - pos.y;
		float angle = (float) (Math.atan2(deltaY, deltaX) * 180 / Math.PI);
		angle -= 90; // seems to be off by 90 degrees probably due to how the graphics are set up
		if (angle > 360f) {
			angle = 360f - angle;
		} else if (angle < 0f) {
			angle = 360f + angle;
		}
		return angle;
	}

Like most programming languages and libraries Math.atan2() returns an angle in radians so we need to convert these to degrees for our use, that’s what the multiplication and division by pi are for.

Next the Boid also needs to be able to discern the distance between it and other Boids, this is a very simple method to implement since it uses a well known forumla for measuring distance on a grid:

	private float getDistanceToBoid(Boid target) {
		Vector2f v = target.getPos();
		return (float) Math.sqrt(Math.pow(v.x - pos.x, 2) + Math.pow(v.y - pos.y, 2));
	}

And finally a Boid should also be able to figure out if another Boid is within range of it or not. The method I made to do this makes use of Pythagoras to check if it is with a circle around the Boid:

	private boolean isBoidInView(Boid target) {
		float dx = Math.abs(target.getPos().x - pos.x);
		float dy = Math.abs(target.getPos().y - pos.y);
		float radius = viewDistance / 2;
		if (dx > radius) {
			return false;
		}
		if (dy > radius) {
			return false;
		}
		if (dx + dy <= radius) {
			return true;
		}
		// Pythagoras here
		if (Math.pow(dx, 2) + Math.pow(dy, 2) <= Math.pow(radius, 2)) {
			return true;
		} else {
			return false;
		}
	}

It also does some checks beforehand to make sure we need to use Pythagoras.

Step 5: Add some Boids and test!

Up until now we havent added any Boids to the actual engine to test. In fact the engine doesn’t have any logic as of yet for dealing with the Boids. What we now need to do is write the code for the update() and render() methods!

This code is quite simple since the logic for the Boids will be contained within the Boids themselves. All I have done is added an ArrayList of Boids to the main game class and some code that loops through each Boid within calling their respective methods:

	private ArrayList boids = null;
	@Override
	public void init(GameContainer gc) throws SlickException {
		Random rnd = new Random();
		boids = new ArrayList();
		// add the boids
		Boid boid1 = new Boid(WIDTH / 2, HEIGHT / 2, rnd.nextInt(100), rnd.nextInt(100));
		boids.add(boid1);
		Boid boid2 = new Boid(WIDTH / 4, HEIGHT / 2, rnd.nextInt(100), rnd.nextInt(100));
		boids.add(boid2);
		gc.setPaused(false);
	}

	@Override
	public void update(GameContainer gc, int delta) throws SlickException {
		//System.out.println(delta);
		for (Boid b : boids) {
			b.update(gc, delta, boids);
		}
	}

	@Override
	public void render(GameContainer gc, Graphics g) throws SlickException {

		if (drawGrid) {
			drawGrid(g);
		}

		for (Boid b : boids) {
			b.render(gc, g);
			if (drawArc) {
				b.renderArc(g);
			}
		}

		if (debugOn) {
			g.setColor(Color.green);
			g.drawString("0,0", 10f, 0f);
			g.drawString(WIDTH + "," + HEIGHT, WIDTH - 65, HEIGHT - 18);
		}
	}

Notice that I have changed the method signature of the Boid method update() to include a reference to the ArrayList, this way we can tell each Boid were each of them are and develop behaviour accordingly. For example, this code will make a Boid look at the closest other Boid within range:

	public void update(GameContainer gc, int delta, ArrayList boids) {

		// some look at the closest boid in view code
		Boid target = null;
		float dist = 0;
		for (Boid b : boids) {
			if (b.getPos().x == pos.x && b.getPos().y == pos.y || !isBoidInView(b)) continue;
			if (target == null || getDistanceToBoid(b) < dist) {
				dist = getDistanceToBoid(b);
				target = b;
			}
		}
		if (target != null) {
			angle = getAngleToBoid(target);
		}

		updatePos(gc, delta); // This contains the original update() code
	}

Also you will notice references to debug features I added; including drawing the view arc around each Boid drawing a grid and drawing out the min and max coordinates in view.

When run at this stage we should get something similar to this when the two Boids go within range of each other:

The source code for this tutorial can be found on GitHub here: https://github.com/LyndonArmitage/Boids

The next part will hopefully deal with adding the various Flocking behaviours Separation, Alignment and Cohesion. For more information on Boids please visit Craig Reynolds website: http://www.red3d.com/cwr/boids/

Edit:

A flaw in the way I had my boids reacting to each other was exposed by Amndeep7 on Reddit, see the original comment here.

I had overlooked the fact that each time I updated a Boid their new values were then used by the next Boid in the loop, this meant that the results would not be valid. The original comment has a much better explanation than this so I encourage you to have a look at it. As for the code in this tutorial I will address the issue in the concluding post so for now I leave it as an exercise for the reader to figure out how to solve this problem, feel free to leave suggestions and solutions in the comments.