This post is the second part of the talk I gave on the WTM and belongs to this root post.
We say that a machine is making decisions when it processes a set of information to generate an action that it wants to carry out.
In this section we’ll look at two of the most common decision making techniques used for games development: State machines and Behavior trees.
1. State Machines
This term was coined for the automata theory. A finite state machine (FSM) is a device which has a finite number of states it can be in at any given time and can operate on input to either make transitions from one state to another or to cause an output or action to take place. A FSM can only be in one state at any moment in time.
So in its purest form it consists of three elements: States, transitions and events. If you look at the following diagram:
This is a state machine that manages the movement of a hero on a game. His states are: standing, jumping, ducking, and diving. The machine can only be in one state at a time.
He can’t move from one state to another randomly, instead, each state has a set of transitions associated. In our example, to start ducking, he must first be at the standing state.
Finally, we call events to the sequence of inputs that are sent to the machine from the user (button presses and releases).
This FSM allows us to change the behavior of the hero, i.e., it causes the behavior of the entity mute depending on its internal state.
State machines can be concurrent, f.i., we could be using this one for movement, another one for combat, and another one for communication, allowing the hero to move, fight and swear at the same time.
State machines can also be hierarchical. They consists in a set of super states and sub states arranged in a tree structure. Events entered by the user runs down along the tree until a state is able to manage it. In the image below, the user inputs the press trigger event into the system. The super state combat cannot handle it, so it delegates the event to its child states. The child state firing is able to manage this event.
The entity must maintain an instance to the state machine, and implement an update method that calls the machine itself. After that, everything is delegated to our implementation of the StateMachine, which will manage logic and transitions between States.
2. Pushdown automaton
There’s one issue that traditional state machines have, and that’s their lack of memory. FSMs don’t keep a history. However, this could be useful sometimes, for instance, let’s imagine we want our hero to be able to shoot. Well, starting to shoot isn’t a big deal, he just transitions to the firing state from whichever state he is.
But, what will happen after the firing sequence is done? We don’t know, because we don’t remember in which state he was before starting to shoot.
This can be solved using a pushdown automaton. This FSM version stores states in a LIFO stack. The current state of the character will always be the last entered state. So in our example:
When the hero is about to start shooting, the firing state is pushed into the stack. The firing sequence is executed, and then, when it finishes, it pops out from the stack. The other states in the stack will emerge, making the character go back to his previous state.
3. Behavior Trees
For the last few years, behavior trees (BT) are the major formalism used in game industry to build complex AI behaviors. This success comes from the simplicity to understand, use and develop BT by non programmers.
As its name suggests, we could imagine them as a tree, with its leafs and its branches, where leafs contain actions which describe the overall behavior, and branches decide the relationships between leafs.
The key concept is that the leafs contain both their internal state and the logic of the actions. So to use a leaf, we first evaluate its internal state, and, depending on the result, we decide if we want to execute the action or not. Leafs will return two different states: Success and Failure.
There are several types of branches.
Selector branch iterates leafs until one of them returns Success, then it executes the logic inside that leaf and the tree is considered a success. As you can see here:
Our goal is to reach a safe spot, so we try to make different actions until one of them succeeds. First, we try to take cover. But there’s no hiding nearby, so the leaf returns failure. Then, we try to leave the risk area, but we can’t because the field around is too large. This leaf also returns failure. And so on, until one of the leafs succeeds, or until we run out of possibilities, in that case the system returns gdxAi’s native leaf Failure and the whole tree is given by failed.
To give an end to our tale, let’s imagine we asked the squad for cover fire, and they were available in range, the leaf ask for cover fire would have returned success, the action would have been performed, our hero would have been able to reach the safe spot, and the tree would have merrily given by succeeded. Cool.
The Sequence branch, on the contrary, evaluates the leafs until one of them returns Failure.
First, we look around searching for a safe spot. If we can find it, the leaf returns success. Then, we try to run to the spot. The leaf returns success and the action of running is executed. Finally, we do a barrel roll and get into cover. As far as everything goes well, each leaf executes its logic, one after another, until there are no more leafs to evaluate.
The tree will be considered a failure if any of the leafs on the sequence fails.
Also, use Parallel branch for concurrent and non-conflicting behaviors or for group behaviors:
Here’s my own try of behavior tree, based on davebaol’s example:
Yeah, it’s the behavior of a kitten, so what ¬¬
Focus on the third level of the tree:
- Parallel (lines 4 and 5) the kitten will simultaneously play and attempt to be distracted. There’s a 0.8 probability of getting distracted, so eventually this leaf will succeed.
- Sequence (lines 7 to 9) the kitten meows 3 times, then walks, then destroys something.
- Selector (lines 11 and 12) simulates a nap that will stop each 5 seconds.
The main problem with State Machines is the exponential growth of states and transitions. Even worse, states cannot be reused easily, without having to worry about transitions being invalid when they are reused for different portions of the AI logic. Essentially, State Machines lack a proper level of modularity.
Behavior Trees increase such modularity by encapsulating logic transparently within the states, making states nested within each other and thus forming a tree-like structure, and restricting transitions to only these nested states.
Therefore, we will use State Machines only for when we have a small and probably immutable amount of states and transitions.
- State machines reacts to events making transitions between states. wiki
- Pushdown automaton keeps a stack of states. wiki
- Behavior trees are composed by leafs and branches. Leafs contain both state and logic, and branches decide relationships. wiki
Keep going! In the next post we’ll speak about pathfinding. ->