Viveckh's Notepad

fsm-theory.png

  • Input vocabulary can be the game world
  • Each state is associated with a behavior
  • Agent responds to changes in the world state by transitioning to new states

# Mealy & Moore

mealy-moore.png

# Global Transitions

global-transitions.png

In the above example, the state can transition to Falling from any of the states, whether the current state is Blend Tree - Forward or Blend Tree - Backward. Instead of drawing transition arrows from each state to Falling, doing it from Any State makes the flow simpler to interpret..

# FSM Example

Using the graph form, design/visualize an FSM for a security guard that patrols a school after hours. If it sees the player it needs to seek the player and give them a lecture till the player can slip away. Otherwise, switch between Idle and Patrol

States = {Idle, Patrol, Seek, Lecture}

fsm-example-solution.png

# State transition tables

fsm-state-transition-table.png

# FSM Advantages

  • Popular and intuitive
  • Very little dev overhead & easy to visualize/debug
  • Low compute costs

# FSM Problems

  • Predictable
    • Can use fuzzy or probabilistic state machines to help some
      • Account for frame rates, when using this, otherwise, user with higher frame rates gets extra edge since their probability is computed more frequently and up-to-date.
  • Simplistic
    • Use hierarchies of FSM's (Half-life). Using FSM stack simplifies dev/debugging
  • Difficult to manage complexity
    • Can get stuck if all contingencies aren't considered
    • No. of states/transitions can blow up while accounting all contingencies
  • Does not work well with multi-step plans

# Implementations

fsm-proc-impl.png

fsm-object-oriented.png

# Parametrized Transitions

  • Often states need information on which to act. As FSM becomes complex, it can be challenging to make sure member variables are correctly set (e.g. activeTarget, currentPath, etc).
  • Parametrizing ChangeState() methods can make state requirements explicit, enforce that info be provided, and provide precondition enforcement opportunity.

fsm-parameterized-trans.png

# Safe state change

  • State changes can normally happen anywhere, including within UpdateState() of a particular FSM state. But this can create situations where the state changes but executes further code, and there might be side effects.

Therefore, enforcing a mechanism for enforcing deferred state changes may be desireable. For instance, only allow a state change request as part of an UpdateState(), return value that specifies either: stay in current state or change to this new state, (and here are parameters)

# Inaction Problem

  • It may be temting to write FSM state that only make decisions but don't themselves perform actions other than transitioning to a state that does perform an action.
  • If the FSM executes one state per simulation frame, this can lead to a lost frame before an action is taken.
  • Some FSM frameworks may indicate an immediate (same frame transition) to avoid delay but care must be taken to avoid infinite loops or arbitrary overhead per frame
  • It is generally better to implement methods for determining decisions rather than using FSM states for that purpose.

# Testing

# Debugging

fsm-debugging.png

# Ablation Testing

  • Temporarily disable states (and transitions to them)
  • Aids in identifying what values a state adds and whether it is worth keeping

# AB Testing

  • Pit version A and B of agent FSM implementation against one another (perhaps leveraging ablation testing)

# Alarm state problem

fsm-no-hierarchy.png fsm-hierarchy.png

The previous example shows an alarm state problem, where all the activities are affected when a predator is noticed. Another similar example can be a cleaning robot, all its search and dispose activities are affected when it runs low on power. And this single contingency can cause huge increase in complexity. So, using hierarchical structure simplifies this.

fsm-cleaning-bot.png

# Hierarchical FSM

  • Equivalent to regular FSMs, adding recursive multi-level evaluation
  • Hierarchical approach addresses entry, update, exit, and any (wildcards) at every level

# Transition from lower-state

  • Changes in world state event (input vocab) can be used for transitions at any level in hierarchy
  • If a low-level state does not handle a potential transition event, the unhandled event is dealt with at a higher level
  • Allows designer to avoid duplicating transitions
  • But we need a way for low-level state to transition out once high-level transition has been identified, which is explained below

# Recursive algorithm

You can learn more about this in the Millington book with examples

fsm-recursive-algo.png

# Mealy

fsm-hierarchical-mealy.png

# FSM Stack

fsm-hierarchical-stack.png

# Problems

  • Memory leak potential
  • Pop + Push New - this approach can help to avoid stack being empty/memory leak
  • May need restrictions such as
    • Cannot have two of the same state on the stack at the same time (or from same hierarchy family)
    • Pop + Push New required for state changes among sibling states within a hierarchical level (cannot push a sibling state without first popping self)

# Transition Problem

hfsm-transition-problem.png

# Solution

  • Practical FSM implementations may need additional support for multi-frame transitions (or additional states and transitions)
  • Example: An agent attack animation must finish first with a deferred transition
  • Example: Agent must sheath sword before beginning conversation with friendly NPC

# Probabilistic State Machines

Change probaility that character will perform a given action under certain conditions, instead of always performing a given action with 100% probability.

← Fuzzy Logic →