State machine

See also Finite State Machine at Wikipedia

State machines can provide very powerful in-game artificial intelligence. They can be easy to implement and maintain, easy to debug, quick to run, and handle many differerent game styles.

Basic switch-based state machine

At the most simple level, each state must have an entry point and a way to move to the next state. Consider this simple state machine:

switch( npc[i].state )
{
 case state_idle:
   {
      // First, see if I should attack.
      target = TryToFindAttackTarget(npc[i]);
      if( target )
      {
        npc[i].SetTarget( target );
        npc[i].state = state_attack;
        break;
      }
      // Next, see if I should heal myself
      ... 
      // Check if I should heal neighbors
      ...
      /* other idle tasks */
      ...
   }
 case state_flee:
   {
  ...
   }
 case state_attack:
   {
     // Determine if the target is still valid.  Maybe it died.
     if( !npc[i].GetTarget() ) 
     {
        // Try to find a new target
        ...
     }
     // If I still don't have a target, go back to idle
     if( !npc[i].GetTarget() )
     {
       npc[i].state = state_idle;
     }
   } 
 case state_dead:
   {
  ... 
   }
...      
}

While this tree is simple, it is not easy to maintain, debug, or extend. We can improve on it by introducing a class hierarchy for individual states.

A more extensible example using inheritence

By deriving states from a simple base class, we can easily add new states without cluttering up existing states. We can create specialized states for bosses and tutorials. We can more easily use breakpoints. We can more easily reuse code. Code will be less complex. In short, it is a good thing all over.

namespace AI {  // Namespaces are a good thing.  If you don't know that yet, it is time to learn.

 enum StateType {
  idle,
  targeting,
  sleeping,
  ...
 };
 
 class StateBase  
 {
  ...
  public:
   // non-virtual.  These won't change in subclasses.
   StateBase ( StateType, std::string );   // It is often useful to have a string name for debugging, testing, and cheating.
   std::string GetName();
   std::string GetType();
 
   // These must be overridden
   virtual bool Validate( World::Character* ) =0;   // Ensure this state is legal for the character
   virtual void Enter( World::Character* ) =0;      // Called when a character enters this state
   virtual void Update( World::Character* ) =0;     // Called every update cycle
   virtual void Exit( World::Character* ) =0;       // Called when a character leaves this state
   ...
 } 
 
} // End namespace AI

With this code, rather than switching on the character's state, we can simply call something like this:

npc[i]->AIState()->Update();

An individual state can be written quickly and easily:

bool IntermediateBossAttackState::Validate( World::Character* boss )
{ 
  // simple preconditions
  ASSERT( boss );
  ASSERT( boss->IsBoss() );
 
  if( boss && boss->IsBoss() )
   return true;
  return false;
 }
 
void IntermediateBossAttackState::Update( World::Character* boss )
{
  ASSERT( boss );
  target = boss->GetTarget();
  ASSERT( target );
  if( target->GetType() == World::Character::Type::npc )
   { ... }
  else if ( target->GetType() == World::Character::Type::player )
   { ... }
  ...
  if( target->IsDead() )
    // Note: We allow the individual character to manage their own list of possible states
    // that enables us to let designers, storywriters and other script people to
    // figure out exactly which system belongs to which boss.
    TransitionToState( boss->GetAIStateFromType( AI::StateType::idle ) );
 }

This improved version meets the original goals stated above.

More areas of improvement

Obviously there are a lot of details not shown in this example.

This example shows no queue of future states and there are minimal details for transitioning between states. Each state in the system would probably need to interact with the behavior or animation system in some way to provide smooth animations for the actions and transitions between the animations, coupled with their audio cues and possibly any special effects.

Notes on choosing series of states

The recent game "Final Fantasy XII" exposed a lot of their AI in their Gambit system. It provides a useful example of how characters can exhibit complex behavior with a simple state system.

Each character had a series of slots available for AI. Each slot could be active or inactive. Each slot contains a condition and a command. On each AU update (run only once or twice per second), the character checks each active slot, in order, to see if the condition is met. If the condition is met and passes the simple validation, the command is issued.

Let's assume a character has only one slot active with the condition "Ally: HP < 70%" and the command "Cure". On each AI update, the character will search through each ally and check that condition.

CommandStatus AllyBasedGambit( World::Character* me, ConditionFunction condition, Command* command )
{
 ASSERT( me );
 ASSERT( condition );
 ASSERT( command );

 // Search for the first ally who meets the condition.
 allyiterator it = std::find( allies.begin(), allies.end(), condition );
 if( it != allies.end() )
 {
   // validate that player can use the command on the target
   // For example, the cure spell is not valid if I am silenced.
   if( command->Validate( me, *it )
   {
     // I passed validation.  Let's issue that command.
     me->DoCommand( command, *it );
     return CommandStatus::Succeeded;
   }
 }
 return CommandStatus::Failed;
}

This simple function could be used for thousands of possible condition and command pairs. Similar functions would exist for Enemy and Self.