Regex & State

Apr.02.2018 | 2m Read | ^AI

Machine Learning hogs the limelight in AI, but before perceptrons we had Finite State Machines. And Hierarchical Finite State Machines. And Behavior Trees with Behavior Trees of Hierarchical State Machines. And, and!

These are still used in games and Unreal Engine so let us read up and add a dash of Regex.

FSMs

Finite State Machines (FSMs) are a popular and simple software pattern to manage and change states (or saved events).

AI:

Virtual tiger Finite State Machine diagram  hunt->eat->preen->-sleep->infinite loop.

Artificial Intelligence state loops often use FSMs. Above is a simple series of states to manage a virtual tiger. A non-specific diagram for games can be sense (hunt) -> think (eat) -> react (preen) -> idle (sleep) -> loop.

Regex:

Regex ab*c+d?[ef] Finite State Machine diagram.

Regular Expressions are a series of events performed on a character String (an object that handles numbers, letters, and font icons). The epsilon character (ε), represents an optional state change.

Op Code:

Op code Esc[\d+;\d+fm and Esc[1m Finite State Machine diagram.

Operation Codes are String references to states for a machine or its Central Processing Unit (CPU). Above charts the Escape (Esc) sequence states of Op Codes (getting the machine to jump out of states and into 'neutral').

Complex Management:

When dealing with a multitude of states you may switch to Hierarchical State Machines (HSMs or Statecharts). An HSM has a superstate that links to substates, limiting the initial scope of complexity. They can be nested FSMs from a general to specialized form the lower you go. Or they can be flat so the primary factor is reusing transitional data.

▼ Features:

  • ☑⁡⁡⁡ Allows for the creation and manipulation of history.
  • ☑⁡⁡⁡ Also supports AND or parallel states and concurrent execution of events.

Another option is Behavior Trees (BTs) which like HSMs, also have parallel states and concurrent events. They can be combined in the same system with FSMs utilized to swap trees. Essentially BTs are a tree of events traversed down from the root node. More complex actions can be created by synching multiple trees.

▼ BT State Status:

  • ☑⁡⁡⁡ Running: the state is currently being processed.
  • ☑⁡⁡⁡ Success: the state has returned a 'success'.
  • ☑⁡⁡⁡ Fail: the state has returned a 'failure'.

▼ BT Node Structure:

  • ☑⁡⁡⁡ Composite Nodes (branch nodes): have multiple children.
  • ☑⁡⁡⁡ Decorator Node: have a single child or decoration.
  • ☑⁡⁡⁡ Leaf Node: the last or ending child in a traversal.

       : NEWS