Overview and implementation of Finite State Machines (FSMs), reference books

Finite State Machines

A finite state machine, also called a finite state automaton, is a model used in computer science and information theory. A finite state machine consists of a finite number of states and rules for transitioning between those states.

A finite state machine has the behavior of transitioning to the next state based on the current state and input. States are usually represented by graphical elements such as circles or rectangles, and transitions are indicated by arrows. Inputs are also defined to trigger state transitions.

Since a finite state machine has a finite number of states, its behavior after reaching a particular state is deterministic. This will be used in a variety of areas, including software and hardware design, automatic control systems, and protocols.

A finite state machine is usually represented as a model consisting of the following three elements

• States: represent the states in which the system may exist. These can be states such as on/off, open/closed, wait/run, etc.
• Inputs: represent inputs given to the system. Inputs are represented as specific events or signals and serve to trigger state transitions.
• Transitions: These are the rules that govern the movement between states. This allows transitions from the current state to the next state based on inputs.

Finite state machines may be represented in the form of state transition diagrams or state transition tables, and extended models include hierarchical and stochastic finite state machines.

Finite state machines are useful for modeling and understanding the behavior of complex systems, and programming languages and tools can be used to implement finite state machines. In practical applications, programming languages such as C, C++, Python, and Java can be used to represent states as variables or enumerated types, and transitions as conditional branches or control flows.

The following is a simple example of a finite state machine implementation in Python.

# state definition
states = ['A', 'B', 'C', 'D']

# Initial state setting
current_state = 'A'

# Transition rules based on input events
transitions = {
    'A': {'event1': 'B', 'event2': 'C'},
    'B': {'event3': 'C'},
    'C': {'event4': 'D'},
    'D': {}
}

# event processing
def process_event(event):
    global current_state

    if event in transitions[current_state]:
        current_state = transitions[current_state][event]
        print(f'Transition: {current_state}')
    else:
        print('Invalid event for current state.')

# event execution
process_event('event1')  # Transition: B
process_event('event4')  # Invalid event for current state.
process_event('event3')  # Transition: C
process_event('event4')  # Transition: D

In the above example, the states are represented as strings, the transition rules are defined as a dictionary, and the process_event function updates the current state based on the given event and displays the transition results.

The algorithm used in this finite state machine is described next.

Algorithms used in finite state machines

Several algorithms are used to implement finite state machines. The following is a description of some of the most common algorithms.

• State Transition Table: The state transition table is a table that indicates the next state based on the states and inputs. The table is usually implemented as a two-dimensional array or hash map, and the algorithm uses the current state and input as table indices to obtain the next state.
• State Transition Diagram: A state transition diagram is a graphical representation of states and transitions. States are represented by nodes and transitions by arrows. The algorithm searches the transition diagram to determine the next state based on the current state and input.
• Mealy and Moore Machines: Mealy and Moore machines are two common variants of state-transition machines, in which outputs are generated simultaneously with state transitions, specifically, with transitions to the next state based on the current state and input. The outputs here are usually represented as part of a transition diagram or transition table; in a Moore machine, the outputs are a type of finite state machine with outputs associated with states. Mealy machines are used for modeling systems and communication protocols that operate based on inputs, while Moore machines are used for modeling systems whose outputs depend only on the state, such as control circuits and sequence control.
• Graph search algorithms: Graph search algorithms (e.g., depth-first and breadth-first search) are used to explore state transition diagrams to find appropriate state transitions. These algorithms are particularly useful when the finite state machine is large or complex.

The following libraries and platforms are used to implement these algorithms.

Libraries and platforms used for finite state machines

Various programming languages, frameworks and libraries are used to implement finite state machines. The following is a list of representative libraries and platforms among them.

• Python:
  • transitions: transitions is a lightweight library that supports FSMs in Python. It defines states and transitions, allows changing states based on events, and provides a concise and intuitive API to easily manage state transitions.
• JavaScript:
  • xstate: xstate will be a library that provides powerful support for state management in JavaScript and TypeScript. xstate defines states and transitions, manages state changes and event handling, provides a variety of advanced features, and supports nested states, guards It supports conditions, actions, effects, and more.
  • javascript-state-machine: javascript-state-machine is a lightweight library for implementing a simple FSM, which defines states and transitions and allows changing states by events. javascript-state-machine provides an intuitive API for easy creation and control of state machines.
  • machina.js: machina.js is a flexible library that supports implementing state machines in JavaScript, defining states and transitions, and adding actions and guard conditions. It also provides hooks to customize event handling and state changes.
• C++:
  • Boost.Statechart: Boost.Statechart is a powerful library supporting state transitions in C++ and is part of the Boost library, providing flexible state machine definition and management, including state and transition definition, event handling, and history management. The library has the following features
  • TinyFSM: TinyFSM is a lightweight, easy to use FSM library for C++.
• Java:
  • EasyFlow: EasyFlow is a simple library for implementing state machines in Java.
  • Spring Statemachine: Spring Statemachine is an FSM library provided as part of the Spring Framework. Spring Statemachine is integrated with Spring’s convenience features, making it easy to control and monitor your state machine.
  • Apache Commons SCXML: An implementation of SCXML (State Chart XML), a state transition model for Java, SCXML will be an XML-based language for representing finite state machines.
• Arduino: 
  • Arduino Finite State Machine Library: The Arduino Finite State Machine Library simplifies the implementation of state machines. The Arduino Finite State Machine Library provides functions for managing state transitions and executing actions.
• Unity:
  • Playmaker: Playmaker is a visual programming tool on Unity with FSM support. Playmaker is very popular and used by many developers.
  • Behavior Designer: Behavior Designer will be a powerful FSM library available in the asset store. It allows you to configure AI and character behavior using a graphical editor, and connect nodes and transitions to define behavior without using programmatic controls.
  • FSM AI Template: The FSM AI Template is a free Unity asset that can be used as a template for implementing FSM. It defines states and transitions and provides a way to process FSMs within C# scripts. It has the flexibility to add, delete, or modify states and transitions.

The following sections describe examples of the application of these finite state machines.

Application Examples of Finite State Machines

Finite state machines have been widely applied in various domains. The following are representative examples of some of these applications.

• Software development
  • UI/UX State Management: In the development of graphical user interfaces (GUIs) and mobile applications, finite state machines are used to manage state based on screen states and user actions. These allow control of screen display and operation based on state transitions.
  • Protocol and communication control: Finite state machines are used in the implementation of networking and communication protocols. These can be used to control the transmission and reception of data based on the state of packets and the state of incoming packets.
• Hardware control:
  • Automata: Finite state machines are used in the design of digital circuits and embedded systems. They allow devices to operate and generate control signals based on sensor states and external inputs.
• Automated control systems:
  • Robot control: Finite state machines are used to control the behavior of robots. They can be used to control the behavior and actions of robots based on sensor data and task states.
• Game Development:
  • Game AI: Finite state machines are used to model the behavior of characters and NPCs (non-player characters) in games. These can be used to generate appropriate actions and reactions based on the state of the characters and the actions of the player.
• System Control:
  • Sequence control: In manufacturing and automation systems, finite state machines are used to manage the operation of machines and devices. They can be used to control the operation of machines and the progress of work according to the state of processes and events.

The cases of UI and game state management are described in detail below.

On state management of UI and games using finite state machines

<Overview>

Finite state machines can be very useful for state management in UIs and games. In particular, since games change state based on player input and events in the game, finite state machines are suitable for modeling their behavior and are widely used. Below we discuss the advantages of using finite state machines for game state management and how they can be implemented.

Advantages:

• Lucid state transitions: Finite state machines clearly define the different states in a game and the transitions between them. This makes game state transitions predictable and easy to understand.
• State-dependent actions: Each state can be associated with an action or process that should be performed in that state. This allows actions to be performed that are only valid in a particular state.
• Bug identification and correction: A finite state machine explicitly defines the states and state transitions of the game, making it easier to identify and correct bugs. It also makes it easier to identify incorrect behavior or inappropriate transitions in state transitions.

Implementation Methods

• Define states and transitions: Define different states in the game and explicitly define transitions between them. Each state represents a specific situation or condition in the game.
• Event handling: Player input and events in the game are handled based on the appropriate state. Depending on this state, only certain events will be accepted.
• Execution of actions: Each state is associated with an action or process that should be executed in that state. Specific actions can be executed on transition, or actions can be set to be executed periodically within a state.
• Graphics and sound control: It is also possible to control the display and playback of graphics and sounds depending on the game state. Specifically, specific effects or music can be set to play when a specific state is entered.
• Game progress control: Finite state machines can also be useful for game progress control. For example, states such as start, pause, and end of a game can be defined and appropriate transitions and actions can be set.

Thus, by using a finite state machine to manage game states, it is possible to design game logic and behavior more flexibly and effectively.

Next, we will discuss a concrete implementation example using python.

<Example Implementation in Python>

The following is an example implementation of game state management using a finite state machine in Python. This example shows a simple state transition of a player character.

class PlayerState(Enum):
    IDLE = 0
    WALKING = 1
    RUNNING = 2
    JUMPING = 3

class Player:
    def __init__(self):
        self.state = PlayerState.IDLE

    def update(self, input):
        if self.state == PlayerState.IDLE:
            if input == 'MOVE':
                self.state = PlayerState.WALKING
            elif input == 'JUMP':
                self.state = PlayerState.JUMPING
        elif self.state == PlayerState.WALKING:
            if input == 'STOP':
                self.state = PlayerState.IDLE
            elif input == 'RUN':
                self.state = PlayerState.RUNNING
        elif self.state == PlayerState.RUNNING:
            if input == 'STOP':
                self.state = PlayerState.WALKING
        elif self.state == PlayerState.JUMPING:
            if input == 'LAND':
                self.state = PlayerState.IDLE

# Game main loop
player = Player()
while True:
    # Receive player input
    input = get_player_input()

    # Update player status
    player.update(input)

    # Drawing and processing games
    render_game()

    # Proceed to next frame
    advance_frame()

In the above example, the enumerated type PlayerState is defined to represent the player’s state, and the Player class uses the update method to handle player state transitions, determining the current state based on the player’s input and transitioning to the next state. The game’s main loop receives the player’s input and updates the player’s state. It also draws and processes the game and proceeds to the next frame.

Reference Information and Reference Books

For more information, including automata theory, see “Automata and State Transitions/Petri Nets and Automated Programming. For more information on game AI and agent technology, see “Artificial Life and Agent Technology.

Reference book is “Understanding of Finite State Machine“

“Finite State Machines and Algorithmic State Machines: Fast and Simple Design of Complex Finite State Machines“