Random Mouse maze algorithm
The Random Mouse picks a random direction at every step. It has no memory and no plan, and it almost never finds the exit in time.
How it works
At each step the mouse looks at the open directions and picks one at random, including the way it just came. It never marks cells and never learns from dead ends.
In theory a random walk on a finite maze reaches the exit eventually, with probability one. In practice the expected time grows very fast with the maze's size, so in every MazeSim show the mouse is still wandering when the time runs out.
What to watch for
Watch the white trail jitter back and forth near the start, fading behind it, while the counter just says 'still wandering…'.
Properties
- Shortest path
- No
- Finds the exit
- Eventually, in theory
- Explores
- Randomly, again and again
- Memory
- None
Race it
Same maze, same speed, first to the exit wins: Random Mouse vs Breadth-First Search. Or put it in a gauntlet, where the winner stays on.
FAQ
Will the random mouse ever finish?
On a finite maze, eventually, yes. But it usually takes many thousands of times longer than a real search, so in these videos it never does.
Why include it?
It's the baseline that shows how much smarter every other algorithm is. And it's funny.