Maze generator & solver

Jamis Buck’s instructive website inspired me to write a sketch that draws a random maze on a display. Next, it finds a trace from entrance to target area, both randomly selected.

The video shows the result on a 320×240 ili9341 TFT display, driven by an esp8266 based Wemos mini pro.

Starting from a random position, the algorithm uses the ‘growing tree’ strategy with backtracking to build a well formed maze (i.e. without unreachable areas). The order in which a position’s four neighbors are checked is randomized as well.

During the build process (removing walls), the cell_status array keeps track of each cell’s visit status (first bit) as well as the status of its four walls (last four bits). Once the maze has been drawn, the first four bits of these status bytes can be used for other puposes, like solving the maze. Notice that by then, the first bit of all bytes will have value 1.

The sketch below will continuously generate random mazes, and then solve them from scratch (rather than cheat by extracting the solution directly from the active array). As you can see, the code for generating the maze is very similar to the code for solving it.

For manually solving the maze, you put the code for building it in setup() and use the loop() function for listening to whatever device you use to navigate. (I plan to use a joystick).