Game AI – An Introduction to Behaviour Trees

ImpalerAugust 14th, 2014Last Updated: August 13th, 2014

8 910 20 minutes read

Game AI is a very broad subject and while there is a lot of material out there, I didn’t find something that introduces the concepts gently and at a slower, more understandable pace. This article will try to explain how to design a very simple but extendable AI system loosely based on the concept of Behaviour Trees.

What is AI?

Artificial Intelligence is the human-like behaviour exhibited by the entities participating in the game. It’s more the illusion of intelligence and thoughtful action performed by the entities than an actual intelligent reasoning driven behaviour. The goal is to try to fool the player into thinking that the other “intelligent” entities are controlled by humans and not by a machine. It’s easier said than done, but we can use a lot of tricks to achieve some really good, seemingly random and “intelligent” behaviours.

An Example

Before we jump right into the fun bit, let’s draft up a plan of what we want to achieve. Again, I will use droids as an example. Imagine an arena where droids will battle it out amongst them and whichever droid is the last one standing is the winner.

The arena will be a board and droids will be placed randomly on it. We’ll make it a turn based game so we can follow the whole AI unfold, but it can be easily turned into a realtime game.

The rules are simple:

The board is a rectangle
A droid can move one tile per turn in either direction to any of the adjacent unoccupied tiles
A droid has a range and can fire at droids within its range
The droids will have the usual attributes: damage they inflict and hit points

For the sake of simplicity we will use very simple structures. The application will have a Droid class and a Board class. A droid will have the following attributes that define it:

public class Droid {

    final String name;
    int x;
    int y;
    int range;
    int damage;
    int health;

    Board board;

    public Droid(String name, int x, int y, int health, int damage, int range) {
        this.name = name;
        this.x = x;
        this.y = y;
        this.health = health;
        this.damage = damage;
        this.range = range;
    }

    public void update() {
        // placeholder for each turn or tick
    }

    /* ... */
    /* getters and setters and toString() */
    /* ... */
}

The Droid is just a simple pojo with a few attributes. The attributes are self explanatory but here’s a short summary of them:

name – the unique name of the droid, can be used for ID as well.
x and y – the coordinates on the grid.
health, damage and range – what it says.
board – is the reference to the Board the droid is on along with other droids. We need this because the droid will make decisions by knowing its environment, which is the board<./li>

There is also an empty update() method which is called each time the droid finishes its turn. If it’s a realtime game, the update method is called from the game loop, ideally from the game engine.

There are also the obvious getters and setters and the toString() method which are omitted from the listing. The Board class is vey simple.

public class Board {

    final int width;
    final int height;

    private List<Droid> droids = new ArrayList<Droid>();

    public Board(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public int getWidth() {
        return width;
    }

    public int getHeight() {
        return height;
    }

    public void addDroid(Droid droid) {
        if (isTileWalkable(droid.getX(), droid.getY())) {
            droids.add(droid);
            droid.setBoard(this);
        }
    }

    public boolean isTileWalkable(int x, int y) {
        for (Droid droid : droids) {
            if (droid.getX() == x && droid.getY() == y) {
                return false;
            }
        }
        return true;
    }

    public List<Droid> getDroids() {
        return droids;
    }
}

It has a width and a height and it contains a list of droids. It also contains a few convenience methods to check if a droid is already present at a given coordinate and a method to easily add droids one by one.

So far this is pretty standard. We can scatter a few droids on the board but they will not do anything. We can create the board, add some droids to it and start calling update(). They are only some dumb droids.

Not so Dumb Droids

To make a droid do something, we could implement the logic in its update() method. This is the method called every tick or in our case every turn. For example we want our droids to wander around the arena (board) and if they see an other droid in range, engage them and start firing at them until they die. This would be a very rudimentary AI but is still a AI.

The pseudo code would look like this:
if enemy in range then fire missile at it otherwise pick a random adjacent tile and move there

This means any interaction between the droids will result in a stand-off and the weaker droid gets destroyed. We might want to avoid this. So we can add that if a droid is likely to lose, then try to flee. Stand and fight only if there is nowhere to escape.
if enemy in range then if enemy is weaker then fight otherwise if escape route exists then escape otherwise fight otherwise wander

This is all good. The droids will start acting “intelligently” but they are still very limited unless we add more code to do more clever things. And also, they will act the same. Imagine if you drop them in a more complicated arena. An arena where there are items like power-ups to pick up to enhance powers, obstacles to avoid. For example decide between picking up a health/repair kit and picking up a weapon power-up when droids are swarming around.
It can get out of hands quite quickly. Also what if we want a differently behaving droid. One is an assault droid and the other one is a repair droid. We could achieve this of course with object composition, but the brains of the droids will be extremely complicated and any change in game design will require tremendous effort to accommodate.

Let’s see if we can come up with a system that can solve these problems.

Here Comes the Brain

We can think of the AI module of the droid as some kind of a brain. The brain is composed of several routines that act on the droid following a set of rules. These rules govern the execution of the routines so it maximises the chances of survival and winning the game as an ultimate goal. If we think of our human brain consisting of routines and having Maslow’s hierarchy of needs as a reference , we can identify a few routines instantly.

Physiological routine – a routine that needs to be executed every time otherwise there won’t be any living
Subsistence routine – this routine needs to be executed once the living conditions have been met so the long term existence is secured
Aspirational routine – this will be executed if there is time left after the subsistence has been secured and before subsistence needs to be executed again

Let’s break the human intelligence down a bit. A human needs to breathe to live. Each breath consumes energy. One can breathe so much until it runs out of energy. To replenish the energy one needs to eat. One can only eat if he/she has food at his/her disposal. If there is no available food, it needs to be acquired which consumes some more energy. If the procurement of food takes a long time (needs to be hunted for example) and the amount of food obtained is small, after eating it, the human is in need of more food and the routine restarts without delay. If the food was bought in bulks from a supermarket, after eating it, there is plenty left so the human can move on to do more interesting things which are in his/her aspirational section. Things like making friends or wage war or watch television for example.
Just think of how many things are in a human brain to make us function and try to simulate it. This all by disregarding most of the stimuli we are getting and responding to them. To do this, we would need to parametrise the human body and each sensor triggered by a stimulus will update the correct parameters and the executed routine will examine the new values and act accordingly. I won’t describe it now but you get the idea I hope.

Let’s switch back to our much simpler droids. If we try to adapt the human routines to the droids we’ll get something like this:

Physiological / Existential – this part we can ignore for this example because we design robots and they are mechanical beings. Of course for them to exist, they still need energy (eg. action points) which they can take from a battery or from some other energy source which can be depleted. For the sake of simplicity we will ignore this and consider the energy source to be infinite.
Subsistence / Safety – this routine will make sure that the droid will survive the current turn and live by avoiding an immediate threat.
Aspirational – this kicks in once the safety routine checked out OK and didn’t have to activate the droid’s fleeing routine. The current simple aspiration for the droid is to kill the other droids.

Although the described routines are very simple and can be hard-coded, the approach we will take to implement is a bit more elaborate. We will use an approach based on behaviour trees.

First and foremost we need to delegate every activity of the droid to its brain. I will call it Routine instead of brain. It can be called Brain or AI or anything, but I have chosen Routine because it will serve as a base class for all the routines that will consist of. Also it will be in charge of governing the flow of information in the brain. The Routine itself is a finite state machine with 3 states.

public abstract class Routine {

    public enum RoutineState {
        Success,
        Failure,
        Running
    }

    protected RoutineState state;

    protected Routine() { }

    public void start() {
        this.state = RoutineState.Running;
    }

    public abstract void reset();

    public abstract void act(Droid droid, Board board);

    protected void succeed() {
        this.state = RoutineState.Success;
    }

    protected void fail() {
        this.state = RoutineState.Failure;
    }

    public boolean isSuccess() {
        return state.equals(RoutineState.Success);
    }

    public boolean isFailure() {
        return state.equals(RoutineState.Failure);
    }

    public boolean isRunning() {
        return state.equals(RoutineState.Running);
    }

    public RoutineState getState() {
        return state;
    }
}

The 3 states are:

Running – the routine is currently running and will act on the droid in the next turn. Eg. the routine is responsible to move the droid to a certain position and the droid is in transit and still moving uninterrupted.
Success – the routine has finished and it succeeded doing what it was meant to be doing. For example if the routine is still the “move to position”, it succeeded when the droid reached the destination.
Failure – using the previous example (move to), the moving of the droid was interrupted (either the droid got destroyed or some unexpected obstacle appeared or some other routine interfered) and it didn’t reach the destination.

The Routine class has the act(Droid droid, Board board) abstract method. We need to pass in the Droid and the Board because when the routine acts, it does so on the droid and in the knowledge of the droid’s environment which is the board. For example the moveTo routine will change the droid’s position each turn. Usually when the routine acts on the droid, it uses the knowledge gathered from its environment. This knowledge is modelled on the realities of the situation. Imagine that the droid (like us humans) can’t see the whole world but only as far as its sight range. Us humans have a field of view of about 135 degrees so if we would be simulating a human, we’d pass in a slice of the world containing the section we see and all the visible components in it and let the routine process just that to the best of its capabilities and come to a conclusion. We could do that for the droids too, and just pass in the section of the board that is covered by the range, but we will keep it simple for now and use the whole board. The start(), succeed() and fail() methods are simple public overridable methods that set the state accordingly. The reset() method on the other hand is abstract and it has to be implemented by each concrete routine to reset any internal state proprietary to that routine. The rest are convenience methods to query the state of the routine.

Learning to Walk

Let’s implement the first concrete routine which will be the MoveTo discussed above.

public class MoveTo extends Routine {

    final protected int destX;
    final protected int destY;

    public MoveTo(int destX, int destY) {
        super();
        this.destX = destX;
        this.destY = destY;
    }

    public void reset() {
        start();
    }

    @Override
    public void act(Droid droid, Board board) {
        if (isRunning()) {
            if (!droid.isAlive()) {
                fail();
                return;
            }
            if (!isDroidAtDestination(droid)) {
                moveDroid(droid);
            }
        }
    }

    private void moveDroid(Droid droid) {
        if (destY != droid.getY()) {
            if (destY > droid.getY()) {
                droid.setY(droid.getY() + 1);
            } else {
                droid.setY(droid.getY() - 1);
            }
        }
        if (destX != droid.getX()) {
            if (destX > droid.getX()) {
                droid.setX(droid.getX() + 1);
            } else {
                droid.setX(droid.getX() - 1);
            }
        }
        if (isDroidAtDestination(droid)) {
            succeed();
        }
    }

    private boolean isDroidAtDestination(Droid droid) {
        return destX == droid.getX() && destY == droid.getY();
    }
}

It’s a very basic class that will move the droid one tile towards the destination until it reaches it. It does not check for any other constraint than if the droid is alive. That’s the condition for failure. The routine has 2 parameters destX and destY. These are final attributes which the MoveTo routine will use to achieve its target. The routine’s single responsibility is to move the droid. If it can’t do that it will fail. That’s it. Single responsibility is very important here. We will see how we’ll combine these to achieve more complex behaviours. The reset() method simply sets the status to Running. It has no other internal state or values to deal with, but it needs to be overridden.
The heart of the routine is the act(Droid droid, Board board) method which performs the action and contains the logic. First it checks for the failure condition, which is if the droid is dead. If it’s dead and the routine is active (its status is Running) then the routine failed to do what it was supposed to. It calls the super class’s default fail() method to set the status to Failure and exits the method.
The second part of the method checks for the success condition. If the droid is not yet at the destination, then move the droid one tile towards the destination. If its’ reached the destination, set the state to Success. The check for isRunning() is made to make sure that the routine only acts if the routine is active and hasn’t finished.

We also need to fill in the Droid‘s update method to make it use the routine. It’s just a simple delegation. This is how it looks like:

public void update() {
        if (routine.getState() == null) {
            // hasn't started yet so we start it
            routine.start();
        }
        routine.act(this, board);
    }

It should consist only of line #6 but I also put in a check to see if the state is null and if so, then start the routine. This is a hack to start the routine the first time update is called. It’s a quasi command pattern, as in the act method gets the receiver of the action command as a parameter, which is the droid itself. I also modified the Routine class to log the different events in it, so we can see what’s happening.

// --- omitted --- */
    public void start() {
        System.out.println(">>> Starting routine: " + this.getClass().getSimpleName());
        this.state = RoutineState.Running;
    }

    protected void succeed() {
        System.out.println(">>> Routine: " + this.getClass().getSimpleName() + " SUCCEEDED");
        this.state = RoutineState.Success;
    }

    protected void fail() {
        System.out.println(">>> Routine: " + this.getClass().getSimpleName() + " FAILED");
        this.state = RoutineState.Failure;
    }
    // --- omitted --- */

Let’s put it to test with a simple Test class.

public class Test {

    public static void main(String[] args) {
        // Setup
        Board board = new Board(10, 10);

        Droid droid = new Droid("MyDroid", 5, 5, 10, 1, 2);
        board.addDroid(droid);

        Routine moveTo = new MoveTo(7, 9);
        droid.setRoutine(moveTo);
        System.out.println(droid);

        // Execute 5 turns and print the droid out
        for (int i = 0; i < 5; i++) {
            droid.update();
            System.out.println(droid);
        }
    }
}

It’s a standard class with a main method which firsts sets up a square 10 x 10 Board and adds a Droid with the provided attributes at the coordinates 5,5. On line #10 we create the MoveTo routine which sets the destination to (7,9). We set this routine to be the only routine of the droid (line #11) and print the droid’s state (line #12). Then we execute 5 turns and display the droid’s state after each turn.

Running the Test we see the following printed to the sysout:

Droid{name=MyDroid, x=5, y=5, health=10, range=2, damage=1}

>>> Starting routine: MoveTo

Droid{name=MyDroid, x=6, y=6, health=10, range=2, damage=1}

Droid{name=MyDroid, x=7, y=7, health=10, range=2, damage=1}

Droid{name=MyDroid, x=7, y=8, health=10, range=2, damage=1}

>>> Routine: MoveTo SUCCEEDED

Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}

Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}

As we can see the droid starts at position (5,5) as expected. Calling the update method for the first time, starts the MoveTo routine. The subsequent 3 calls to the update will move the droid to the destination by changing its coordinate each turn by one. After the routine succeeded, all the calls passed to the routine are ignored, because it’s complete.

This is the first step, but it’s not very helpful. Let’s say we want to have our droid wander around the board. To achieve this, we will need to execute the MoveTo routine repeatedly, but every time it restarts, the destination needs to be randomly picked.

Wandering About

But let’s start with the Wander routine. It’s nothing more than a MoveTo but we generate a random destination given that we know the board.

public class Wander extends Routine {

    private static Random random = new Random();
    private final Board board;
    private MoveTo moveTo;

    @Override
    public void start() {
        super.start();
        this.moveTo.start();
    }

    public void reset() {
        this.moveTo = new MoveTo(random.nextInt(board.getWidth()), random.nextInt(board.getHeight()));
    }

    public Wander(Board board) {
        super();
        this.board = board;
        this.moveTo = new MoveTo(random.nextInt(board.getWidth()), random.nextInt(board.getHeight()));
    }

    @Override
    public void act(Droid droid, Board board) {
        if (!moveTo.isRunning()) {
            return;
        }
        this.moveTo.act(droid, board);
        if (this.moveTo.isSuccess()) {
            succeed();
        } else if (this.moveTo.isFailure()) {
            fail();
        }
    }
}

Following the single responsibility principle, the Wander class’s sole purpose is to pick the random destination on the board. Then it uses the MoveTo routine to get the droid to the new destination. The reset method will restart it and pick a new random destination. The destination is set in the constructor. If we’d like our droid to wander, we would change the Test class to the following:

public class Test {
    public static void main(String[] args) {
        // Setup
        Board board = new Board(10, 10);

        Droid droid = new Droid("MyDroid", 5, 5, 10, 1, 2);
        board.addDroid(droid);

        Routine routine = new Wander(board);
        droid.setRoutine(routine);
        System.out.println(droid);

        for (int i = 0; i < 5; i++) {
            droid.update();
            System.out.println(droid);
        }
    }
}

The output would be something similar to this:

Droid{name=MyDroid, x=5, y=5, health=10, range=2, damage=1}

>>> Starting routine: Wander

>>> Starting routine: MoveTo

Droid{name=MyDroid, x=6, y=6, health=10, range=2, damage=1}

Droid{name=MyDroid, x=7, y=7, health=10, range=2, damage=1}

Droid{name=MyDroid, x=7, y=8, health=10, range=2, damage=1}

>>> Routine: MoveTo SUCCEEDED

>>> Routine: Wander SUCCEEDED

Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}

Droid{name=MyDroid, x=7, y=9, health=10, range=2, damage=1}

Notice how the Wander contains and delegates to the MoveTo routine.

Repeat, Repeat, Repeat …

This is all good but what if we want the droid to be wandering repeatedly? We will make a Repeat routine which will contain a routine to be repeated. Also we will make this routine so that it can take in a parameter to specify how many times we want to repeat a routine. If it won’t take in a parameter, then it will repeat the containing routine forever or until the droid’s dead.

public class Repeat extends Routine {

    private final Routine routine;
    private int times;
    private int originalTimes;

    public Repeat(Routine routine) {
        super();
        this.routine = routine;
        this.times = -1; // infinite
        this.originalTimes = times;
    }

    public Repeat(Routine routine, int times) {
        super();
        if (times < 1) {
            throw new RuntimeException("Can't repeat negative times.");
        }
        this.routine = routine;
        this.times = times;
        this.originalTimes = times;
    }

    @Override
    public void start() {
        super.start();
        this.routine.start();
    }

    public void reset() {
        // reset counters
        this.times = originalTimes;
    }

    @Override
    public void act(Droid droid, Board board) {
        if (routine.isFailure()) {
            fail();
        } else if (routine.isSuccess()) {
            if (times == 0) {
                succeed();
                return;
            }
            if (times > 0 || times <= -1) {
                times--;
                routine.reset();
                routine.start();
            }
        }
        if (routine.isRunning()) {
            routine.act(droid, board);
        }
    }
}

The code is easy to follow but I’ll explain a few things that were added. The attribute routine is passed in the constructor and that will be the routine that gets repeated. The originalTimes is a storage variable that holds the initial number of times value, so we can restart the routine with the reset() call. This is just a back-up of the initial state. The times attribute is how many times the provided routine will be repeated. If it’s -1 then it’s infinite. This is all coded in the logic inside the act method. To test this out, we need to create a Repeat routine and provide what to repeat. For example, to have the droid wander endlessly, we’d have this:

Routine routine = new Repeat((new Wander(board)));
        droid.setRoutine(routine);

If we’d call the update repeatedly, we’ll see that the droid will be moving constantly. Check this sample output:

Droid{name=MyDroid, x=5, y=5, health=10, range=2, damage=1}

>> Starting routine: Repeat

>>> Starting routine: Wander

>>> Starting routine: MoveTo

Droid{name=MyDroid, x=4, y=6, health=10, range=2, damage=1}

>>> Routine: MoveTo SUCCEEDED

>>> Routine: Wander SUCCEEDED

Droid{name=MyDroid, x=4, y=7, health=10, range=2, damage=1}

>>> Starting routine: Wander

>>> Starting routine: MoveTo

Droid{name=MyDroid, x=5, y=6, health=10, range=2, damage=1}

Droid{name=MyDroid, x=6, y=5, health=10, range=2, damage=1}

Droid{name=MyDroid, x=7, y=4, health=10, range=2, damage=1}

Droid{name=MyDroid, x=8, y=3, health=10, range=2, damage=1}

Droid{name=MyDroid, x=8, y=2, health=10, range=2, damage=1}

>>> Routine: MoveTo SUCCEEDED

>>> Routine: Wander SUCCEEDED

Droid{name=MyDroid, x=8, y=1, health=10, range=2, damage=1}

>>> Starting routine: Wander

>>> Starting routine: MoveTo

Droid{name=MyDroid, x=7, y=2, health=10, range=2, damage=1}

Droid{name=MyDroid, x=6, y=3, health=10, range=2, damage=1}

Notice how the Repeat routine does not end.

Assembling the Intelligence

So far we’re just composing behaviours. But what if we want to add decision making to the droids and build a more complex behaviour? Enter the behaviour trees. This term doesn’t describe what it is and neither do most of the articles that I found. I’ll start with what I want to achieve first and hopefully it will all make sense. I want to implement the behaviour described at the beginning of the article. I want my droid to scan if there is a weaker droid in its range and engage it if it is, or flee otherwise. Take a look at the following diagram. It shows a tree. It’s nothing more than a routine composed of multiple different routines. Each node is a routine and we will have to implement some special routines.

Let’s break the routines down.

Repeat – is the routine implemented earlier. It will repeat the given routine forever or until the embedded routine fails.
Sequence – the sequence routine will succeed only when all the routines that it contains have succeeded. For example to attack a droid, the enemy droid needs to be in range, the gun needs to be loaded and the droid needs to pull the trigger. Everything in this order. So the sequence contains a list of routines and acts on them until all succeed. If the gun is not loaded then there is no point in pulling the trigger so the whole attack is a failure.
Selector – this routine contains a list of one or more routines. When it acts, it will succeed when one of the routines in the list succeeds. The order in which the routines are executed is set by the order in which the routines are passed in. If we’d like to randomise the execution of routines, it’s easy to create a Random routine whose sole purpose is to randomise the list of routines passed in.
All the grey routines are leaves in the tree, meaning that they can’t have any subsequent routines and these are the ones that act on the droid which is the receiver.

The above tree represents the very basic AI we wanted to implement. Let’s follow it through starting from the root.
Repeat – will repeat the selector indefinitely until neither of the branches can be executed successfully. The routines in the selector are: Attack a droid and Wander. If both fail that means that the droid is dead. The Attack a droid routine is a sequence of routines meaning that all of them have to succeed in order for the whole branch to succeed. If it fails, then the fall back is to pick a random destination through Wander and to move there. Then repeat.

All we need to do is to implement the routines. For example the IsDroidInRange could look something like this:

public class IsDroidInRange extends Routine {

    public IsDroidInRange() {}

    @Override
    public void reset() {
        start();
    }

    @Override
    public void act(Droid droid, Board board) {
        // find droid in range
        for (Droid enemy : board.getDroids()) {
            if (!droid.getName().equals(enemy)) {
                if (isInRange(droid, enemy)) {
                    succeed();
                    break;
                }
            }
        }
        fail();
    }

    private boolean isInRange(Droid droid, Droid enemy) {
        return (Math.abs(droid.getX() - enemy.getX()) <= droid.getRange()
                || Math.abs(droid.getY() - enemy.getY()) < droid.getRange());
    }
}

It’s a very basic implementation. The way it determines if a droid is in range, is by iterating through all the droids on the board and if the enemy droid (assuming that the names are unique) is within range, then it succeeded. Otherwise it failed. Of course we need to feed in this droid to the next routine somehow, which is IsEnemyStronger. This can be achieved by giving the droid a context. One simple way could be that the Droid class could have an attribute nearestEnemy and on success the routine will populate that field and on failure it will clear it. This way the following routine can access the droid’s internals and use that information to work out its success or failure scenarios. Of course this can be and should be extended so the droid will contain a list of droids in its range and have a routine to work out if the droid should fly or fight. But it’s not the scope of this introduction.

I won’t be implementing all the routines in the article, but you will be able to check out the code on github: https://github.com/obviam/behavior-trees and I will be adding more and more routines.

Where to go from here?

There are quite a few improvements that can be made just by looking at it. As a first step to test the system out, I’d move the creation of the routines to a factory for convenience.

/**
 * Static convenience methods to create routines
 */
public class Routines {

    public static Routine sequence(Routine... routines) {
        Sequence sequence = new Sequence();
        for (Routine routine : routines) {
            sequence.addRoutine(routine);
        }
        return sequence;
    }

    public static Routine selector(Routine... routines) {
        Selector selector = new Selector();
        for (Routine routine : routines) {
            selector.addRoutine(routine);
        }
        return selector;
    }

    public static Routine moveTo(int x, int y) {
        return new MoveTo(x, y);
    }

    public static Routine repeatInfinite(Routine routine) {
        return new Repeat(routine);
    }

    public static Routine repeat(Routine routine, int times) {
        return new Repeat(routine, times);
    }

    public static Routine wander(Board board) {
        return new Wander(board);
    }

    public static Routine IsDroidInRange() {
        return new IsDroidInRange();
    }

}

This will allow to test some scenarios out in a more elegant way. For example to place 2 droids with different behaviours you could do the following:

public static void main(String[] args) {
        Board board = new Board(25, 25);
        Droid droid1 = new Droid("Droid_1", 2, 2, 10, 1, 3);
        Droid droid2 = new Droid("Droid_2", 10, 10, 10, 2, 2);

        Routine brain1 = Routines.sequence(
                Routines.moveTo(5, 10),
                Routines.moveTo(15, 12),
                Routines.moveTo(2, 4)
        );
        droid1.setRoutine(brain1);

        Routine brain2 = Routines.sequence(
            Routines.repeat(Routines.wander(board), 4)
        );
        droid2.setRoutine(brain2);

        for (int i = 0; i < 30; i++) {
            System.out.println(droid1.toString());
            System.out.println(droid2.toString());
            droid1.update();
            droid2.update();
        }
    }

Of course this is not the best solution by far but it’s still better than the constant instantiation of routines. Ideally the AI should be scripted and loaded from an external source, either via scripting, or at least provided as a JSON for example and have a AI assembler create it. This way the game does not need to be recompiled every time the AI is tweaked. But again, it is not the scope of this article.

Also, how shall we decide which action will take up a turn/tick or is evaluated instantly? One possible solution could be to allocate action points to the droid that it can spend one turn (tick if realtime) and for each action to assign a cost. Whenever the droid runs out of points, then we can move on. We’d also need to track which routine is the current one so we can optimise the traversal of the tree. This is helpful if the AIs are very complex especially in realtime games.

If you think the article was useful and want to get the code, please check the github repo. You can also check back because I intend to extend it and to update it so it evolves into a more complete AI example. As it is my first encounter with AI, there will be lots of things to improve and I am always open to criticism and ideas on how to improve.