Snake Path Planning Lab (2D)

Can a snake fill the whole board without ever crashing? A Hamiltonian loop, cycle shortcuts, BFS with a tail check, unsafe BFS, greedy chasing, or you at the controls.

Presets

Playback

Strategy

Pick who drives the snake. Shortcut settings apply to "Cycle + safe shortcuts".

Board and speed

The loop needs an even side length. Same seed = same apple sequence.

Layers

Model checks

The science

Hamiltonian cycle

A closed path through every cell of the N x N grid exactly once. It exists when N is even: run along the top row, weave through columns 1..N-1, return up column 0. A head that always steps to the next cell of the loop only enters cells the body has already left, so it can never collide with itself.

Expected cost

With length L the snake leaves N2 - L free cells, all lying just ahead of the head on the loop, and the apple falls uniformly among them. The expected distance is (N^2 - L + 1)/2. Summing for L = 3 to N2 - 1 gives E[moves] = N^2 (N^2 - 3) / 4 (976 for 8 x 8), growing like N4/4.

Safe shortcuts

The body always stays in loop order. The head may step to a neighbouring free cell that is further along the loop, not beyond the apple and strictly before the tail (plus the optional safety gap). The guarantee survives, but skipped cells are left behind the head and may later receive an apple that costs a full lap; hence shortcuts help early and hurt late (control: allowed until length < x board).

BFS and greedy

Breadth-first search finds the shortest free path. Unprotected, it eventually coils into a dead end. The safe variant simulates the move on a copy of the snake and commits only if the tail stays reachable afterwards; otherwise it chases its tail. Greedy only reduces the Manhattan distance and traps itself early.

Simplifications

Start length 3 on the loop, the tail cell counts as free for the next step, constant speed, apples drawn by a seeded generator so every run replays exactly. The 3D page uses the very same model code, so both views give identical numbers.

What to try
  • Cycle on 8x8: watch the cyan loop; compare "Moves per apple" with the yellow theory line in the first graph.
  • Try "BFS without safety" and "Greedy chaser" and press Run shoot-out to see how often each fills the board.
  • Shortcuts: raise the cut-off to 1.0 and see apples stranded behind the head (graph one spikes late in the game).
  • Choose "You steer" and play with the arrow keys, WASD or a swipe.
Moves needed per apple versus snake length
Snake length versus moves
Strategy shoot-out: share of games that fill the board
Cycle cost versus board side (measured vs N^2(N^2-3)/4)