The Project | About Us | Contribute | Donations | License

HOME

Finite State Machines (FSM) are a fundamental concept in AI for video games, providing a structured way to model the behavior of game characters. This section will cover the basics of FSM, their components, how to implement them, and practical exercises to solidify your understanding.

What is a Finite State Machine?

A Finite State Machine is a computational model used to design algorithms. It consists of:

States: Different conditions or modes in which an entity can exist.
Transitions: Rules that define how the entity moves from one state to another.
Events: Triggers that cause transitions between states.
Actions: Operations performed when entering, exiting, or during a state.

Key Concepts

States: Represent different behaviors or modes.
Transitions: Define the conditions under which the state changes.
Events: External or internal inputs that trigger transitions.
Actions: Tasks executed during state transitions or while in a state.

Example: Simple FSM for a Guard NPC

Consider a guard NPC in a game with the following states:

Patrolling: The guard moves along a predefined path.
Chasing: The guard chases the player when detected.
Returning: The guard returns to the patrol path after losing the player.

State Diagram

[Patrolling] --(PlayerDetected)--> [Chasing]
[Chasing] --(PlayerLost)--> [Returning]
[Returning] --(ReachedPatrolPath)--> [Patrolling]

Implementation in Code

Let's implement this FSM in Python:

class State:
    def __init__(self, name):
        self.name = name

    def on_enter(self):
        pass

    def on_exit(self):
        pass

    def update(self):
        pass

class Patrolling(State):
    def on_enter(self):
        print("Entering Patrolling State")

    def update(self):
        print("Patrolling...")

class Chasing(State):
    def on_enter(self):
        print("Entering Chasing State")

    def update(self):
        print("Chasing the player...")

class Returning(State):
    def on_enter(self):
        print("Entering Returning State")

    def update(self):
        print("Returning to patrol path...")

class GuardFSM:
    def __init__(self):
        self.states = {
            "Patrolling": Patrolling("Patrolling"),
            "Chasing": Chasing("Chasing"),
            "Returning": Returning("Returning")
        }
        self.current_state = self.states["Patrolling"]
        self.current_state.on_enter()

    def change_state(self, new_state_name):
        self.current_state.on_exit()
        self.current_state = self.states[new_state_name]
        self.current_state.on_enter()

    def update(self, event):
        if self.current_state.name == "Patrolling" and event == "PlayerDetected":
            self.change_state("Chasing")
        elif self.current_state.name == "Chasing" and event == "PlayerLost":
            self.change_state("Returning")
        elif self.current_state.name == "Returning" and event == "ReachedPatrolPath":
            self.change_state("Patrolling")
        self.current_state.update()

# Example usage
guard = GuardFSM()
guard.update("PlayerDetected")
guard.update("PlayerLost")
guard.update("ReachedPatrolPath")

Explanation

State Class: A base class for all states.
Patrolling, Chasing, Returning Classes: Derived from the State class, each implementing specific behaviors.
GuardFSM Class: Manages state transitions and updates based on events.

Practical Exercise

Exercise 1: Extend the Guard FSM

Task: Add a new state called "Investigating" where the guard investigates a suspicious noise before returning to patrolling.

Steps:

Define a new Investigating state class.
Update the GuardFSM class to handle transitions to and from the Investigating state.
Implement the logic for the Investigating state.

Solution:

class Investigating(State):
    def on_enter(self):
        print("Entering Investigating State")

    def update(self):
        print("Investigating noise...")

class GuardFSM:
    def __init__(self):
        self.states = {
            "Patrolling": Patrolling("Patrolling"),
            "Chasing": Chasing("Chasing"),
            "Returning": Returning("Returning"),
            "Investigating": Investigating("Investigating")
        }
        self.current_state = self.states["Patrolling"]
        self.current_state.on_enter()

    def change_state(self, new_state_name):
        self.current_state.on_exit()
        self.current_state = self.states[new_state_name]
        self.current_state.on_enter()

    def update(self, event):
        if self.current_state.name == "Patrolling" and event == "PlayerDetected":
            self.change_state("Chasing")
        elif self.current_state.name == "Chasing" and event == "PlayerLost":
            self.change_state("Returning")
        elif self.current_state.name == "Returning" and event == "ReachedPatrolPath":
            self.change_state("Patrolling")
        elif self.current_state.name == "Patrolling" and event == "NoiseHeard":
            self.change_state("Investigating")
        elif self.current_state.name == "Investigating" and event == "InvestigationComplete":
            self.change_state("Patrolling")
        self.current_state.update()

# Example usage
guard = GuardFSM()
guard.update("NoiseHeard")
guard.update("InvestigationComplete")
guard.update("PlayerDetected")
guard.update("PlayerLost")
guard.update("ReachedPatrolPath")

Common Mistakes and Tips

State Explosion: Avoid creating too many states. Combine similar behaviors where possible.
Transition Conditions: Ensure transitions are mutually exclusive to prevent conflicting states.
State Actions: Clearly define actions for entering, exiting, and updating states to maintain clarity.

Conclusion

Finite State Machines provide a robust framework for modeling character behaviors in video games. By understanding states, transitions, events, and actions, you can create complex and realistic NPC behaviors. Practice implementing FSMs and extending them to handle various scenarios to deepen your understanding.

Next, we will explore Decision Trees, another powerful tool for decision-making in game AI.

Finite State Machines (FSM)

What is a Finite State Machine?

Key Concepts

Example: Simple FSM for a Guard NPC

State Diagram

Implementation in Code

Explanation

Practical Exercise

Exercise 1: Extend the Guard FSM

Steps:

Solution:

Common Mistakes and Tips

Conclusion

AI for Video Games

Module 1: Introduction to AI in Video Games

Module 2: Navigation in Video Games

Module 3: Decision Making

Module 4: Machine Learning

Module 5: Integration and Optimization

Module 6: Practical Projects

Module 7: Additional Resources