Action and planning

People aren't inert.  We do things.  Characters are no different.  We perform actions, and those actions change things:

• The environment: turning on a heater changes the temperature of the room
• Yourself: eating makes you less hungry
• The relationship between yourself and the environment: walking changes your location
• Other people: feeding someone makes them less hungry

In some sense, the central problem of life is deciding what to do next.  It's our core loop.  And so the central problem of character AI is also action selection.  It often goes by other names, such as behavior selection or planning, but we'll use the term “action selection” here.

Examples

In combat games, combatant NPCs must decide whether to engage or flee, who to target and with what, where to take cover, and so on.  Their available actions are things like:

• Move some place
• Pick up an item
• Equip a weapon
• Load the weapon
• Aim
• Fire

In a game like The Sims, characters use objects to satisfy needs.  Actions involve things like:

• Eating
• Shopping
• Preparing food
• Drinking
• Socializing
• Watching TV

In some cases, it's not a particular character that's choosing actions, but rather the game itself, for example:

• Game master systems like the “AI director” in Left 4 Dead, which chooses when and where to spawn enemies so as to maintain a desired tension curve for the game.
• Storylet systems such as the one in Fallen London and Weird West.  These allow dynamic story generation based on gameplay by breaking the story into fragments and sequencing them dynamically.  Every bit of story is an action with its own effects and preconditions.

Action selection systems for games

An action selection system is a solver that chooses actions.  The designer authors a menu of available actions.  Then the game repeatedly presents the menu together with the current state to the solver, which chooses the action to perform next.

Many algorithmic frameworks have been developed for action selection.  To name but a few,

• Behavior trees
• Utility-based methods: assign a score (utility) to each action and take the one with the highest score.
• Needs-based AI: compute action utilities from the degrees to which each action satisfies numerical “needs” such as hunger and thirst.  This design was popularized in The Sims.

Often, it's impossible to choose an immediate action without considering which actions would come after it (planning) or at least what the game state would be after executing the action:

• Single-action lookahead: like utility approaches, but we score resulting game states rather than actions.  For each possible action, we simulate it and score the resulting game state.  That score is the utility of the action.  This was used in the Versu interactive fiction platform.
• Path planning: choose a path to take through space to get from one location to another
• Goal Oriented Action Planning (GOAP): given the game state, descriptions of the impact of different actions on the game state, and a desired change in the game state, find a sequence of actions that will produce that change.
• Hierarchical Task Network (HTN) planning: Given a task to perform and a set of methods for achieving different tasks, choose a series of tasks and methods to achieve the original task.  Step can be thought of as a kind of HTN planner.

Most of these approaches involve the system considering the effects of actions before committing to executing them.  This often takes the form of simulating the execution of the action and considering the resulting world state.