In my previous article I talked about designing a dungeon generation system for the roguelike I'm working on, Explore. Today I'm going to talk about writing the AI and some of the design decisions behind enemies.

Speed and Timing

Explore, like many roguelikes before it, is a turn-based game. With that, I wanted some sort of way to work in a "speed" statistic for players and enemies. What I came up with is a pretty simple system. Both the player and enemies have a speed stat, and they take turns at rates defined by that stat.

Specifically, the player always takes one turn at a time. Enemies always take a number of turns defined by their speed compared to the player's speed. For example, if the player's speed is 10 and an enemy's speed is 5, the enemy will take a single turn for every two the player takes. If the enemy's speed is 20, then they will take two turns for every turn the player takes.

Another example: if the enemy's speed is 12. This means that an enemy takes 1.2 turns for every turn the player takes - well, not really. That fractional amount is added up over time - eventually the enemy will take two turns after a single player turn.

Representing Turns

Now, to the player, this may be somewhat confusing. How do you know when an enemy is going to take a turn? What about two (or more) turns? This is the system I came up with.

This is an enemy that isn't going to be taking a turn once the player moves.

This is the same enemy, but this time it will take a turn right after the player does (enemies always take their turns after the player does). The red outline is the way of knowing that it will be taking a turn.

Finally, here's a different enemy that's about to take two turns in a row. The outline is thicker to signify this.

Now, this isn't meant to be an exact system. It is an intentional design decision that the player can't just look at a number for each enemy and determine their speed - not without actually paying attention. I don't know if this is how things will stay, but that's the reasoning behind it. Additionally, I'm planning that enemy speeds will generally scale to take at most two turns at a time as to not burden the player too heavily. That's part of a larger discussion about balance, however.

Scripting AI

With turns out of the way, I can get to actually scripting AI. Initially, the enemies in the dungeon were fairly simplistic - each one would have a component attached that would have a hardcoded set of actions it would take. For zombies, they used a FollowAndAttackAI component which did some pathfinding to the player for movement, and would attack when appropriate.

This isn't horribly flexible. If, for example, I want a version of a zombie that runs in, attacks, then runs away I'd need to write a completely new component that shares much of the code with FollowAndAttackAI but is changed enough to warrant having it be separate. This is not an ideal way to write more complex behaviors - ideally, I want to be able to combine a bunch of simple actions to create complex behavior with as much code reuse as possible (always the ideal, however achieveable it may be).

Behavior Trees

My solution to the issue of scripting AI is the behavior tree model. Behavior trees are a fairly elegant way to script behavior - they're made up of reusable "nodes" that each comprise a single simple action to take, but can be used to simulate incredibly complex behaviors.

A behavior tree is represented by, as the name implies, a tree. A single node sits at the root of the tree, and each node may have children. Generally, leaf nodes (nodes that have no children) make up actual actions for the AI to take while nodes that have children are for flow-control.

Additionally, each node has a result after it finishes executing - success or failure. For my implementation, I also have an extra result returned at the end of an action, which signifies whether the turn should end or not. This is because a behavior tree may take multiple AI turns to execute, and not all actions should take up a turn.

Composite Nodes

Nodes that have children are known as "composites". They generally don't do much on their own, but instead execute their child nodes in a specific way. Different behavior tree implementations will generally have different sets of composites, but a few tend to be very common across the board.

Sequence

A sequence node executes each of its children in order until either a child node fails or there are no children left. If a child node fails, the sequence stops further execution of children nodes and the result of the sequence is failure. If all children succeeded, then the result of the sequence is success.

Generally, sequences are used to group sets of actions together, for example if you want an AI to open a door you would have a sequence of movement towards the door, the opening of the door, and moving through the door. If any single action fails, the rest do not execute.

Selector

A selector node executes each of its children in order until either a child node succeeds or there are no children left. If a child node succeeds, the selector stops further execution and the result of the selector is success. If all children failed, then the result of the selector is failure.

Generally, selectors are used to select an action to take in order of priority. If an AI's priority is to open doors, that may be the first child of a selector. If the AI can't open the door, the next course of action might be to try to knock the door down instead, which would be the second child.

Decorator Nodes

Decorators are generally nodes that modify the result of another node or do checks to make sure an action is allowed. In my implementation specifically, they are nodes that have exactly one child.

Invert

The invert decorator inverts the result of its child node. If the child returns success then the result of the invert node is failure and vice-versa.

Force Result

The force result decorator always has a specific result, irregardless of the result of its child node.

Action Nodes

Action or "leaf" nodes are any nodes that do not have children. They actually perform tasks for the ai. Actions are pretty diverse, and some may be purely utility (like checking if the player is visible to the AI) while others might make the AI move towards the player.

Storage

In order to facilitate communcation between different nodes in a behavior tree, there's also an instance-specific storage system (sometimes called a blackboard). Each instance of an AI has its own storage that can be accessed by whatever behavior tree it is using.

Bringing it together

There are other selectors and decorators, but the best way to learn about behavior trees is to see an actual example. Here's a graph of what the basic zombie AI is in Explore:

Note that blue boxes here are action nodes, while white boxes are composite nodes. No decorators are used in this tree.

Starting from the root, we immediately hit a sequence node called FollowAndAttack. This is our starting point. From here, we can see that the first action that will be called is GetPlayer.

GetPlayer retrieves the player entity and stores it into the "target" location in the AI's storage. If that fails (like if the player doesn't exist for some reason), then we will end up failing the whole tree and the AI will do nothing that turn (remember, FollowAndAttack is a sequence node - if any direct child fails, then it stops execution and fails as well).

Next we come to the SelectAction selector. This is where the AI decides what to do. The two children of SelectAction are sequences that each represent one overall action the AI can take.

The AttackPlayer sequence handles attacking the player. The first child, CheckDistance, makes sure the AI is at most one tile away from whatever is in the "target" location in AI storage (which is the player, since that's what GetPlayer handled earlier). If the player is not in range, the CheckDistance node fails which also fails AttackPlayer. If it succeeds, then we move onto the Attack node which triggers the AI to attack the player.

If anything fails in AttackPlayer, then the SelectAction selector will move on to FollowPlayer. The first child is, again, a CheckDistance - this time to make sure the player is within a reasonable distance before following. Next, we have a Follow action which moves the AI one space towards the player.

In Code

There's no fancy XML scripting system just yet (see the dungeon generator for that) and I may or may not implement one in the future. In the meantime, I did build a nice behavior tree construction system that makes it fairly quick to define one. Here's the above AI in code:

var myTree = new BehaviorTreeBuilder()
    .Sequence("FollowAndAttack") // start a sequence named "FollowAndAttack"
        .Do("GetPlayer", BasicNodes.GetPlayer("target")) // Do() creates an action node with the specified name (names are purely informational) and action. 
                                                         // BasicNodes.GetPlayer() creates an action node that stores the player into the specified location in storage.
        .Selector("SelectAction")
            .Sequence("AttackPlayer")
                .Do("CheckDistance", BasicNodes.MaxDistance("target", 1))
                .Do("Attack", BasicNodes.Attack("target"))
            .End()
            .Sequence("FollowPlayer")
                .Do("CheckDistance", BasicNodes.MaxDistance("target", 12))
                .Do("Follow", BasicModes.MoveTo("target")) // despite what it sounds like, MoveTo only moves one tile on the path to the target
            .End()
        .End() // end the SelectAction sequence
    .Build(); // end the FollowAndAttack sequence and return the finished tree

The Jester

As an ending to this article, here's a behavior tree for a new enemy I'm currently calling a "Jester". See if you can deduce what exactly it does.

var myTree = new BehaviorTreeBuilder()
    .Sequence("Jester")
        .Do("GetPlayer", BasicNodes.GetPlayer("target"))
        .Selector("SelectAction")
            .Sequence("MoveAway")
                .Do("CheckDistance", BasicNodes.MaxDistance("target", 2))
                .Do("GetDirection", BasicNodes.GetDirectionAwayFrom("target", "direction")) // gets a direction vector away from "target" and stores it to "direction"
                .Do("Move", BasicNodes.Move("direction")) // moves in a specific direction
            .End()
            .Sequence("ThrowRocks")
                .Do("CheckDistance", BasicNodes.MaxDistance("target", 4)
                .Succeed("SpawnUp-Succeed", false) // We want to ignore spawning failures, as we always want to try all spawn positions one way or the other. The second argument here is whether to end the AI's turn, which again we don't want to.
                    .Do("SpawnUp", BasicNodes.SpawnProjectile<ProjectileTemplate>(Vector2d.Up, Vector2d.Up)) // First argument of SpawnProjectile is the spawn position offset from the AI, the second argument is the direction of movement for the projectile
                .End()
                .Succeed("SpawnDown-Succeed", false)
                    .Do("SpawnDown", BasicNodes.SpawnProjectile<ProjectileTemplate>(Vector2d.Down, Vector2d.Down))
                .End()
                .Succeed("SpawnLeft-Succeed", false)
                    .Do("SpawnLeft", BasicNodes.SpawnProjectile<ProjectileTemplate>(Vector2d.Left, Vector2d.Left))
                .End()
                .Succeed("SpawnRight-Succeed", false)
                    .Do("SpawnRight", BasicNodes.SpawnProjectile<ProjectileTemplate>(Vector2d.Right, Vector2d.Right))
                .End()
            .End()
            .Sequence("FollowPlayer")
                .Do("CheckDistance", BasicNodes.MaxDistance("target", 12))
                .Do("Follow", BasicNodes.MoveTo("target"))
            .End()
        .End()
    .Build();