Maze Generation with Prim's Algorithm

Edit Feb 2023: I realized that there's somehow a lot of links floating around to this old post, so I've come back and edited the explanation to be clearer. Enjoy Prim's Algorithm!

As it's been a while since I've written a technical post (because we all know how much everyone loves those), I'd like to take a moment to introduce my good friend Prim's Algorithm. Time to get excited about graph theory!

I rediscovered a Java implementation of Prim's that I had made about a year ago to generate mazes for contest problems. With that purpose in mind, randomized Prim's algorithm represents the maze as a graph and connects the vertices in a minimum spanning tree. I created my implementation using the pseudocode on wikipedia.

The algorithm works by filling in a grid with "wall" tiles and opening one starting cell at random. This starting cell becomes a root node from which paths begin to branch. The surrounding walls of the open cell comprise the "frontier", or the set of potential next cells to process.

We begin by randomly selecting a wall cell from the frontier. If the cell on the other side of the selected wall has not been explored (is not connected to the maze), we knock down the wall. In other words, we mark the wall and the opposite tile as open, connecting them to the maze. In graph terms, the starting cell and the cell on the other side of the wall are nodes, and we've connected them with an edge by creating a path through the wall. The walls touching this new open cell then become part of the frontier.

We repeat this process, randomly selecting from the frontier at each iteration. Random selection provides branching, so that we're not always opening paths in a straight line. We remove wall cells from the frontier only when the cell cannot be operated on because the opposite cell has already been explored. This ensures sufficient backtracking to explore the entire maze.

The above video shows visually what the process of the algorithm is. The implementation is my Java code ported to Android, drawn to a live wallpaper using Canvas. (Gingerbread is starting to show its age.)

The maze in the app is actually generated with an added heuristic such that the beginning and end points will be far enough apart that the end result will be visually interesting. This is because the second part of that video, after the maze completes generation, shows a visualization of Dijkstra's shortest path algorithm solving the maze that has just been generated. Incidentally, Dijkstra is cited as a rediscoverer of Prim's algorithm. Dijkstra's is a favorite shortest path algorithm, and we use an implementation of it often in computer science contests.

My implementation of Prim's Algorithm

import java.util.*;

public class Prim {

 public static void main(String[] args) {
  // dimensions of generated maze
  int r = 10, c = 10;

  // build maze and initialize with only walls
  StringBuilder s = new StringBuilder(c);
  for (int x = 0; x < c; x++)
   s.append('*');
  char[][] maz = new char[r][c];
  for (int x = 0; x < r; x++) maz[x] = s.toString().toCharArray();

  // select random point and open as start node
  Point st = new Point((int)(Math.random() * r), (int)(Math.random() * c), null);
  maz[st.r][st.c] = 'S';

  // iterate through direct neighbors of node
  ArrayList < Point > frontier = new ArrayList < Point > ();
  for (int x = -1; x <= 1; x++)
   for (int y = -1; y <= 1; y++) {
    if (x == 0 && y == 0 || x != 0 && y != 0)
     continue;
    try {
     if (maz[st.r + x][st.c + y] == '.') continue;
    } catch (Exception e) { // ignore ArrayIndexOutOfBounds
     continue;
    }
    // add eligible points to frontier
    frontier.add(new Point(st.r + x, st.c + y, st));
   }

  Point last = null;
  while (!frontier.isEmpty()) {

   // pick current node at random
   Point cu = frontier.remove((int)(Math.random() * frontier.size()));
   Point op = cu.opposite();
   try {
    // if both node and its opposite are walls
    if (maz[cu.r][cu.c] == '*') {
     if (maz[op.r][op.c] == '*') {

      // open path between the nodes
      maz[cu.r][cu.c] = '.';
      maz[op.r][op.c] = '.';

      // store last node in order to mark it later
      last = op;

      // iterate through direct neighbors of node, same as earlier
      for (int x = -1; x <= 1; x++)
       for (int y = -1; y <= 1; y++) {
        if (x == 0 && y == 0 || x != 0 && y != 0)
         continue;
        try {
         if (maz[op.r + x][op.c + y] == '.') continue;
        } catch (Exception e) {
         continue;
        }
        frontier.add(new Point(op.r + x, op.c + y, op));
       }
     }
    }
   } catch (Exception e) { // ignore NullPointer and ArrayIndexOutOfBounds
   }

   // if algorithm has resolved, mark end node
   if (frontier.isEmpty())
    maz[last.r][last.c] = 'E';
  }

  // print final maze
  for (int i = 0; i < r; i++) {
   for (int j = 0; j < c; j++)
    System.out.print(maz[i][j]);
   System.out.println();
  }
 }

 static class Point {
  Integer r;
  Integer c;
  Point parent;
  public Point(int x, int y, Point p) {
    r = x;
    c = y;
    parent = p;
   }
   // compute opposite node given that it is in the other direction from the parent
  public Point opposite() {
   if (this.r.compareTo(parent.r) != 0)
    return new Point(this.r + this.r.compareTo(parent.r), this.c, this);
   if (this.c.compareTo(parent.c) != 0)
    return new Point(this.r, this.c + this.c.compareTo(parent.c), this);
   return null;
  }
 }
}