AI in games II – Decision making

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

Definition

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:

source

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.

 

Concurrent FSM

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.

 

Hierarchical FSM

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.

jerarquico

 

Implementation

maquinasdeestadosThe 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:

state-pushdownsource

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.

 

References

Read gdxAi wiki for further information. Also here‘s the best post about FSM I’ve ever read so far. gdxAi provides this package for FSM management.

 

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.

Behavior trees have been originally pioneered by robotics and soon adopted for controlling AI behaviors in commercial games such as first-person-shooter Halo 2 and life-simulation game Spore.

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.

 

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.

 

Branches

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:

selector

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.

sequence

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.

You could also execute leafs randomly using Random Selector and Random Sequence branches.

Also, use Parallel branch for concurrent and non-conflicting behaviors or for group behaviors:

parallel

 

Implementation

gdxAi recommends to implement behavior trees in a external way, either using formatted text or external libraries, and then everything is translated into Tasks.

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.

 

4. Conclusion

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.

In brief:

  • 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. ->

 

 

 

Facebooktwittergoogle_plusredditpinterestlinkedintumblrmail

Leave a Reply

Your email address will not be published. Required fields are marked *

Proudly powered by WordPress | Theme: Baskerville 2 by Anders Noren.

Up ↑