Pathfinding race

Rung 35 turned structures into graphs: nodes, and edges between them. A maze is one of those graphs wearing a costume. Every open square is a node, every gap in a wall is an edge, and every step costs the same. Finding your way through it is pathfinding: get from one node to another, ideally by the cheapest route.

There are two different costs in that sentence, and this side quest is about keeping them apart. One is the length of the path you return. The other is how much of the graph you had to look at to find it.

Why AI needs it

A character in a game chasing you round a wall is running a pathfinder. So is a warehouse robot getting round a shelf, and a route planner picking roads. An AI agent planning a sequence of actions is often searching a graph too, just one whose nodes are situations rather than squares.

In all of them, looking costs something — time, battery, compute. A search that finds the best route but looks at the whole world to do it will not scale to a world the size of a city. The useful algorithms find the best route while looking at as little as they can get away with.

Do this

Open the Algorithm Arena at https://schoolhouse.space/arena and go to Write code. Your bot is one function, solve(maze). It gets:

• maze.start and maze.goal, cells like {x: 0, y: 0};
• maze.neighbors(cell), the open cells next to cell. Each cell you call it on counts once as examined, however many times you call it;
• maze.distance(a, b), the Manhattan distance between two cells, as if there were no walls. It is free and counts nothing;
• maze.maxSteps, the most steps a path may take.

Return the list of cells walked, from maze.start to maze.goal. The Arena re-checks every step against the real walls, so a path through a wall is rejected, not scored.

Start by running the built-in bots and watching them. "Step toward the flag" looks at very little but gets stuck. "Explore in layers" is breadth-first search: it looks at every cell one step away, then two, then three, so the first time it reaches the flag it has found a shortest path. On the ten tournament mazes it examines 3,079 cells in total. That is the number to beat.

Then write your own. The idea to chase: BFS treats every cell at the same depth as equally worth looking at, but you know where the flag is. A cell's distance walked so far, plus maze.distance from it to the flag, says something about how long any route through it must be. Look at the most promising cells first.

Run it on all ten tournament mazes. The Arena shows, for each run, whether you reached the flag, whether your path was the shortest possible, and how many cells you examined.

Where people get stuck

Stopping too early. If you stop the first time you see the flag as a neighbour, rather than when the flag is the cell you take next to look at, you can return a path that is not the shortest. It only bites on mazes with more than one route, which is why half the tournament mazes are braided.

Using a guess that can overestimate. maze.distance never claims a cell is further from the flag than it really is, because walls can only make a route longer. That property is exactly what your written explanation has to lean on. Multiply the guess by two to "be more confident" and the guarantee is gone — you may examine fewer cells and lose the shortest path on some maze.

Sorting a whole list every time you pick a cell works on these mazes, but it is the slow way to keep the most promising cell at the front. Rung 26's heap is the structure built for that job.