State Machines

A game is never doing just one thing. It shows a title screen, runs an attract mode, plays a level, pauses, plays a death animation, shows the high scores, and starts again. A state machine handles this with one variable that records which of those things is happening now, a separate piece of code for each, and a small set of rules for moving between them. Each frame the program looks at the variable and runs the code for that state, and nothing else.

The alternative is a main loop full of flags (if paused, if dying, if not game_over) that every routine has to check, and that grows more tangled with each feature. A state machine trades that for a single question asked once a frame: what are we doing?

The pattern

states: TITLE, PLAYING, PAUSED, GAMEOVER

each frame:
    look at current_state
        TITLE:    run the title screen
        PLAYING:  run the game
        PAUSED:   wait for the unpause key
        GAMEOVER: show the score, count down, go back to TITLE

Each state decides for itself when to hand over. The title screen changes the variable to PLAYING when the player presses fire; the game changes it to GAMEOVER when the last life is lost. The other states never need to know.

A state machine in an arcade game

Pac-Man’s ghosts are the best-known state machine in arcade games. Each ghost is always in one of three modes: chasing the player, scattering to its own corner of the maze, or frightened after the player eats a power pellet. Each mode has its own rule for choosing a direction at a junction (Ghost AI gives the details), and a timer or an event moves the ghosts between them.

The scatter mode exists for the player’s sake. Toru Iwatani explained in 1986 that “when a human being is constantly under attack like this, he becomes discouraged”, so his team “developed the wave-patterned attack-attack then disperse; as time goes by the ghosts regroup and attack again.” The transitions are visible on screen. Jamey Pittman’s analysis of the arcade program found that the ghosts are “forced to reverse direction by the system anytime the mode changes” between chasing, scattering and being frightened, though not when they recover from being frightened. A sharp-eyed player can see the state change as the whole pack turns round.

On an 8-bit machine

In assembly language the state is a single byte, and the states are numbered from zero.

STATE_TITLE    = 0
STATE_PLAYING  = 1
STATE_PAUSED   = 2
STATE_GAMEOVER = 3

game_state:    !byte STATE_TITLE

Choosing the code to run

A common 6502 dispatcher uses the state as an index into a table of addresses. Each address takes two bytes, so the state is doubled first. This version writes the address into the operand of a JMP instruction, which works because the program runs from RAM:

update_game:
    lda game_state
    asl                 ; two bytes per address
    tax
    lda state_table,x
    sta jump+1          ; rewrite the JMP's operand...
    lda state_table+1,x
    sta jump+2
jump:
    jmp $0000           ; ...and jump to the state's routine

state_table:
    !word update_title
    !word update_playing
    !word update_paused
    !word update_gameover

Called with JSR update_game, the state’s own routine ends with RTS and returns straight to the main loop. For a handful of states, a chain of comparisons is easier to read and nearly as fast:

update_game:
    lda game_state
    cmp #STATE_TITLE
    beq update_title
    cmp #STATE_PLAYING
    beq update_playing
    cmp #STATE_PAUSED
    beq update_paused
    jmp update_gameover

The branches only reach 127 bytes forward, so the state routines have to sit close by, or the chain has to jump to them instead.

Changing state

A transition is a write to game_state, plus whatever the new state needs setting up. A state that should last a fixed time keeps its own timer:

; show GAME OVER for three seconds, then go back to the title screen
trigger_gameover:
    lda #STATE_GAMEOVER
    sta game_state
    lda #150            ; 3 seconds at 50 frames a second
    sta state_timer
    rts

update_gameover:
    dec state_timer
    bne .still_showing
    lda #STATE_TITLE
    sta game_state
.still_showing:
    rts

As a game grows, it helps to give every state an enter routine and an exit routine, and to change state in one place only. The caller passes the new state in A; the routine keeps it on the stack while the old state tidies up, so the exit routine is free to use any register:

; call with the new state in A
change_state:
    pha                 ; keep the new state
    jsr exit_state      ; game_state still holds the old one
    pla
    sta game_state
    jmp enter_state     ; its RTS returns to our caller

enter_state:
    lda game_state
    cmp #STATE_PLAYING
    bne .not_playing
    jsr init_level      ; set up the level only when play begins
.not_playing:
    rts

Smaller machines inside the big one

The same shape turns up inside a state. The player in PLAYING may be standing, walking, jumping or dying, each with its own byte and its own routines. A sprite’s animation is a tiny state machine too: the state is the frame number, and the transition is a timer running out.

update_animation:
    dec anim_timer
    bne .no_change
    inc anim_frame      ; next frame...
    lda anim_frame
    cmp #4
    bcc .not_wrap
    lda #0              ; ...back to the first after the fourth
    sta anim_frame
.not_wrap:
    lda #6              ; frames per animation step
    sta anim_timer
.no_change:
    rts

The listings are in ACME syntax. They were assembled with ACME and run in the VICE emulator inside a test program that called each routine and checked the result: every state reached by both dispatchers, the game-over screen lasting exactly 150 calls, the exit and enter routines seeing the old and new states, and the animation wrapping from the fourth frame to the first.

What period programmers wrote

C64 programmers rarely used the term, but the idea is all through their own accounts.

Jeff Minter’s diary of Iridis Alpha in ZZAP!64 in August 1986 describes ACONT, “essentially an interpreter for my own wave language, allowing me to describe, exactly, an attack wave in about 50 bytes of data”. His reason was memory: “It’s impractical to write separate bits of code for each wave; even with 64K you can run outta memory pretty fast that way.” One routine stepped through each wave’s data, so what made one wave different from another was the data, not the code. Many table-driven state machines work the same way.

Lasse Öörni, who writes as Cadaver and whose games include the Metal Warrior series, gave game objects two states in an article on building a scrolling game world. Objects near the screen are “actors”, run every frame; the rest are “leveldata”, which “basically stores their positions and actor types, possibly hitpoints, but not any other information”. Each frame he checks part of the leveldata, “for example 16 objects”, and promotes any that have come within a rectangle a little larger than the screen. Actors that leave it go back to being leveldata, though “in some special cases objects are never removed (the player actor!)”.

Hannu Nuotio’s C64 game Pallo (2006), published in source on the Codebase64 wiki, writes its states down in the header. Its interrupt routine has “Interrupt states”: state $01 updates the random numbers and checks for collisions, then sets the next state to $02, $40, $80 or $C0 according to what was hit, and state $02 moves the sprites and sets the state back to $01. The main loop has three “Gameloop states” of its own, which read the joystick, count down timers and deal with whatever collision the interrupt reported.

Bigger state machines

A flat list of states starts to strain when a character can do several things at once, such as running while charging an attack while taking damage. In 1987 the computer scientist David Harel published statecharts, a notation that nests states inside other states, so that WALKING and RUNNING can share everything that belongs to their parent, MOVING. On an 8-bit machine the same idea often appears as nested dispatchers, or as one byte whose high four bits hold the outer state and whose low four bits hold the inner one.

Later games kept the idea and changed its shape. Damian Isla described the AI of Halo 2 in 2005 as “a hierarchical finite state machine (HFSM) or a behavior tree”, in which a behaviour could sit in several places in the hierarchy at once. At the next year’s Game Developers Conference, Jeff Orkin of Monolith said that “nearly every game that exhibits any A.I. at all uses some form of an FSM to control character behavior”, and then explained why F.E.A.R.’s did not do the deciding. Its state machine “has only three states”, named Goto, Animate and UseSmartObject. A planner chose the sequence of actions, and the state machine just carried them out.

See also

• Game Loop
• Ghost AI
• Sprite Animation
• Frame Animation
• Jeff Minter
• Game State Machine pattern