MazeMasterKarel
—Corbin Foucart
MazeMasterKarel creates a random, but solvable maze by using a
bifurcation algorithm.
Karel begins on the only “active cell,” with the rest of the world closed
cells. He creates a path by randomly connecting to one of four linearly
adjacent spaces in the maze, which then is designated as the new “active
cell,” and the process repeats. While doing so, Karel leaves a “trail of
breadcrumbs;” if he hits a dead end, he follows the trail back to the
last possible point where the trail could have diverged and starts
again. The maze generation is complete when Karel follows his trail all
the way back to the origin. The last two steps create a start and a
central end point for square world mazes -- the nature of the algorithm
tends to make adjacent and opposite start and end points uninteresting.
However, if the last two lines of run() are disabled, Karel can generate
a random solvable maze in a world of any dimension. One can also alter
the weights of the probabilities in for Karel’s selection decisions,
allowing for the creation of a diverse group of mazes.
This project is dedicated to Wilhelm and Jacob Grimm, as well as their
clever protagonists, Hansel and Gretel. Thanks for the inspiration.