Adaptive AI Engine for RTS Games

Discussing the theory and practice

Finite State Machines (FSM)

Posted by Ogail on July 17, 2009

Finite State Machines (FSM)

  • FSM is a data structure used in AI contexts
  • Contents of state machine: machine states, several input conditions and transaction function
  • How transaction checking made in classic (271)
  • Most game FSM are coded using Moore model (272)
    • Where you put your actions inside the state instead of the transaction between states (Sit/ Stand Up Example)
    • Moore Model = Mealy Machine Model
  • PAC-MAN FSM Example:


  • FSM Skeletal Code:
    • FSMState class: the basic state in the system
    • FSMMachine class: houses all states and acts as state machine
    • FSMAIControl class: houses state machine and game specific code (such as perception data)
  • The FSMState class:
    • Each state should have following functions:
      • Enter(): this function is always run when you enter the state to do initializations
      • Exit(): run when leaving state to cleanup and run any code after leaving (Mealy State)
      • Update(): This is the main function that is called every AI processing call (Moore)
      • Init(): Resets the state
      • CheckTransition(): This function should return the enumeration value to next state to run
  • FSM Pros:
    • Easy to implement, debug and make code centralized
  • FSM Cons:
    • State oscillation


  • Extensions to FSM:
    • Hierarchical FSMs:
      • FS that contains another FS and called "super state"
    • Message and Event-Based FSMs:
      • Using events to triggers rather than polling model
    • FSMs with Fuzzy Transitions:
      • Adding more calculations or simple comparisons to the transition states
      • Most of the transition computations are done in the state itself rather than Control class
    • Stack-Based FSMs:
      • Use stack rather than current state so that you can make interpretations to the system and come back again to the previous state when interpretation done (Attack/Take Cover Example)
    • Multiple Concurrent FSMs:
      • multiple FSMs between multiple characters
      • multiple FSMs for same character
      • This issue in handled by a manager (could be General FSM) that coordinates between FSMs
      • RTS Game Example: AI opponent could need separate decision state machines for resources management, research and combat and so on. These FSMs might communicate throw an observer of some kind (could be a FSM that uses output of these FSMs as transition conditions)
      • Drawbacks of this issue: oscillations and data overwriting
    • Data-Driven FSM:
      • Motivation: adding new AI by nonprogrammers
      • Techniques to do this:
        • Scripted FSMs: easy for programmers hard for designers
        • Visual Editor: easy for designers hard for programmers
    • Inertial FSM:
      • If a state has been actuated, it stays actuated for some time, or that new states have to overcome some inertia before they can fire in the first place. This can be done in the states themselves or on the perceptions that fire the states
  • Optimizations to FSM:
    • Load Balancing Both FSM and Perceptions
      • Refers to spreading the amount of computation to be done over time to lessen the immediate load on the processor. This is done by:
        • Make system run at a set of scheduled rate (every 2 seconds)
        • Have system that give better results by having more time
    • Level of Detail (LOD) AI Systems:
      • Ignoring some AI details when they are not needed
      • Teleport example (Start 304)
    • Shared Data Structures:
      • If there is a computation that is done my many states then, this computation could be computed by one state and then be send to the sheared control so any other state can take the results without re-computing it
      • Blackboard paradigm (End 304)

You can separate the state-based portion of your code from the AI code

Advertisements

2 Responses to “Finite State Machines (FSM)”

  1. […] Finite State Machines (FSM) « Adaptive AI Engine For RTS Games […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: