Solving Mazes

Last week, I explained the process of visually generating mazes. In this post, I will explain how I managed to solve the mazes. Over the last week, I have explored two different options, but only one of them ended up being practical and useful.

Before entering the explanation of both ideas, here is how the maze looks to the program. The layout of an unsolved maze is a list of lists of one of two characters, space or block. In other words, it is a list of strings where each string is a row and the equal indices in a string are in the same column. This is demonstrated by the image below:

In this, spaces can either indicate a "cell" or a "wall." They can be identified by the row or column they are in. A wall can be identified as any odd row (with the top row being row number one) and any odd column (with the leftmost column being column number one).

Creating a Graph

My first idea, and the idea I had assumed I was going to use throughout my project, was to generate a graph of cells given a maze. These cells would be represented by nodes, and the connection between nodes (shown by a lack of a wall in a maze) would be denoted by an edge (a representation of two nodes connected). As with most functions in Haskell, the idea was to simply recur on every visited cell, and draw connections between every cell. The program would work as follows

1. Beginning with the starting cell, check the walls above, left, right, and below a cell.

2. For every wall that is empty, create an edge between the current cell node and the node the wall leads to.

3. Create a wall for every empty wall around the current cell node, and store the resulting maze

4. Combine the current node value and the current edges with the result of repeating step two onwards for every cell node that was connected to the current cell node given the "new" maze created in step 3

However, this idea ended up being too complicated, especially due to a lack of state-changes.

A Path of Nodes

This idea took a simpler approach, although it ended up being slightly more inefficient. Instead of using nodes and graphs, I simply solved the maze directly in the graph using the following steps.

1. Create an "Integer Maze," replacing every space character with a -1 and every block character with a -2

2. Put a positive integer in every cell. This number should also be able to be mapped back to the its location, using coordinates

3. Given this new integer maze, do the following

4. Begin at cell number 1

5. Check the four surrounding walls of the cell

6. For every -1

7. If the cell on the other side of the negative one is the "goal" cell (the last cell in the path from the beginning of the maze to its end), return the goal cell appended to the list of the rest of the cells already traversed by that thread

8. Otherwise, replace the -1 with a -2, and move into the cell on the other side, repeating steps 3.2 onwards until 3.1 succeeds

9. If there are no -1s around the cell (i.e. all -2s), return an empty list as there is no path from the beginning to the goal cell

This approach results in only a single list of nodes (as there is only one path of nodes from beginning to destination). Once this list is returned, the program simply converts those nodes to coordinates, and then replaces those coordinates with period characters (.), resulting in a maze like the following.