Maze Generation with Prim's Algorithm

November 6, 2012 at 10:05pm

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 basically becomes a root node from which paths begin to branch. For each surrounding wall of the open cell which comprise the "frontier", the algorithm makes the decision to, if the tile on the other side of the wall has not been explored and is not part of the maze, knock down the wall and essentially open that tile as well as the tile where the wall was, connecting the two nodes. The walls of this new node then become part of the frontier. Intuitively, the random selection from the frontier at each iteration provides branching, and the removal from the frontier only when the cell cannot be operated on because the opposite cell has already been explored 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;
  }
 }
}