Archive for the ‘algorithm’ Category

A Little Maze Algorithm

Way back on my Amazon reviews post, I promised I’d post an explanation of the algorithm I used to generate the random mazes for the maze game in my book.

maze.png

Unfortunately, I haven’t had time to get around to it until just now, but better late than never!!!

So, here’s how it works:

Think of the pathways through the maze as being a graph (in the Mathematical sense) where a point where two pathways join or a point where you might turn is a vertex, and then the pathways connecting the vertices are edges. It’s clear that for a maze, you want your graph to be one connected tree, in other words a graph with no cycles. As long as the entry point and the exit point are part of one connected tree, there will be exactly one path from the beginning to the end.

To apply this idea and create the maze, the first step is to use the screen and graphics dimensions to determine the size of your grid of vertices (how many squares across and how many down). In this implementation, I start by dividing the entire playing field into equal-sized squares which form part of the maze pathways if colored white, and part of the maze wall if colored black. There’s a lattice of squares that I know should be black and a lattice that I know should be white, and the trick is to figure out which colors to give to the wild-card squares.

maze_algorithm.png

Here I’ve colored gray all of the squares whose color should be decided by the algorithm (note that this screen never appears in the final game). In graph terms, the white squares are the vertices, and the gray squares are the squares that might potentially be edges by being added to the maze pathway and turned white. You can see from this that the number of rows and number of columns both need to be odd numbers.

The algorithm works by picking one of the white squares at random from the middle of the grid and growing the tree from there by picking undecided (gray) squares and turning them white. Throughout the algorithm, you maintain a list of all of the white squares (vertices) that are not yet connected to the maze, but are only one gray square away from being linked in. At each round of the algorithm, you use the randomizer to pick one square from the list and attach it to the maze (by turning a gray square white, hence adding an edge to the graph). Then just keep going until there are no white squares left that aren’t connected to the maze pathway graph, and color the remaining gray squares black.

By only adding edges to connect vertices that weren’t already connected to the graph, you can see that you’ll never get a cycle. And by growing the graph from one central point, you can be sure that all of the vertices will be connected to the same component. So in the end, for every two white squares in the maze there’s exactly one path that leads from one to the other, notably there’s a unique path from the entry square to the exit square.

For fun, I wrote a MIDlet that illustrates the maze algorithm in action. You can donwload it from my game page: it’s the one with the enticing title “Illustration of maze algorithm.”

Remember that all of the source code from the examples in my book (including the complete maze example) is available for download on the publisher’s site Apress.com. The exact page for my book is here. (The source code download is in the left sidebar under “book extras”.)