Background
So to anyone who knows me (or literally just reads my blog/website) it should come as no surprise that I’m more of a PL guy than an Algo guy. I think algorithms are neat and all, I just never found them as interesting as programming languages. A programming language is something tangible that I can have fun with and interact with, algorithms exist mostly on paper. However, I decided that I can’t keep thinking like this, so over the past weekend, I locked myself in and forced myself to come up with some sort of an algorithm with no resources. Just simple trial and error with a bit of logic on the side. I ultimately settled on trying to make a maze generation algorithm since that seemed like a fairly good application for pattern matching (and I love pattern matching).
First I tried subdividing mazes into the smallest possible building blocks. While you can totally construct a maze from these, it actually didn’t help my algorithm that much. My goal was to ensure mazes were acyclic and used all possible space on the board. Using all possible mazes on a 2×2 or 3×3 grid, I was unable to find a way to stitch them together which guaranteed an acyclic and solvable maze.
Once I had come to the realization that I wasn’t going to get anywhere by building a maze with pre-made pieces, I decided to try to draw the lines in a similar way. Basically I would start at a position and try to calculate whether or not adding a line would make any other tile unreachable. While this would theoretically work, when trying this out on paper, it turned really cumbersome on any maze greater than 3×3 tiles. Since each line involves iterating over every tile in the maze, this algorithm would balloon really fast. It also tended to produce very similar looking mazes and had no guarantees about being acyclic.
Finally I came to the algorithm I am presenting here. It is quite simple and lends itself well to pattern matching. I am not sure if this algorithm exists, I still have not looked up any maze generator algorithms and will not I am certain I cannot improve my algorithm any more. If this is a case of parallel evolution, that’s pretty neat (don’t tell me about it too 🙃). If not, I would like this algorithm to be called “McKinley’s algorithm” mostly so my namesake algorithm can be something completely useless 😜.
The Algorithm
This algorithm relies on tracking the number of possible connections a maze tile can have. Connections are defined as any edge which doesn’t have a line. Therefore a tile with no edges has 4 connections, one line has 3 connections, two lines has 2 connections, and three lines has 1 connection. There is no possible tile that can have 0 connections.
This algorithm relies on reducing the value of these connections which is anologous to placing a wall between two adjacent tiles. There, however, are a number of cases where reducing the value of a connection would lead to parts of the maze becoming unreachable or connections reaching 0. Once a tile is irreducible, no further action can be taken on it, so it is in effect finished with the algorithm. For the sake of demonstration, we will denote any irreducible tile with the “Δ” symbol (arbitrarily chosen because I know it will make math people mad). The following are rules for a given tile to transition to irreducible:
- A tile with 1 connection is always Δ.
- A tile with 2 connections is Δ iff 1 or more of its connections is Δ.
- A tile with 3 connections is Δ iff 2 or more of its connections are Δ.
- A tile with 4 connections is Δ iff 3 or more of its connections are Δ.
To begin the algorithm, begin by writing a grid of tiles. The width and height of this grid must be at minimum 2×2. All tiles should start with a connection value of 4, indicating that the tiles have no walls drawn. The following is an example of a starting grid:
| 4 | 4 | 4 |
| 4 | 4 | 4 |
| 4 | 4 | 4 |
Next update connection values to indicate the walls of the maze on the outside. This is as simple as subtracting 1 from the connections on edges and 2 on corners. This indicates that one of the possible connections (one which would lead us outside of the maze bounds) is invalid, therefore we are unable to use it. Our starting grid would look as follows after we add our borders:
| 2 | 3 | 2 |
| 3 | 4 | 3 |
| 2 | 3 | 2 |
Next we pick a random tile from our grid. For this example, we will pick the top left tile. We then pick a random connection. For this example, we will pick the center left tile. We subtract 1 from both connections indicating that we have drawn a wall between the two tiles. The following is our outcome:
| 1 | 3 | 2 | ||
| — | ||||
| 2 | 4 | 3 | ||
| 2 | 3 | 2 |
Next we examine the values which we just changed. Since 1 is always Δ, we update our grid to reflect that. After updating 1 to Δ, we look to its current connections. Its only connection is a 3 in the top middle position. Since 3 is only Δ when 2 or more of its connections are Δ, we do not update the 3 to Δ. Next we change our focus to the other tile we updated in the previous step. 2 is only Δ iff 1 or more of its connections is Δ. Since 4 and 2 are not Δ, we do not update the center left tile. The resulting grid is now:
| Δ | 3 | 2 | ||
| — | ||||
| 2 | 4 | 3 | ||
| 2 | 3 | 2 |
Next, let’s pick the top center tile and place a wall between it and the center tile, the following would be our grid after adding that wall:
| Δ | 2 | 2 | ||
| — | — | |||
| 2 | 3 | 3 | ||
| 2 | 3 | 2 |
Now when we examine our tiles to see what we can change to Δ, we notice something interesting. Since 2 is Δ when 1 or more of its connections is Δ, and this holds true, our top center tile becomes Δ. However, the top right tile is also 2, and now also has 1 or more connection which is Δ, so it will also become Δ. This process will continue on until we hit the center right tile. Since that tile has 3 connections, and only one of those connections is Δ, it does not become Δ. Next, looking to the center tile, the 3 there also does not become Δ since it does not fit the requirements. The following is the outcome of this:
| Δ | Δ | Δ | ||
| — | — | |||
| 2 | 3 | 3 | ||
| 2 | 3 | 2 |
Now let’s pick the center right tile. Notice one of its connections is Δ, this means we cannot sever this connection. In effect we only have two connections we could cut between. For this example we’ll pick the bottom right tile. After adding the wall and updating Δ, we are left with this:
| Δ | Δ | Δ | ||
| — | — | |||
| 2 | 3 | Δ | ||
| — | ||||
| 2 | 3 | Δ |
The algorithm finishes once all tiles are Δ, which will result in the finished acyclic maze. Since we have not hit this stage yet, we still have some work to do. Let’s next place a wall between our center tile and the center left tile. This will result in this grid:
| Δ | Δ | Δ | ||
| — | — | |||
| Δ | | | Δ | Δ | |
| — | ||||
| Δ | Δ | Δ |
Notice, all of our tiles have now flipped. This indicates that our maze is complete. Drawing it out with text gives us this rather boring but valid maze:
+---+---+---+
| |
+---+---+ +
| | |
+ + +---+
| |
+---+---+---+
To add the start and end, simply pick one of the tiles on the edge and remove a wall. This is done separate to the algorithm because when it was factored in, it would either require Δ tiles be placed outside the bounds of the maze to ensure the start or end would not be closed off accidentally. This was more trouble that it was worth, so I just opted to pick random edge tiles after the maze is complete. The following could be our completed maze with a proper start and end:
+---+---+---+
START |
+---+---+ +
END | |
+ + +---+
| |
+---+---+---+
And thus the algorithm is finished. I am not sure if this algorithm exists already. I would not be surprised given how simple it is, although I feel like it was probably done in a much better way 😁. If anyone can find any holes in this algorithm, please drop a comment, I would be happy to know how wrong I am (or I guess how much of an unintended plagiarist I am too).