*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; } } }