A quick look at how Kruskal's algorithm can be used to generate a perfect maze.
Kruskal's algorithm is an algorithm for finding a minimum spanning tree, it takes a set of vertices for input and finds the subset of edges that forms a tree that:
Kruskal's algorithm is very similar to Prim's algorithm, but with the following key steps:
traversable edges (sorted or as priority queue)traversable edges, get minimum edge and traverseLet's demonstrate Kruskal's algorithm by using it to generate a perfect maze—a maze where all points are reachable. We'll use JavaScript, specifically p5js to help visualize what we are doing. I'll keep the user interface as simple as possible.
We setup our initial canvas and a basic grid to outline the cells that will make up our maze.
function setup() {
const canvasSize = 400;
const gridSize = 8; // num of cells in grid
const csize = canvasSize / gridSize; // cell size
/* draw initial canvas */
createCanvas(canvasSize, canvasSize);
background(160); // gray
strokeWeight(2); // width of lines
stroke(255); // white lines
/* draw grid, outline each cell */
for (let i=0; i <= gridSize; i++) {
const k = i * csize;
line(k, 0, k, canvasSize);
line(0, k, canvasSize, k);
}
}
We can think of our grid as a graph, and each cell within the grid as a vertex.
function setup() {
...
const cellmid = Math.floor(csize / 2); // offset to help get midpoint of cell
strokeWeight(10);
stroke('lightblue')
for (let i=0; i < gridSize * gridSize; i++) {
const r = Math.floor(i / gridSize);
const c = Math.floor(i % gridSize);
const x = (c * csize) + cellmid;
const y = (r * csize) + cellmid;
point(x, y);
}
}
The first step of Kruskal's algorithm is to convert all the vertices to individual disjoint sets. We'll do that by creating a custom VertexDisjointSet class to hold a vertex's (e.g. cell) coordinates while supporting disjoint set operations. Additionally we will add an Edge class to represent the relation between two vertex.
// define outside of setup function
class VertexDisjointSet {
constructor(x, y) {
this.x = x;
this.y = y;
this.size = 1;
this.parent = this;
}
/** Find the parent disjoint set of given set */
find(vds) {
if (vds.parent != vds)
vds.parent = this.find(vds.parent);
return vds.parent;
}
/** Connect other set with this set */
union(other) {
const ourParent = this.find(this);
const theirParent = this.find(other);
if (ourParent !== theirParent) {
if (ourParent.size > theirParent.size) {
theirParent.parent = ourParent;
ourParent.size += theirParent.size;
} else {
ourParent.parent = theirParent;
theirParent.size += ourParent.size;
}
}
}
}
/** A connection between two vertices */
class Edge {
constructor(v1, v2) {
this.v1 = v1;
this.v2 = v2;
}
}
Next we convert the vertices to the disjoint sets, and store them in the collection vertices. It's also a good time to build all the edges as we're initializing our vertices.
function setup() {
...
const cellmid = Math.floor(csize / 2); // offset to help get midpoint of cell
const vertices = new Array(gridSize * gridSize); // <-- holds our vertices
const edges = [];
strokeWeight(10);
stroke('lightblue')
for (let i=0; i < vertices.length; i++) {
const r = Math.floor(i / gridSize);
const c = Math.floor(i % gridSize);
const x = (c * csize) + cellmid;
const y = (r * csize) + cellmid;
vertices[i] = new VertexDisjointSet(x, y);
point(x, y);
if (r > 0) {
edges.push(new Edge(vertices[i], vertices[i-gridSize]));
}
if (c > 0) {
edges.push(new Edge(vertices[i], vertices[i-1]));
}
}
}
To keep edge generation simple, we use the following formula, for every vertex:
Let's visualize what we have so far, vertices and their edges.
function setup() {
...
...
vertices[i] = new VertexDisjointSet(x, y);
point(x, y);
if (r > 0) {
edges.push(new Edge(vertices[i], vertices[i-gridSize]));
line(x, y, x, y-csize); // add vertical edge line
}
if (c > 0) {
edges.push(new Edge(vertices[i], vertices[i-1]));
line(x, y, x-csize, y); // add horizontal edge line
}
}
}
We started with a simple grid, now we have a graph with vertices and edges. Finally, we're ready to start building out the minimum spanning tree that will form our maze path.
The next part of the algorithm calls for traversing the minimal edges. At this point though our edges are not weighted and the distance between each vertex is the same, so we will introduce a random artifical weight to each edge—this will give the tree (i.e, our maze path) a more naturally non-uniform shape.
// update the Edge class
class Edge {
constructor(v1, v2) {
this.v1 = v1;
this.v2 = v2;
this.weight = Math.random();
}
}
Then we need to sort it so that we are always working with the minimal edge, we'll do descending order and just pop() off the end.
function setup() {
...
edges.sort((e1, e2) => {
if (e1.weight === e2.weight) return 0;
else if (e1.weight < e2.weight) return 1;
return -1;
});
}
Now for each edge we traverse, if it's vertices are not connected, we connect them, slowly expaning our spanning tree.
function setup() {
...
edges.sort(.....)
while (edges.length > 0) {
const edge = edges.pop();
const {v1, v2} = edge;
if (v1.find(v1) === v2.find(v2))
continue;
v1.union(v2);
}
}
Again to visualize, let's add a purple line for each connection.
function setup() {
...
edges.sort(.....)
stroke('purple'); // <-- draw connection as purple
while (edges.length > 0) {
const edge = edges.pop();
const {v1, v2} = edge;
if (v1.find(v1) === v2.find(v2))
continue;
v1.union(v2);
line(v1.x, v1.y, v2.x, v2.y); // <-- draw connection
}
}
The purple lines represent the minimum spanning tree (i.e, our maze path), the white lines with no purple lines crossing represent the walls. Let's turn off the original edge lines that are not connect (light blue lines), drawing only the connected edges (purple lines) for a better look at the spanning tree.
function setup() {
...
...
vertices[i] = new VertexDisjointSet(x, y);
point(x, y);
if (r > 0) {
edges.push(new Edge(vertices[i], vertices[i-gridSize]));
// line(x, y, x, y-csize);
}
if (c > 0) {
edges.push(new Edge(vertices[i], vertices[i-1]));
// line(x, y, x-csize, y);
}
}
}
The purple lines represent the minimum spanning tree (e.g. our maze path). If you look closely, you can see the tree spans to every vertex, thus every point on the corresponding maze path is access—a perfect maze.
We've just implemented Kruskal's algorithm, cool right? To finish off the maze generation, we simply remove all the vertex and edge lines and clear out the grid lines where ever there are connected vertices.
function setup() {
...
stroke(160); // same as background color
while (edges.length > 0) {
const edge = edges.pop();
const {v1, v2} = edge;
if (v1.find(v1) === v2.find(v2))
continue;
v1.union(v2);
if (v1.y == v2.y) {
const x = v2.x + cellmid;
const yoffset = (v2.y + cellmid-2) >= canvasSize ? 0 : 2;
line(x, v2.y-cellmid+2,
x, v2.y+cellmid-yoffset);
}
if (v1.x == v2.x) {
const y = v2.y + cellmid;
const xoffset = (v2.x + cellmid-2) >= canvasSize ? 0 : 2;
line(v2.x-cellmid+2, y,
v2.x+cellmid-xoffset, y);
}
}
}
With a little tweaking of the offsets for x and y, we end up with a maze.
Here's it scaled out with size 20.
function setup() {
const canvasSize = 400;
const gridSize = 20; // num of cells in grid
...
}
Now you know how to generate mazes with Kruskal's algorithm! Check out the p5js online editor to continue playing with the code we just walked through.
Source for this post and demo above can be found on GitHub.