How It Works

Since my last blog post, I have tried multiple different methods of generating the mazes, with the last last one being the simplest and most successful. Before I go through those methods, I will provide the overall way my program works, except the actual printing of the maze. These first two steps are adapted from the blog I mentioned in my earlier posts.

Step 1: Create n x m Grid The foundation of graph theory in computer science is that a graph is made up of nodes that are interconnected. The connections between these nodes are known as edges. Each of these edges has two important elements: the nodes that it connects and the label (or name) of the edge. For the purposes of this program, only the walls are necessary. This step creates width*height number of mazes, where width and height are parameters given by the user/generator. Once these nodes are created, the edge, known as a Wall in this program, between each node is specified to either be a Horizontal or Vertical wall. With this, we are left with an n x m grid (n = width, m = height), with walls between every node.

Step 2: Generate the random edge traversal of a grid The algorithm with which I am creating these mazes is known as a Depth First Search (DFS) algorithm. This algorithm takes a starting node as input, then visits all nodes that are directly adjacent to it. For each of these nodes, if there are no more unvisited adjacent nodes, the algorithm returns the list of nodes that it has gone to. However, if there are unvisited adjacent nodes to the current node, the algorithm recurs using the new node as a starting input. Eventually, every node is visited, and a list of potential paths has been made. Knowing this, there will always be a path from one node to another, thus allowing us to start and end the maze wherever we want. For a more detailed explanation of this, please refer to this link. However, rather than using the DFS algorithm, I used an Edge DFS (EDFS) algorithm, in which the program does the same thing, but marks which Walls it “breaks down,” allowing us to finish with a list of Walls that will not be shown in the maze. After comparing that list to the list of all Walls we had to begin with, the program generates a list of all walls that hadn’t been broken. This list is the key to viewing the mazes.

Monads

The most difficult concept I have been struggling with over the past month is the idea of monads, one that is unique to the Haskell programming language. However, after a few weeks of working with one of the more confusing monads (Monad.Random) and a more basic one (System.IO), I have gained a basic understanding of monads, although I still have much to learn. The definition of a monad, according to the Haskell Wiki is: “A monad is a way to structure computations in terms of values and sequences of computations using those values.” Whether or not you find this to be a complex statement, the true complexity of understanding the extremely abstract concept of a monad is significantly higher. After reading many tutorials, some more confusing than others, I have come to understand the definition written above. The word “monad” means “a single unit.” This definition captures an important aspect of the concept, in that monads are constructions that allows data and computations of that data in a single structure, allowing for a centralized, more efficient, and more reliable form of computation. While monads are meant to give the programmer more power and flexibility, they are very difficult to use at first. For my project, in order to randomize the EDFS, I had to use Control.Monad.Random. Once I had randomized EDFS and shuffled its results, I ended up leaving the data within the monad. After doing some research on this, it is debatable whether or not this is the correct practice, but I left the data in the monad due to an intransparency in extraction of this data, with the only other option being to move the data from the Monad.Random monad to the System.IO monad, which I ended up doing in my final visual. My next post (posted early next week) will go through the steps I went through over the last two weeks to achieve the actual printing of the following maze and far more just like it:

Please feel free to leave questions or comments below, or use the contact box at the bottom of this page. Thanks!