Transcription
You can solve a maze with your eyes closed. If you just put one hand along one wall, you will eventually reach the end of most common mazes.
After a simple wall following mouse took home gold in the first finals, the goal of the maze was moved away from the edges and freestanding walls were added. Your next instinct might be to run through the maze, taking note of every fork in the road. Whenever you reach a dead end or a loop, you can go back to the last intersection and try a different path. If your last left turn got you nowhere, you'd come back to that intersection and go right instead. You can think of this strategy as the one a headstrong mouse might use, running as deep into the maze as it can and turning back only when it can't go any further. This search strategy known as depth first search will eventually get the mouse to the goal. The problem is it might not be the shortest route.
The sibling to this search algorithm, breadth first search, would find the shortest path. With this strategy, the mouse runs down one branch of an intersection until it reaches the next one. Then it goes back to check the path it skipped before moving on to the next layer of intersections. So the mouse checks every option it reaches. But all that backtracking means that it's rerunning paths dozens of times. At this point, even searching the whole maze often takes less time. So why not just do that? A meticulous mouse could search all 256 cells of the maze, testing every turn and corner to ensure it has definitely found the shortest path. But searching so thoroughly isn't necessary either.
Instead, the most popular micro mouse strategy is different from all of these techniques. It's a search algorithm known as flood fill. This mouse's plan is to make optimistic journeys through the maze. They simply draw the shortest path to the goal and go. When their optimistic plan inevitably hits a wall that wasn't on their map, they simply mark it down and update their new shortest path to the goal.
Under the hood of the algorithm, what the micro mouse is marking on their map is the distance from every square in the maze to the goal. To travel optimistically, the mouse follows the trail of decreasing numbers down to zero. Whenever they hit a wall, they update the numbers on their map to reflect the new shortest distance to the goal. This strategy of following the numerical path of least resistance gives the floodfill algorithm its name. The process resembles flooding the maze with water and updating values based on the flow.
While this algorithm isn't guaranteed to find the best path on first pass, it takes advantage of the fact that micro mice need to return to the start to begin their next run. So if the mouse treats its return as a new journey, it can use the return trip to search the maze as well. Between these two attempts, both optimized to find the shortest path from start to finish, it's extremely likely that the mouse will discover it. And the mouse will have done it efficiently, often leaving irrelevant areas of the maze entirely untouched.