AI Planning

AI is one of the most important facets of a game. It not only provides interesting and challenging gameplay, but is also vital to a player's immersion. Choosing the right AI method to use is a very important decision, and one which depends heavily on the circumstances of the game and the development company.

There are many types of AI to choose from, but today we'll look at three different AI decision making methods - finite state machines, GOAP (Goal-Oriented Action Planning), and behavior trees. We'll use a simple problem that the AI entity must solve, to compare these methods:

“An NPC is standing on the bank of a river, and he wants to get to the  other side. He can walk, swim, and sail. Walking is the most  preferable, but can only happen if there is a bridge. Sailing is the  second most preferable, but can only happen if there is a boat.  Swimming is the last resort.” 

Finite State Machine

In a finite state machine, the different behaviors the entity can exhibit are sectioned off into states, which are connected by transitions, often accompanied by some condition. 

In this case, I represented the different conditions (bridge, no bridge, no boat) as separate states to keep the diagram from looking so cluttered with transitions, but this probably would more accurately have been represented as one state (where the behavior was standing on the river bank) with multiple transitions, each with their own conditions (bridge, no bridge but boat, no boat or bridge).

The advantage of a finite state machine is that it is fairly simple to understand and implement, and that you can represent pretty much any behavior in this fashion. The disadvantage is that the programmer must explicitly define all behavior and transitions/conditions manually, which can require a lot of time. Additionally, when representing vast complex actions, the FSM can become convoluted and difficult to follow.

GOAP

GOAP sacrifices run-time speed for development speed, placing the burden on the entity to make decisions based on action weighting and constraints. A GOAP representation of a problem consists of a goal, an initial state, and a set of actions the entity can choose from to reach the goal from the initial state. Each action must have a weighting, an effect, and a precondition.

GOAP can either build toward the goal from the initial state, or build backwards from the goal state towards the initial state. Both methods use a state space search method to build an optimal solution. In this case, we have a post condition where we've crossed the bridge. The GOAP system then Finds an action from it's database of possible actions which has an effect matching the end goal. Next, it checks if the precondition for this action is satisfied by the initial condition. If so, it has a possible solution, if not, it continues selecting actions matching the current state (effect) until it reaches the initial condition - though if no actions can reach the initial condition, it abandons the possible solution. Once it has a possible solution, it checks the value of the solution by adding up the weight of all the actions. It keeps doing this until it finds the lowest value solution, using a heuristic to perform a state space search. 

As you can imagine, this takes a lot of processing power, especially if there are many actions available. The trade off is that it makes the workload on the programmer much less, since he or she needs only code in possible actions for an entity, and the entity creates it's own solution for each particular problem. Compare this with creating a finite state machine for every possible problem, and you can see how it is easier on the programmer. For projects with limited programmer resources (time or number of programmers), this can be a great choice.

Behavior Trees

Behavior trees (actually directed acyclic graphs or DAGs) represent a breakdown of a task into smaller tasks. These break down until you reach the leaves of the tree, which represent the interface between the AI logic and the engine. These include conditions and actions. A task will continue to run it's action as long as it's condition is true, or until the action is complete. Parent tasks choose which child tasks can be run. This can be done in sequence, or by selection based on conditions. In a sequence, the parent task deals with the success of a child task by moving on to the next task in the sequence. For a selector, it tries to execute a child task and deals with failures by moving onto the next. Essentially, sequence moves on success while selector moves on failure.

In this example, the main task is to cross the river. Since there are several ways to do this, and not a sequence of ways, this will be a selector type task. It will try child tasks from left to right, so higher priority tasks go on the left. First it will try to walk over the bridge. If there is a bridge, this task will carry out until either it completes (success) or until there stops being a bridge (failure). As you can see, this allows for a change of action in the middle of the task, if for example the bridge is destroyed. A success of any of the tasks causes the parent to stop trying other child tasks, and return success to it's parent. Failure of all child classes will cause a return of failure to the parent - the bridge cannot be crossed in that case. However in our example, that won't happen, since the final child task (swim) has no conditions - it is always possible.

The tasks used for behavior trees have the advantage of being re-useable. They have the advantage of being more efficient during run-time, but they do take longer to create than a simple database of actions as in GOAP. However, it has been proposed to combine these two methods, using planning to dynamically build behaviour trees out of a database of tasks. This would allow programmers to explicitly define behaviour trees when it makes sense to do so, saving run time resources, but to build them dynamically when necessary.

Conclusion

No single AI method will be ideal for every game and every dev team. As with most development choices, it depends entirely on the circumstances. However, by combining AI techniques, smart programmers can get the best of both development and run-time efficiency.