5 min read

Stack-based State Machine

Stack-based State Machine

Since the beginning we understood the crucial role of code structure of handling characters for the quality of our game development process. If adding anything over time becomes more time-consuming than anticipated, it can cause growing frustration. So naturally, we wanted to avoid that. Being proactive in this area has been one of our better decisions. We closely monitored how the code complexity increased with additional character behaviours, and this led us to iterate over several designs over a few weeks.

During our game design meetings, we agreed that each character, whether a hero or enemy, should be able to handle a distinct set of behaviours and interactions. Assumptions like "all characters must move" were too general for us. We also recognized that a character's behaviour is not always determined by the player. A character can get stunned, knocked back, or even die. When a character dies, it's expected that it can no longer receive damage and become "more dead" than it already is. From these and other observations, we decided to operate on the concept of a Finite State Machine.

Let's illustrate this with a scenario: a player sees an enemy goblin walking in the distance. As the player moves closer, the goblin notices and starts to chase him, attacking when close enough until the hero dies. The goblin's actions change depending on certain conditions. If there's no one to attack, it patrols the area. If someone is nearby, it closes the distance. If it can hit, it attacks. So, the goblin is always in some state doing some actions and can transition to other states depending on the conditions that occur.

Goblin finite state machine

We were already familiar with the programming design pattern called State, which naturally led us to design around it. After several iterations, we arrived at our current design, which we call a Stack-based Finite State Machine.

Behaviours

To better understand this, let's examine some behaviours we wanted to handle in our game. For easier visualization of state transitions, we used a timeline with each state represented as a separate box. This shows that only one state is active at any given time. "Active" here means it's controlling the character. The fact that we also can use a state machine to handle effects like buffs or modifiers will be a topic for another blog post.

Representation of states. Only one active at any given time.

We identified several scenarios that we wanted to handle in a particular way. Let's go through the most interesting ones, first by modelling how we would like the system to behave, then discussing the solution.

General Actions

A significant part of our game involves what we call actions. An action can be started (e.g., from player input), take some time, and then return control to the default state. What's common for actions is that they can be interrupted or canceled (eg. when character gets hit while in the middle of some action).

Execution of general actions.

Control Effects and Interrupts

We also wanted to apply control effects like stuns or knockbacks. These effects remove control in some way (e.g., the player cannot move or attack) and can stack (as opposed to cancel each other).

Stacking of stun effects. We want to return control after all stuns expire.
Stacking of control effects. We want to be able to knock back stunned character but also make sure it's under control effects for correct time period.

Moreover, we didn't want to remove control any longer than necessary. For example, if you're knocked back while attacking, control should be regained after the control effect expires, not after the attack would have finished.

Long Lived States

Although we assumed that the default state (usually some form of movement or idle state) would be the fallback when all actions finish, we also wanted to handle cases where there's no fixed time interval when it should be active.

Imagine a scenario where you want to pick up a box and then throw it. By default, you're just running (default state), then you execute a "try pick up" action, which can either return you back to the default state, or if there's a box nearby, switch you to a "holding object state". This allows for clear separation of behaviours and easy modification of them.

How it works

To better understand the structure of a stack-based state machine, let's take a look at the main parts separately: the state lifecycle and the state manager. The state lifecycle describes what each state might go through, while the state manager causes the change between states and ensures each state gets notified appropriately.

State Lifecycle

In the state lifecycle, each state should have the following methods:

  • Start() is called when the state begins execution.
  • Pause() is called when the current running state is paused, meaning another state should be actively run.
  • Resume() is called when another state finishes, and this one can resume execution
  • Finish() signals to the state manager that this state is finished and can be removed from the stack.
General state lifecycle

State Manager

In the state manager, pushing a new state first pauses the current running state, adds a new one at the top of the stack, and starts it. When removing a state from the stack, we need to consider whether the removed state is the one currently running or is somewhere in the middle of the stack. If it's at the top, we need to resume the state that is below it.

Summary

We've discussed our journey in designing a Stack-based Finite State Machine for our game development process. We identified that managing character behaviors is crucial in creating a smooth and enjoyable gaming experience. We explored the concept of a Finite State Machine, which allowed us to structure our code in a way that each character state and behavior could be efficiently managed. This enabled us to handle multiple scenarios, including actions, control effects, interrupts, and long-lived states.

Through careful observation and multiple iterations, we developed a system that could handle complex character behaviours without compromising the quality of our game development process. The design of a state lifecycle and state manager played a significant role in achieving this.

In conclusion, the journey towards creating a Stack-based Finite State Machine was not without its challenges. However, it was an essential step in ensuring our game characters behaved as expected and in improving the overall gaming experience. This process taught us the importance of careful planning, proactive decision-making, and iterative design in game development. We hope that our experiences can provide valuable insights for other developers facing similar challenges.