Mapping mazes from the inside
We have been tasked with mapping and finding routes through multiple tunnel systems. Each one is a “perfect maze”, meaning its structure is a tree, and any two locations, including the start and goal, have one non-backtracking route connecting them:
In these dark tunnels, we occupy one maze cell at a time and only know which directions we can move in and whether we’ve reached the goal. We can record our history along the way.
A natural choice would be depth-first search (DFS). Any time we encounter a fork, choose one direction and keep going. When we hit a dead end, turn around and try the next option. A deterministic version of this is the hand on wall rule, where we touch our right or left hand to the wall and keep walking without losing contact with the wall. Here, we get multiple runs through the maze to try to map it, so we’ll choose randomly when we encounter a fork.