Module 1 · Arcades and foundations

Arcade AI: state machines and greedy ghosts

How four ghosts with one tile of vision and zero pathfinding create "character" — and why arcade AI is the first case in history of classical beating ML.

~16 min

The gist in 20 seconds

The Pac-Man ghosts do not build a path. At a junction each one greedily picks the neighboring tile that minimizes the straight-line distance to its own target tile; ties are broken in the order "up → left → down", and reversing is forbidden. One tile of vision, no memory, O(1) — because 1980 hardware allowed nothing more. The "character" comes not from intelligence but from where each of them looks: Blinky aims at Pac-Man, Pinky 4 tiles ahead, Inky through a vector from Blinky, Clyde chickens out up close. On top sits a simple global state machine, Scatter ⇄ Chase ⇄ Frightened. This is greedy argmin, the direct ancestor of greedy decoding in LLMs — and a counterpoint to A* and RL.

The mechanism

A greedy choice one tile deep

Every ghost has a target tile, recomputed each frame by its personal rule. At a junction the ghost looks at the legal exits (all but a reversal) and picks the one whose center is closest in a straight line to the target. It compares the square of the distance — no square root needed:

d^{2} = {(x_{t} - x_{n})}^{2} + {(y_{t} - y_{n})}^{2}

n^{*} = \underset{n \in N}{\arg \min} d^{2}

where t is the target tile and n ranges over the neighbors N (no reversal). A tie (equal d²) is broken by a fixed direction priority — up, left, down (never right as a tie-break, and never backward). That is the whole "intelligence": no queue, no closed set, no search — one argmin over 2–3 candidates.

A junction: 3 legal exits (reversal forbidden), compute d² to the target for each, go to the minimum. That is the entire ghost.

Four targets — four "personalities"

The algorithm is the same for all of them; what differs is only the rule for computing the target tile — and out of that comes the sense of different personalities:

Blinky (red) — target = Pac-Man's current tile. Straight at you, pressing from behind.
Pinky (pink) — target = 4 tiles ahead of Pac-Man along his heading. Seems to cut you off and set ambushes.
Inky (cyan) — takes the point 2 tiles ahead of Pac-Man, draws a vector from Blinky to that point and doubles it. The target depends on Blinky's position — behavior that feels "unpredictable".
Clyde (orange) — if Pac-Man is > 8 tiles away he targets like Blinky; closer than 8 he runs to his corner (as in Scatter). Which is why he lunges in and then cowardly peels off.

The famous bug is baked into the hardware: when Pac-Man faces up, an overflow in the 8-bit arithmetic makes Pinky target not "4 up" but 4 up AND 4 left; Inky inherits the same offset in his "2 ahead" point. Namco never fixed the bug — it added an angle of attack, and it stayed canon.

The global state machine: Scatter / Chase / Frightened

On top of the individual targeting runs a shared finite state machine on a timer:

Chase — target by the personal rule (above). Lasts ~20 s.
Scatter — target = the ghost's fixed home corner; everyone scatters, giving you a breather. The first phases are ~7 s.
Frightened — after an energizer is eaten: the ghosts reverse, turn blue, slow down and take pseudo-random turns at junctions (direction from a PRNG). The Scatter/Chase timer is paused for the duration and resumes afterward.

The game alternates Scatter→Chase a few times (7/20/7/20/5/20…), and after that it is Chase almost forever. Every mode change forces the ghosts to reverse — which is both anti-looping and an honest telegraph to the player: see a reversal, the mode has changed.

One small FSM for everyone + a personal targeting rule for each. A mode change = a forced reversal.

A worked example. Blinky is in a tile, target = Pac-Man at (25,4). Three exits: up (22,5), left (21,6), down (22,7). Compute d²: up (25−22)²+(4−5)² = 9+1 = 10; left 16+4 = 20; down 9+9 = 18. The minimum is up (10). Had up and down been equal, up would win by tie-break. One pass over three candidates, zero search.

🕹 Games to play — and what to notice

From "AI in two lines" to four ghosts with emergent character. For each: how it was done and what to provoke to see the state machine with your hands. From reactive tracking to greedy targeting.

Pong 1972 · a reactive machine in 2 lines

The AI paddle simply reaches toward the ball along Y: if ball.y > paddle.y: move down else up. No prediction, no plan. Which gives it an honest hole: serve the ball so it reaches the edge faster than the paddle can travel and it physically cannot make it. "AI" that fits entirely into one comparison.

🎮 Play: in Pong, hit sharply on the diagonal toward the far edge — you'll see the opponent fail to arrive. That is not "difficulty" but the ceiling of reactive tracking with no lead.

Space Invaders 1978 · determinism + pseudo-randomness

The formation of aliens moves on a rigid deterministic pattern (left-right-down), but the shots come from a simple deterministic PRNG (pseudo-randomness from a seed). And the speed-up as the enemies thin out was originally an artifact (fewer sprites → less work per frame → a faster loop), kept as a tension-building feature.

🎮 Play: notice how the music tempo and the movement speed up when few aliens are left. That isn't "adaptive difficulty" design but an old loop that literally runs faster under a lighter load.

Pac-Man 1980 · 4 greedy targeters + an FSM

All the theory above is this game. Four identical greedy machines with different targeting rules + the global Scatter/Chase/Frightened. Emergent "character" without a single line about personality: it lives entirely in the choice of target tile.

🎮 Play: corner the ghosts — at junctions they split into different directions (each has its own target). Tease Clyde: walk right up to him and he peels off (8 tiles), back away and he lunges in. Turn upward and watch Pinky and Inky miss you (the overflow bug).

Deep end · design: why minimal rules yield maximal "character"skippable

Pac-Man is the textbook case of emergence: complex behavior out of simple rules. Why this works better than "smart" AI:

Legibility beats optimality

A perfect pursuer (real A* to the player) would be unfair and illegible: the player doesn't understand the logic and can't play around it. Greedy targeting with different goals is predictable enough to read and asymmetric enough to keep the tension. Blinky presses from behind, Pinky cuts you off in front — together they "pin" you, though each is dumb.

Scatter — a designed breather

Without the Scatter phases four pursuers would clump into one lethal blob. Periodically scattering to the corners is a design pressure valve: it opens windows to get through and breaks up the clumping. Clyde the coward does the same thing locally: he creates a safe zone near his corner.

Determinism as depth — and its price

Full determinism let experts learn patterns (fixed routes that kill a level). That is both mastery depth and a longevity problem: a memorized pattern kills replayability. Which is why Championship Edition and the later remakes added randomization — a deliberate trade of "legibility/mastery" against "unpredictability/longevity".

Deep end · engineering: the cost in cycles, and why NOT pathfindingskippable

The budget. On an 8080/Z80 at ~2–3 MHz with dozens of sprites, pathfinding (BFS/A*) for each of 4 ghosts every frame is an unaffordable luxury. A greedy choice is 2–3 subtractions and comparisons per ghost per junction, O(1). It is enough for the gameplay because the maze itself channels the movement: corridors don't let greediness get stuck.
A common myth (present in our own source too): "the ghosts run BFS". They don't. There is no path construction — only a local argmin over neighbors. That matters conceptually: "character" arises without search and without memory.
The reversal ban is not style but protection against oscillation: allow reversals and a ghost will lock up, twitching back and forth at a local minimum. Reversing is allowed only as a forced signal on a mode change.
8-bit thrift backfires. The same class of "cheap but overflows" that gave us the Pinky bug produces the famous kill screen at level 256: the 8-bit level counter overflows and half the screen turns to garbage. The price of maximally cheap arithmetic.
When greed isn't enough. In open space (not corridors) greedy targeting gets stuck on concave obstacles — that is where real A* is needed (see the pathfinding lesson). An arcade maze doesn't need it — the topology does the algorithm's work.

Analogy

Four hunters, each able to do exactly one thing: look at their own landmark and step toward it. No map, no plan, no negotiation. But their landmarks differ — one looks straight at the prey, another at where it will be, a third at a reflection through a teammate. Add three dumb gazes together and they pin you. The "personality" is not in the hunter's mind but in where he has been trained to look.

Why it matters

This is the first and purest lesson: rich behavior does not require search or learning — sometimes a local greedy rule is enough, and it is even better, because it is cheap, deterministic and legible to the player. Knowing where greed suffices and where it fails (open space → A*, dynamics without a model → RL) is exactly the engineering judgment of "don't reach for the expensive tool while the cheap one fundamentally holds". Arcade AI is the zero point of a scale whose other end is AlphaStar.

🔁 Beyond games — where this transfers

The lesson gives you three transferable moves: a greedy local choice instead of a global search, emergence out of simple rules and a finite state machine as the skeleton of behavior.

ML / AI (your domain): a greedy argmin over neighbors is literally greedy decoding (take the most probable token with no search); beam search and MCTS (AlphaGo) are what starts when greed isn't enough. "Ghosts vs A*" = "greedy decode vs search". A reactive targeter with no memory is a policy without planning (model-free), and Scatter/Chase/Frightened is early hierarchical/options RL: switchable sub-policies. Determinism = a reproducible eval.

Systems: greedy heuristics are everywhere — least-loaded balancing, greedy cache eviction, nearest-server routing; finite state machines are workflow and protocol engines, resource lifecycles.

Robotics / control: reactive architectures (Braitenberg, Brooks's subsumption) versus deliberative planning — the same trade of "cheap and now" against "expensive and optimal".

The principle: minimal local rules can produce rich global behavior. Start greedy/reactive; escalate to search or learning only where the local approach demonstrably fails.

🔧 Run it and poke at it — on your home machine

What to play is above (🕹). Here — see the targeting and the FSM live:

🔧 Poke at it (debug) ~40 min, emulator / Pac-Man Dossier

Get a Pac-Man emulator with a target-tile overlay (such builds and mods show colored target tile markers for every ghost) or the write-up on pacman-dossier. Watch Pinky's marker jump 4 tiles ahead, watch Inky's depend on Blinky, and watch Pinky's marker slide left when you face up (the bug). Time the phases: catch the moments when all the ghosts reverse at once — that is the Scatter↔Chase switch.

🧪 Test it (QA eyes) ~15 min

Check the state machine at the seams: is the forced reverse there on exactly every mode change? Does Clyde switch precisely at 8 tiles (not gradually)? In Frightened are the directions really pseudo-random, and is the Scatter/Chase timer paused (after the fright the same mode returns)? This is the standard "FSM states and transitions" checklist.

Checklist: saw four different target tiles; caught Pinky's "facing up" bug; confirmed the forced reverse on a mode change.

Connections

foundation

The game loop — deterministic fixed ticks make the ghosts' behavior repeatable, hence the learnable clearing patterns.

contrast

Pathfinding: A* and NavMesh — greedy targeting is "pathfinding with no path"; A* is what you need once the maze stops channeling movement.

FSM and Behavior Trees — Scatter/Chase/Frightened is the textbook finite state machine; BTs are the next step in scaling behavior.

Questions worth asking

I keep hearing "the ghosts use BFS/pathfinding". Is that true?

No — and it is a common myth (it is even in our own source write-up). There is no path construction: at a junction each ghost makes a greedy local choice — the argmin of straight-line distance to its target tile over 2–3 neighbors, with no queue, no closed set and no memory. The "pinning" behavior is an emergent consequence of different targets, not the result of a search. Understanding this matters: a rich result was obtained without an expensive algorithm.

Why is reversing forbidden, yet a mode change forces it?

The ban is anti-oscillation: allow reversing and a ghost will twitch back and forth at a local minimum and hang. So normally there is no going back. But on a Scatter↔Chase switch the target jumps, and a single forced reversal serves two purposes: it instantly redirects the pack toward the new target and telegraphs the mode change to the player (see a synchronized reversal — the phase has changed). The exception is designed as a signal.

Pinky's bug (facing up → the target also shifts left) — does it make her worse?

It changes her rather than breaks her. Because of the overflow, "4 ahead" while facing up becomes "4 up and 4 left", so Pinky's ambush shifts diagonally. Namco did not fix the bug: it added non-obvious interception angles and broke nothing. The classic case of a hardware defect becoming part of the "character" — and why blindly scrubbing every anomaly is harmful.

Greed works in a maze — why does it fail in an open field?

In corridors the topology does the leading: there are few choices, a dead end is cut off quickly, and the local minimum almost always coincides with the right move. In open space with a concave obstacle, greed drives the agent into a "pocket" (the step toward the goal runs into a wall, and going around means temporarily increasing the distance, which greed won't do) → it gets stuck. There you need a search that accounts for cost so far — A*. So the sufficiency of greed is a property of the map, not the algorithm.

Determinism produces learnable patterns — bug or feature?

Both; it is a trade. Full determinism gave experts patterns — memorized routes that clear a level on autopilot: enormous mastery depth. But it also kills replayability once the pattern is learned. Which is why Championship Edition and the remakes injected randomization. The same choice faces any AI opponent: predictability (legibility, mastery) against variety (longevity, fairness).