The ghost hunts you

Your task

In a maze, the shortest way to someone often starts by going away from them, around a wall. Breadth-first search finds it. Picture water poured on the ghost's cell: it spreads into every open neighbour, then into their neighbours, one ring at a time. The first time the water reaches the player, it has come along a shortest path.

In code, the rings come from a queue: a list you take cells from at the front and add cells to at the back.

• Put the ghost's cell in the queue.
• Take the first cell out. If it is the player, stop.
• Otherwise add each of its neighbours that you have not seen before to the back of the queue, and repeat.

The ghost needs only the first step of that path. So keep a dictionary first that says, for every cell the search reaches, which step out of the ghost's cell leads there. The ghost's own neighbours are their own first step; any other cell copies first from the cell it was reached from. When the search reaches the player, first[player] is where the ghost moves.

Write ghost_step(grid, ghost, player) and return that cell. Find neighbours with your next_cell, so the ghost knows the walls and the tunnels too (a wall gives back the cell itself). Try the directions in the order up, left, down, right: when two ways are equally short, the ghost then takes the one whose first step comes first in that order. If the ghost is already on the player, or no path reaches the player, return ghost.

The game moves the red ghost with red = ghost_step(grid, red, player), a little more often as you eat the dots. The orange ghost still wanders at random.

The function is at the top of the program, marked fix this. Press Run to play the game as it is, then Check when your function is ready.

What Check tests