Feelings = nullptr; Guest AI

Blog Header Image

This week I gave the inn a reason to exist! Without guests it would just a big empty building with too many tables, beds, and innkeepers. Not that it has all of those features yet…

Behavior Trees

Unreal Engine has native support for a very powerful form of AI modelling called Behavior Trees. Instead of writing code with a lot of branches or devising clever hierarchical state machines, AI behaviors can be modelled as trees of tasks. Of course the same AI behaviors could be achieved with any of these methods, but behavior trees offer a unique visual representation that’s pretty easy to understand and debug.

For those already familiar with state machines, you can think of each branch of the tree as being a unique state (some with sub-states!) and moving between branches would be the same as transitions between states.

Task nodes

A very simple behavior tree might look like this:

Simple behavior tree

Starting from the root node, look for a task node in the tree to run. In this case the only node available is Move, so that’s what executes. Once the Move task completes, it sends a basic pass (AI moved) or fail (AI can’t move) up to the node above it. This might not seem very useful right now…

Composite nodes

To add more than one task to the behavior tree, another type of node is required: the Composite node. These nodes can hold more than one attached node.

Sequences

The simplest composite node is the Sequence. Each attached node in the sequence is executed from left to right. The intuitive interpretation is “Do this then that and then that too and then also that one”.

Behavior tree with sequence node

Execution:

  1. Root -> Sequence
  2. Root -> Sequence -> Find Player
  3. Root -> Sequence -> Move
  4. Root -> Sequence -> Talk
  5. Root -> Sequence -> Find Exit
  6. Root -> Sequence -> Move
  7. Root -> Sequence
  8. Root
  9. The end.

That would describe an AI that goes to talk to the player and then exits.

Did you notice that I didn’t say “each attached Task node” earlier? Composite nodes can also be attached!

Behavior tree with nested sequences

Now the tree is organized into two separate branches: “talk to the player” and “leave”.

Execution:

  1. Root -> Sequence 1
  2. Root -> Sequence 1 -> Sequence 1A
  3. Root -> Sequence 1 -> Sequence 1A -> Find Player
  4. Root -> Sequence 1 -> Sequence 1A -> Move
  5. Root -> Sequence 1 -> Sequence 1A -> Talk
  6. Root -> Sequence 1 -> Sequence 1A
  7. Root -> Sequence 1 -> Sequence 1B
  8. Root -> Sequence 1 -> Sequence 1B -> Find Exit
  9. Root -> Sequence 1 -> Sequence 1B -> Move
  10. Root -> Sequence 1 -> Sequence 1B
  11. Root -> Sequence 1
  12. Root
  13. The end.

What happens if a task (or node!) in a sequence fails? The sequence itself will fail instead of executing the next node.

Using the first tree as an example:

  1. Root -> Sequence
  2. Root -> Sequence -> Find Player (fail!)
  3. Root -> Sequence (fail!)
  4. Root
  5. The end.

Selectors

The AI still isn’t very sophisticated. What if we want the AI to leave if the player can’t be found? Using sequences the AI stops dead immediately after Find Player fails. The other major composite node, Selector, has nearly the opposite behavior of Sequence. Instead of executing until a node fails, Selector will continue until a node passes. It will continue executing even if nodes fail. If you read between the lines above, you’d have noticed that a Sequence where all nodes pass will also pass. A Selector where all nodes fail will also fail.

Sounds complicated and tricky to figure out why it’s useful, but the intuitive interpretation is “try all of these options until one works”. Let’s swap out the top Sequence in the last tree for a Selector.

Behavior tree with selector node

Now let’s say the player can’t be found (also labelling pass results this time):

  1. Root -> Selector
  2. Root -> Selector -> Sequence 1
  3. Root -> Selector -> Sequence 1 -> Find Player (fail!)
  4. Root -> Selector -> Sequence 1 (fail!)
  5. Root -> Selector -> Sequence 2
  6. Root -> Selector -> Sequence 2 -> Find Exit (pass)
  7. Root -> Selector -> Sequence 2 -> Move (pass)
  8. Root -> Selector -> Sequence 2 (pass)
  9. Root -> Selector (pass)
  10. Root
  11. The end.

Other Nodes

Nothing is ever so simple as it’s initially presented! Unreal Engine also adds in some handy shortcuts such as Decorator Nodes and Services. I’m not going to go into much detail on these other than to explain the final result when the guest AI tree is presented in the next section.

A Decorator node can make a branch fail early. For simple yes/no questions (e.g. is character hungry?) it’s conceptually similar to setting up a Selector branch and having the first task pass/fail depending on the character’s hunger level.

A Service node will continuously run while the rest of the branch is executing. This is very useful if checks need to be run regularly (e.g. Find all nearby seats).

If you didn’t understand much, most, any, or all of this section that’s fine! This is more of a rambling blog than an educational one :). More thorough introductions to the topic exist, but I hope you got a taste of the power of behavior trees.

Guests

Back to this game. Guests will start off with very simple behavior:

  • Move to the Inn
  • Look for an empty table
    • If there are no empty tables after waiting for a while, leave
  • Move to the table
  • Request service (food or drink)
    • If service takes too long, leave
  • Eat/Drink
  • Pay
  • Leave

Here’s how I implemented it, can you decipher what does and doesn’t work? Guest behavior tree

If you guessed the following… then you’d be right:

  • Move to the Inn
  • Look for an empty table
    • If there are no empty tables after waiting for a while, leave
  • Move to the table
  • Request service (food or drink)
    • If service takes too long, leave
  • Eat/Drink
  • Pay
  • Leave

What’s next???

Next week marks the start of the 2018 Epic MegaJam, so I’ll be taking time off to participate in that! For this game jam I’m going to try and stream 80-95% of the development process (excluding showerthoughts). Tune in on my Twitch channel starting on November 8th. For anyone who has been expecting the same amount of streaming for Twig development, I’m sorry to disappoint but it’s turned out to be unsustainable to chain myself to a desk and stream when so much of the initial development is happening in flashes and bursts of insight. Streams will still happen, just less frequently and not as long. :)

The time this upcoming week that I do spend on Twig will be focused on finishing AI behaviors and adding animations. Ideally a small segment of gameplay will be polished up before long.