Table of Contents
My games are too simple to deserve “architecture”. But the point of this project is to play with designs I might use someday. One such design is game states.
A state is a mode of being. The game exists differently depending on what’s happening. Title screen? That’s a state. Playing a level? State. Paused? Also a state. Each needs different logic, different drawing, different input handling. The title screen doesn’t care about physics. The pause menu doesn’t animate enemies. The level doesn’t render “Press Start.”
States are usually organized as stacks.
Sometimes they combine. In Mario, pausing freezes the world entirely, allowing the player to set down their Game Boy and attend to matters in the physical universe. Elden Ring, by contrast, continues its enthusiastic attempts to kill you while you’re reading what a Smithing Stone does. Both approaches are valid. One of them is hostile.
State of the Art
So, a stack. The data structure where things can only enter or leave from the top.
Picture Shovel Knight. You run the game. An asset manager loads resources while company logos appear on screen. Call this the system state:
┌────────┐ │ system │ ← Active └────────┘The loop runs, checking if logos have displayed for their contractually obligated durations and if assets are loaded. system also initializes the window, audio channels, and whatnots. This happens once. Then: title screen.
We push this new state onto system:
┌────────┐ │ title │ ← Active ┌────────┐ ├────────┤ │ system │ ← Active │ system │ └────────┘ └────────┘
Before ───► AfterWhy keep system? It still manages global resources. Audio, for instance, needs someone to keep feeding it things to play.
After the push, system becomes inactive, title becomes active.
Fast forward. Player passed level selection (world), played a bit (level), and encountered a boss. The boss, naturally, wishes to speak at length about matters that could have been an email.
┌────────┐ │ dialog │ ← Active ├────────┤ │ level │ ├────────┤ │ world │ ├────────┤ │ system │ └────────┘Each state has its job. Jobs differ when active versus inactive.
If level were active, it would move the avatar, handle inputs, animate enemies, and generally conduct the business of being a video game. Here it just renders the frozen world while your archenemy explains, in considerable detail, the backstory of their sword.
Popping works in reverse. Player finishes or quits. The top states are destroyed, and whoever’s now on top becomes active:
┌────────┐ │ dialog │ ← Active ├────────┤ │ level │ ├────────┤ ┌────────┐ │ world │ │ world │ ← Active ├────────┤ ├────────┤ │ system │ │ system │ └────────┘ └────────┘
Before ───► AfterSo how does the loop use this? Every frame, it walks bottom to top, calling step() on each state. The catch: behavior differs based on position.
for state in stack: if state == stack.top(): state.step_active() else: state.step_inactive()step_active() speaks to the player. It handles input, makes decisions, reacts. It’s having a conversation.
step_inactive() does vital work that the player never notices. Audio buffers get pumped. Backgrounds get rendered. The system state keeps music playing. The level state draws frozen scenery behind the dialog. Essential, invisible, thankless. Like the bass player during a guitar solo.
This is why the stack is useful. Without it, you’d write conditionals like: “if there’s a dialog, don’t move the player, but do keep drawing, unless we’re in a cutscene, in which case…” and so on, forever, until the heat death of the universe or your resignation letter, whichever comes first.
The stack exists because developers tried the alternative of not using one and didn’t enjoy it. It has since saved countless debugging hours and, by some accounts, at least one marriage.
One more thing. States often need to react to transitions. When level becomes active, it might unpause the music. When pause enters, it might dim the screen. These hooks (enter, exit, pause, resume) are useful. We’ll get to them.
State of Decay
Now, how do you actually implement this? An array, a loop, push and pop. Simple enough. But there’s a problem to solve.
The loop traverses the stack. States want to modify the stack while you’re walking through it.
Player presses Escape: level wants to push pause.
Player dies: level wants to pop itself and push game_over.
Dialog ends: dialog wants to remove itself.
All valid requests. All made at the worst possible moment. This is not a coincidence. This is programming.
Consider:
for state in stack: state.update() # state calls stack.push() or stack.pop() # iterator: "excuse me what"Modifying a collection while iterating through it is, as they say, “undefined behavior.” Some programs throw exceptions. Some corrupt memory silently. Some continue running purely to prove a point.
Solutions exist. Some are even good.
You could lock the stack during iteration. Simply forbid modifications. This approach has the elegant simplicity of solving a problem by making it illegal. It also ignores a fundamental truth: the universe has arranged things so that traversal is precisely when states most want to change. Banning this is like banning hunger during dinner. You can do it. It won’t help.
You could use two stacks. Read from one, write to the other, swap at the end of the frame. Double-buffering. This works well, but requires keeping two stacks in sync.
Or we make the stack safe to edit.
Linked-List Approach
So, let’s keep the stack. But as a linked list. Don’t leave. I promise this one has a purpose.
First, here is our state, a set of callback functions, each for a specific purpose:
struct state { action_fn active; // Called each frame when state is top of the stack action_fn inactive; // Called each frame when state is not top of stack
action_fn enter; // Called once when state is pushed onto the stack action_fn exit; // Called once when state is popped from the stack
action_fn pause; // Called once when state is not top-most element anymore action_fn resume; // Called once when state becomes top-most element back};When a state is pushed onto the stack, whatever was on top is called its pause() callback.
Then we call enter() from the new state.
From then on, each frame will go through all steps from bottom to top, calling inactive() for each, with the exception of the top-most on which we call active().
action_fn can be any signature you need for the sake of your game.
Here, we will use:
typedef void (*action_fn)(struct state_chain* chain, void* env, void* data);chain is explained further in this section.
env points to any custom data shared by all states within the frame.
data points to any custom data given to a specific state.
The stack itself, will be a linked list. But hear me out! Each state will actually hold a link to the previous state, not the following one.
┌────────┐ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ ← │ level │ ← │ pause │ └────────┘ └───────┘ └───────┘ └───────┘ └───────┘ ActiveImplementation
So, here’s our “stack element” structure. A state, a pointer to its parent, and some data. Three fields. If this feels too simple, you’re right.
struct state_ref { struct state state; struct state_ref* parent; void* data;};Finally, our last structure will be a container for the stack itself. Normally, a linked list doesn’t need one, for the first element of the list is the only thing needed to represent the entire collection. But here, we will need two pointers:
struct state_chain { struct state_ref* head; struct state_ref* staging;};Why two pointers? One knows where we are. The other knows where we’ll be. They disagree often. This is normal.
head represents the active state for the current frame. staging accumulates the pushes and pops that happen during traversal.
Because we are recursively traversing the collection from the last element, modifying it from staging will keep our traversal safe.
So what will the update function look like? It’s probably the simplest function of this post:
void step_state(struct state_chain* chain, struct state_ref* state_ref, bool active, void* env) { if (state_ref->parent) { step_state(chain, state_ref->parent, false, env); } action_fn fn = active ? state_ref->state.active : state_ref->state.inactive; if (fn) { fn(chain, env, state_ref->data); }}
void step_chain(struct state_chain* chain, void* env) { if (chain->head) { step_state(chain, chain->head, true, env); }}step_state() recursively calls itself on each state until it reaches the bottom of the bucket.
At that moment, it calls inactive() or active() while going back up.
The active parameter controls this choice, which is easily set to “always false except the first time”.
step_chain() takes care of making the first call:
custom_data data = { ... };
step_chain(&chain, &data);Now, editing the stack itself is the fun part and the reason we need two heads.
When modifying the stack (by adding or removing states), we don’t edit head, but staging.
The latter can be interpreted as “what head look like on next frame?”.
Then, before the next frame starts, we “commit” the stack, roughly by setting head to whatever staging is.
Adding New States
Pushing is simple. This should worry you. It worried me. But no, it’s actually just simple. These moments are rare. Enjoy it.
void state_push(struct state_chain* chain, struct state state, void* data) { assert(chain);
struct state_ref* new_ref = malloc(sizeof(struct state_ref)); new_ref->state = state; new_ref->parent = chain->staging; new_ref->data = data;
chain->staging = new_ref;}When pushing, a new state_ref is created and the staging head is set to this value.
Note that the current head isn’t involved at all in this process.
When new states are pushed while the update is already traversing the chain, this has no impact and the additional state(s) do not parasite the current traversal:
Pushing two states at once goes from this:
┌────────┐ ┌───────┐ Ø ← │ system │ ← │ title │ └────────┘ └───────┘ head staging… to this:
┌────────┐ ┌───────┐ ┌───────┐ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ ← │ level │ └────────┘ └───────┘ └───────┘ └───────┘ head stagingAfter the two pushes, staging points to the future stack.
It’s also interesting to see that every state in the ]head;staging] range just entered the stack, meaning we should call their enter() function.
This operation is deferred to when head and staging are resynced.
Removing States
Popping from the stack works similar, but with a bit more attention.
Removing two states from the stack is similar to pushing them: we edit the staging pointer.
Before:
┌────────┐ ┌───────┐ ┌───────┐ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ ← │ level │ └────────┘ └───────┘ └───────┘ └───────┘ head stagingAfter:
┌────────┐ ┌───────┐ ┌───────┐ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ ← │ level │ └────────┘ └───────┘ └───────┘ └───────┘ staging headAnd now, ]staging;head] represents the range of states to call exit() on, then delete.
Like for enter(), this operation is deferred to when we synchronize head and staging.
Now, let’s consider we pop a state that has just been pushed, before no synchronisation happens. For example, we first push two new stages like before:
┌────────┐ ┌───────┐ Ø ← │ system │ ← │ title │ └────────┘ └───────┘ head staging ┌────────┐ ┌───────┐ ┌───────┐ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ ← │ level │ └────────┘ └───────┘ └───────┘ └───────┘ head stagingThen, we pop a single state:
┌────────┐ ┌───────┐ ┌───────┐ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ ← │ level │ └────────┘ └───────┘ └───────┘ └───────┘ head staginglevel cannot be reached, nor by head neither by staging.
And since it was just added, we will not call any of its callbacks.
As such, it’s destroyed immediately. Without triggering its enter() or exit() functions:
│ ┌────────┐ ┌───────┐ ┌───────┐ │ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ │ Ø ← │ level │ → free() └────────┘ └───────┘ └───────┘ │ └───────┘ head staging │level never ran. Its enter() function waited for a call that never came. This is not a tragedy. This is memory management. They are sometimes the same thing.
Now we have it all, here is the pop function:
void state_pop(struct state_chain* chain) { assert(chain->staging != 0);
struct state_ref* old_ref = chain->staging; chain->staging = old_ref->parent;
if(state_in_chain(old_ref, chain->head) == false) { free(old_ref); }}state_in_chain() is a convenience function that checks whether a given state can be reached from another.
This is provided as another function because we will be using it later on:
bool state_in_chain(const struct state_ref* needle, const struct state_ref* haystack) { for (; haystack != 0; haystack = haystack->parent) { if (haystack == needle) { return true; } } return false;}Commit
Now, the “commit” function. This is called at the beginning of each frame and reconciles head with staging. It must:
- Call
exit()for removed states, from top to bottom, and free them. - Call
enter()for new states, from bottom to top. - Call
pause()on any state that gets buried under a new one. - Call
resume()on any state that becomes the new top. - Finally, set
headtostaging.
The function processes one state at a time. Each step must decide: are we advancing or retreating?
Four cases determine this:
bool should_retreat;
if (chain->head == 0) { should_retreat = false; // Stack was empty, can only advance} else if (chain->staging == 0) { should_retreat = true; // Stack will be empty, can only retreat} else if (state_in_chain(chain->staging, chain->head)) { should_retreat = true; // staging is ancestor of head: retreat toward it} else if (state_in_chain(chain->head, chain->staging)) { should_retreat = false; // head is ancestor of staging: advance toward it} else { should_retreat = true; // Diverged: retreat to common ancestor first}The last case handles an edge scenario: what if states were both pushed and popped before commit? The chains diverge. We retreat to the common ancestor, then advance toward staging.
┌────────┐ ┌───────┐ ┌───────┐ Ø ← │ system │ ← │ title │ ← │ world │ └────────┘ └───────┘ └───────┘ │ ↑ │ head ▼ ┌─────────┐ ┌───────┐ │ options │ ← │ audio │ └─────────┘ └───────┘ stagingHere, the player quit the game (world) and opened settings instead. We exit world, then enter options and audio. The function handles this by retreating first until it can advance.
When retreating, we exit the current head, free it, and resume whatever’s beneath:
if (should_retreat) { struct state_ref* to_exit = chain->head; chain->head = to_exit->parent;
if (to_exit->state.exit) { to_exit->state.exit(chain, env, to_exit->data); } free(to_exit);
if (chain->head && chain->head->state.resume) { chain->head->state.resume(chain, env, chain->head->data); }}Note that resume() is called even if this state will be exited on the next iteration. This is intentional. Each state gets its moment as the active head, however brief. A state might use resume() to check conditions and immediately request another retreat. The system doesn’t skip steps.
When advancing, we find the next state to add (the one directly above current head), pause the current head, and enter the new one:
else { // Find the state one level above current head struct state_ref* to_enter = chain->staging; while (to_enter->parent != chain->head) { to_enter = to_enter->parent; }
if (chain->head && chain->head->state.pause) { chain->head->state.pause(chain, env, chain->head->data); }
if (to_enter->state.enter) { to_enter->state.enter(chain, env, to_enter->data); }
chain->head = to_enter;}Again, pause() is called even if this state was just entered. Advancing through multiple states means each intermediate state experiences enter() then pause() in sequence. This is correct. A state that enters and immediately gets buried should know about both events.
Now, wait. What if enter() pushes another state? What if exit() pops one? What if resume() decides the game is over and clears the entire stack?
This is why we loop. After each transition, head moves, but staging might have moved too. We keep processing until they agree:
while (chain->head != chain->staging) { // Process one state transition}The condition is checked after every advance or retreat. If a callback modified staging, we simply continue. The same logic applies: determine direction, process one state, repeat. The stack remains consistent because we never skip steps, and we never assume staging stayed where we left it.
Here is the complete function:
static void commit_chain(struct state_chain* chain, void* env) { while (chain->head != chain->staging) { bool should_retreat;
if (chain->head == 0) { should_retreat = false; // Stack was empty, can only advance } else if (chain->staging == 0) { should_retreat = true; // Stack will be empty, can only retreat } else if (state_in_chain(chain->staging, chain->head)) { should_retreat = true; // staging is ancestor of head } else if (state_in_chain(chain->head, chain->staging)) { should_retreat = false; // head is ancestor of staging } else { should_retreat = true; // Diverged: retreat to common ancestor first }
if (should_retreat) { struct state_ref* to_exit = chain->head; chain->head = to_exit->parent;
if (to_exit->state.exit) { to_exit->state.exit(chain, env, to_exit->data); } free(to_exit);
if (chain->head && chain->head->state.resume) { chain->head->state.resume(chain, env, chain->head->data); } } else { struct state_ref* to_enter = chain->staging; while (to_enter->parent != chain->head) { to_enter = to_enter->parent; }
if (chain->head && chain->head->state.pause) { chain->head->state.pause(chain, env, chain->head->data); }
if (to_enter->state.enter) { to_enter->state.enter(chain, env, to_enter->data); }
chain->head = to_enter; } }}Conclusion
What we built: a linked list pretending to be a stack, with two heads that occasionally disagree. States enter and exit. Callbacks fire in the right order. The system tolerates modifications during traversal because it never assumes the ground beneath it is stable.
The code presented here is minimal. A production version might add:
- State names, for when you need to ask “what is even happening right now?”
- Loop detection, in case a state decides to push forever (they sometimes do, for reasons they refuse to explain)
- Memory pooling, because
mallocin a hot loop is how you make your CPU cry - Better cache behavior.
Could I have just used an enum and a switch? Probably. But then I wouldn’t have learned anything, and you wouldn’t have anything to read. We both made choices today.