You step back into the mine, and this time you are not alone. Somewhere in the dark there is a monster, and it can hear every step you take. Each time you move, it moves. If the monster ever catches up to you, the game is over.

How do you escape a maze when the maze itself is hunting you?

Try It Yourself First

Use the arrow keys (or hjkl) to walk. The monster takes one step toward you on every move you make, always picking the shortest route through the walkable cells. There is no time pressure: you can think for as long as you like between moves. Reach the red E to escape.

You will probably get caught a few times before you find the trick. Most mazes have at least one route the monster cannot cut you off on, but finding it requires thinking two players ahead.

Setup From the Previous Notes

If you want to experiment with a different cave layout — moving walls, shifting the start, or changing the monster’s spawn — edit the prelude below. Besides S and E, the map uses an M marker for the monster’s initial cell. The game, the replay, and the prelude all read that exact spawn from MINE_MAP. The dark-violet M circle on the map marks it.

Why This Is Harder Than Shortest Path

In The Shortest Path Out of the Mine the only thing that mattered was how far each cell was from the start. Here, the monster is also moving — and it always takes the shortest path toward you. That makes its behaviour completely deterministic: given a sequence of player moves, the monster’s trajectory is fully determined. No randomness, no fog of war.

This determinism is what makes the problem tractable. Instead of reasoning about probabilities or worst-case branches, we can search for the optimal plan — the shortest sequence of player moves that reaches the exit without ever landing on the same cell as the monster.

Joint-State BFS

The key insight is to model the full situation as a single graph where each node is a pair of positions — the player’s and the monster’s:

• Nodes are pairs $(p, m)$ with $p \neq m$.
• Edges correspond to one player move in any of the four directions, followed by one deterministic monster step (BFS-shortest toward the new player position).
• Goal is any node where $p = \text{exit}$.

Running BFS on this joint graph gives us the shortest plan — the fewest player moves that reach the exit alive. It naturally discovers maneuvers like luring the monster away from the exit and then doubling back, something you cannot find by analysing each agent’s distances independently.

The joint graph has up to $W^2$ nodes (where $W$ is the number of walkable cells), so it uses more memory than plain BFS. For the small caves in these notes that is no problem; for huge mazes you would want pruning, symmetry breaking, or A* with a tailored heuristic.

What Comes Next

Once you can outrun a single, perfectly-informed monster, two natural follow-ups appear:

• Multiple monsters with different start positions — the joint state grows to a tuple of all agent positions.
• Monsters with imperfect information — for example, a monster that only sees you within a certain radius, or that wanders randomly until it spots you. Suddenly the optimal player strategy is no longer deterministic.

The next note in the series, Escaping with the Most Gold, drops the monster but adds a different kind of pressure: every step you take collapses the floor behind you, so each cell can only be visited once. The goal is no longer to escape fast, it is to escape rich.