The shortest path to the fruit

Posted on 26 August 2026

Reading time 7 minutes

Comments

golang ai snake

Breadth first search, a bordered board, and why searching properly is barely worth six points

The greedy player measures the distance to the fruit in a straight line, which stops being true the moment there is a snake in the way. The fix is to stop guessing and search for a real route through the board as it actually is.

This is the first player with a search in it, and the first one to share machinery with the rest of the series.

Following a path

Several players work the same way: search for a route, then walk it. That lives in one type.

type RegenType int

const (
	RegenEveryTick RegenType = iota
	RegenEveryFruit
	RegenNever
)

func NewPathFollowingSolver(name string, pathGen path.Generator, regenPath RegenType) *PathFollowingSolver

A path.Generator is anything that can find a route between two tiles.

type Generator interface {
	Generate(state *state.State, from *tile.Vector, to *tile.Vector) (Path, bool)
}

shortest is a breadth first search regenerated on every tick. It plans a whole route to the fruit, takes one step of it, throws it away, and plans again from the board it now finds itself on. Planning every tick sounds wasteful and is the right thing to do: the board changes underneath a plan, and a route that was fine three moves ago is now a route through the snake’s own middle.

A board with a wall around it

The obvious way to write a search is to hold a visited set, and for each tile work out its four neighbours, check each one is on the board, look up what is on it, and decide whether it can be walked on. That is four range checks and four tile lookups per tile visited, and it is most of what the search costs.

Instead the board keeps a mask of the tiles the snake could move into, with a one-tile border of wall around the outside.

# # # # # # # # # # # #
# . . . . . . . . . . #
# . . . . o . . . . . #
# . . . . . . . . . . #
# . . . @ # # # . . . #
# . . . . . . # . . . #
# . . . . . . # . . . #
# . . . . . . . . . . #
# . . . . . . . . . . #
# . . . . . . . . . . #
# . . . . . . . . . . #
# # # # # # # # # # # #

The border is never open, so a search can take a neighbour as the index plus or minus one, or plus or minus a row, and never check an edge. There is no coordinate arithmetic and nothing to range-check: walking off the left of a row lands on the border column, which is wall, and the search stops there on its own.

// Open returns the board as a bordered mask of the tiles the snake could move
// into - empty or fruit. The mask is Stride wide; the tile at (x, y) is at
// (y+1)*Stride + x + 1.
func (s *State) Open() []Cell

The board keeps that mask up to date as the snake moves - only two or three tiles change a tick - so a search copies it rather than building it.

The search

func (g *BreadthFirstSearch) Generate(st *state.State, from *tile.Vector, to *tile.Vector) (Path, bool) {
	mask, stride := st.Open(), st.Stride()
	if len(g.owners) != len(mask) {
		g.owners = make([]pos, len(mask))
		g.queue = make([]pos, 0, len(mask))
	}

	owners := g.owners
	start(owners, mask)

	delta := stepDeltas(stride)
	fromI, toI := index(from, stride), index(to, stride)
	owners[fromI] = noOwner
	if fromI == toI {
		return backtrace(fromI, owners, stride), true
	}

	queue := append(g.queue[:0], fromI)

	for read := 0; read < len(queue); read++ {
		i := queue[read]
		if i == toI {
			return backtrace(i, owners, stride), true
		}

		for _, at := range permutations[g.roll()%uint32(len(permutations))] {
			adj := i + delta[at]
			if owners[adj] != unvisited {
				continue
			}
			owners[adj] = i
			queue = append(queue, adj)
		}
	}

	return nil, false
}

There are three things in there worth pulling out.

owners is doing three jobs at once. It starts as a straight copy of the mask, so every wall is already marked blocked and every open tile is already marked unvisited. When the search reaches a tile it writes the tile it came from over it. So the same array is the board, the visited set, and the route home, and the inner loop is one load and one comparison.

const (
	blocked   = state.Wall
	unvisited = state.Open
	noOwner   = pos(-1)
)

The queue never shrinks. A read cursor into a slice that only grows gives a queue without reslicing or allocating for every tile taken off it.

The four directions are tried in a different order every time. permutations is all twenty-four orderings of the four directions, as byte indices, and the search draws one for every tile it visits.

// Which of the many equally short routes a search comes back with depends
// entirely on that order, and solvers that judge a route by its shape do far
// worse when the tie always falls the same way.
var permutations = allOrders()

That does not matter to this player, which just wants a shortest route. It matters a great deal to the safe player later on, which judges a route by the shape it leaves the snake in.

Watching it spread

Breadth first means the search expands in rings of equal distance, and the first time it touches the fruit it has come by a shortest route.

. . . . . . . .        . . 4 . . . . .        . 4 3 4 . . . .
. . . . . . . .        . . . . . . . .        . 3 2 3 4 . . .
. . . o . . . .        . . 2 o . . . .        . 2 1 2 3 4 . .
. . . . . . . .        . . 1 . . . . .        . 1 @ 1 2 3 . .
. . . @ . . . .   ->   . . @ . . . . .   ->   . 2 1 2 3 4 . .
. . . . . . . .        . . 1 . . . . .        . 3 2 3 4 . . .

Every ring is the whole board at that distance, whether or not it is anywhere near the fruit. That is the thing the next post fixes.

How it does

solver        games   wins  stalled  avg score   best  worst  avg moves   per game
greedy         2000      0        0       22.4     47      6      182.3       42us
shortest       2000      0        0       28.2     51      8      228.1      423us

Six points, for ten times the cost per game.

I found that genuinely deflating the first time I ran it. The search is correct - it finds a real shortest route through the real board, and the greedy player is guessing - and it buys six points of ninety-nine.

The reason is that both players are answering the same question, and it is the wrong question. “What is the quickest way to the fruit” has nothing to say about what the board looks like when you get there.

. . . . . . . . . .
. . # # # # # # # .
. . # . . . . . # .
. . # . o . . . # .          shortest route: four moves
. . # . . . . . # .          and then the snake is sealed
. . # # # # # # @ .          inside a room with itself
. . . . . . . . . .

The route is genuinely the shortest one. Taking it ends the game.

Pros

It finds a route through the board rather than over it, so it never walks into a wall of its own body while a way round exists.
The bordered mask makes the inner loop about as small as it can be, and the search allocates nothing after the first call.
It is the honest baseline for “search, but no lookahead” - everything smarter in this series is measured against 28.

Cons

Six points over guessing, which tells you how little of this problem is pathfinding.
It searches the entire board evenly, including everything in the opposite direction from the fruit.
A shortest route and a survivable route are different things, and it cannot tell them apart.

Next: the same routes, found by looking at a fraction of the board.

Jim Wright