Hello! Welcome to the first lesson of our new module on Advanced FSM Patterns.
So far, you've successfully built and applied FSMs to manage a complete, round-based game loop. You've orchestrated player spawning, UI updates, and even player controls, all from a central, server-side state machine. This demonstrates just how powerful FSMs can be for creating robust and predictable game logic.
However, as systems grow in complexity, the simple FSM structure we've used can start to show its limits. In this lesson, we will explore these limitations. Our learning outcome is to identify common design problems in complex FSMs, such as 'transition explosion' and state duplication.
Understanding these challenges is the crucial first step before we can explore the more advanced patterns designed to solve them.
The Slippery Slope of Complexity
Imagine you're adding features to an NPC. A simple jump action seems easy at first. But then you need to prevent "air jumping." Then you add ducking, but you must prevent standing up mid-jump. Then you add a dive attack, which introduces more rules and more boolean flags to track the character's status. Each new feature risks breaking existing ones.
This is a common experience in game development. The code becomes a tangled web of if statements and flags, making it fragile and difficult to reason about. Let's read a short passage that illustrates this exact scenario.
State · Design Patterns Revisited - Game Programming Patterns
The book Game Programming Patterns by Robert Nystrom has an excellent chapter on the State pattern. The introduction perfectly captures how quickly simple character logic can become a mess.
Please read the sections titled "We’ve All Been There" and "Finite State Machines to the Rescue". This will walk you through building up a Heroine controller and show how adding simple moves leads to buggy, hard-to-maintain code, which sets the stage for why we use FSMs in the first place.
As the text explains, an FSM is the solution to this initial chaos. It organizes the logic by enforcing a clear structure: a finite set of states and explicit transitions between them. But what happens when the FSM itself becomes the source of complexity?
Problem 1: State Duplication and Code Redundancy
Let's consider the NPC AI you want to build. You might have states like Idle, Patrol, Chase, and Attack. Now, let's add a new dimension: what if the NPC can pick up different weapons?
If the NPC has a pistol, its Attack state is different from its melee Attack state. But its Idle and Patrol states are likely identical, whether it's armed or not. How would you model this?
A naive approach would be to create a whole new set of states: IdleWithPistol, PatrolWithPistol, ChaseWithPistol, etc. This leads to our first major problem: state duplication.
Let's read about this specific issue.
State · Design Patterns Revisited - Game Programming Patterns
The same Game Programming Patterns chapter discusses this problem directly. It shows how adding a seemingly simple, independent piece of state (like carrying a gun) can cause a combinatorial explosion in the number of states.
Read the section titled "Concurrent State Machines". Focus on how adding a weapon forces you to double the number of states and creates significant code redundancy.
This combinatorial explosion is a huge source of bugs and maintenance headaches. You are duplicating not just the states, but also the logic within them. If you want to change how the NPC patrols, you now have to change it in Patrol and PatrolWithPistol.
This problem also appears when multiple states share a lot of common logic. The developer of the game Gunpoint and Heat Signature ran into this when trying to manage states like Dead and Unconscious. Both states make the guard immobile, but he found himself writing if state ~= "Dead" and state ~= "Unconscious" all over his code, and every time he added a new "immobile" state, he had to update every single one of those checks. This is a form of logic duplication that stems from having similar, but separate, states.
This issue of duplicating logic across states is also called out in the following video.
Beyond the RTOS Part-4: state machines as "spaghetti" reducers
This video from Quantum Leaps, LLC discusses state machine design for embedded systems, but the principles are universal. It presents a simple example that clearly shows how logic can be needlessly repeated across states.
Watch from 06:41 to 07:36. Notice how the logic for handling button presses needs to be implemented identically in both the 'on' and 'off' states. This is a small-scale example of the same code duplication problem.
Problem 2: Transition Explosion (The "Spaghetti FSM")
The second major problem is closely related to the first. As you add more and more states, the number of potential transitions between them can grow exponentially. Eventually, your clean state diagram starts to look like a plate of spaghetti. This is often called "transition explosion."
An FSM with this level of complexity is incredibly difficult to work with.
- Hard to understand: It's difficult to trace the logic and predict what the AI will do in a given situation.
- Hard to debug: If a bug occurs, finding the incorrect transition in this tangled web is a nightmare.
- Hard to extend: Adding a new state requires considering its connections to potentially every other state, a process that is tedious and highly error-prone.
Let's hear a concise summary of why this scalability issue caused many in the game industry to look for alternatives to simple FSMs.
The AI of Half-Life: Finite State Machines | AI 101
This video from the AI and Games YouTube channel discusses the AI of the classic game Half-Life. In this short clip, the creator explains the primary drawbacks of FSMs that led to the development of other techniques.
Watch from 04:50 to 05:27. The video explicitly names the two big problems with FSMs: they are labor-intensive to build, and they don't scale well as the number of behaviors and transitions increases.
As the video highlights, the more states you have, "the more unique transitions between states that need to be captured and in turn the more circumstances you're going to have to debug." This is the essence of transition explosion.
Conclusion
In this lesson, we've taken a critical look at the simple FSMs we've been building and identified their breaking points when faced with real-world game complexity.
Key Takeaways:
- While FSMs solve the initial problem of tangled conditional logic, complex FSMs can introduce their own maintenance problems.
- State Duplication: This occurs when you model independent concerns (e.g., action and equipment) in a single FSM, leading to a combinatorial explosion of states (
Standing,StandingWithGun,Jumping,JumpingWithGun, etc.). It also happens when multiple states share large amounts of code, leading to redundancy. - Transition Explosion: As the number of states grows, the web of possible transitions can become unmanageably complex, creating a "spaghetti FSM" that is difficult to understand, debug, and maintain.
Recognizing these patterns is a key skill for an AI developer. It allows you to know when a simple FSM is not enough and when you need to reach for a more powerful tool.
Next Lesson Preview:
Now that we have clearly defined the problems, we can start exploring the solutions. In our next lesson, we will introduce our first advanced pattern: the Hierarchical Finite State Machine (HFSM). You'll see how HFSMs directly tackle the problem of state duplication by allowing us to create "super-states" and "sub-states," enabling code reuse and bringing order back to our complex designs.