Labyrinth

Rust implementation of the algorithms in Mazes For Programmers

Colored Solutions

The darkness of color depicts the distance from a starting square(the farther the darker). This lets us see, quite clearly, the structure of the maze. We’re shining Dijkstra-flavored X-rays at it and seeing what’s inside. It turns out that this works great for letting us visually compare all kinds of different maze algorithms.

Binary Tree Algorithm

Starting from the northwest corner, we randomly choose either to move south or east. When we can’t move east, we move south and when we can’t move south we move east. This leads to a corridor in the southern and eastern walls.

showing the longest path in a binary tree maze

Sidewinder Algorithm

Here on every starting from northwest, we flip a coin. If heads we carve east else we halt, select a cell from the current carved path, and open up the cell to the south. Then we start from the next cell from the halted cell.

showing the longest path in a sidewinder maze

Aldous Broder Algorithm

In Aldous Broder Algorithm we randomly hop from cell to neighbour cell and create a path through them(if not already present). It’s a time-consuming algo but lacks bias.

showing the longest path in an Aldous broder maze

Wilson Algorithm

We start by choosing a point on the grid marking it visited. Then we choose any unvisited cell in the grid and randomly walk until we encounter a visited cell. At that point we add the path followed to the solution, marking each as visited, and then repeat. The process repeats until all the cells in the grid have been visited. Unbiased like Aldous Broder but focuses on visited cells rather than unvisited cells.

showing the longest path in a Wilson maze

Hunt And Kill Algorithm

We start randomly from any cell and then traverse to an unvisited neighbour. When we run out of unvisited neighbours, we randomly choose an unvisited cell that neighbours the visited cell and make a path between those. Then we repeat the method until all cells are visited.

showing the longest path in a hunt-and-kill maze

Recursive Backtracking

Same as Hunt and Kill, but on finding no unvisited neighbour, we backtrack the visited cells until we find one with an unvisited neighbour.

showing the longest path in a recursive backtracking maze

Algorithm analytics

Deadends are cells with only one way out. With better algorithms, the number of dead ends decreases which increases the longest path length.

           BinaryTree -> longest_path_len: 73,  deadend: 100/400, %: 25
           Sidewinder -> longest_path_len: 70,  deadend: 111/400, %: 27
         AldousBroder -> longest_path_len: 109, deadend: 117/400, %: 29
               Wilson -> longest_path_len: 106, deadend: 115/400, %: 28
          HuntAndKill -> longest_path_len: 147, deadend: 40/400,  %: 10
RecursiveBacktracking -> longest_path_len: 244, deadend: 41/400,  %: 10

Masking

We can create a text/image file where some cells are inactive. And when we run an algorithm on it mazes are made by ignoring the cells

Text Masking

                                ......................
                                ..........XX..........
                                .........XXXX.........
                                ........XXXXXX........
                                .......XXXXXXXX.......
                                ......XXXX..XXXX......
                                .....XXXXX..XXXXX.....
                                ....XXXXXX..XXXXXX....
                                ...XXXX........XXXX...
                                ..XX..............XX..
                                ......................
                                ..XX..............XX..
                                ...XXXX........XXXX...
                                ....XXXXXX..XXXXXX....
                                .....XXXXX..XXXXX.....
                                ......XXXX..XXXX......
                                .......XXXXXXXX.......
                                ........XXXXXX........
                                .........XXXX.........
                                ..........XX..........
                                ......................

Image Masking

YIP YIP!