So far, we've explored maze generation algorithms that are excellent for creating simple, grid-based mazes. However, the true power of algorithms lies in their ability to be generalized. Imagine needing to generate mazes that aren't just squares or rectangles, or mazes with different connectivity patterns. This is where the art of abstraction truly shines. We move from specific maze-building recipes to more general principles that can be applied to a wider range of structures and requirements.
One fundamental concept for generalization is viewing a maze not just as a collection of cells, but as a graph. Each cell can be considered a node, and a passage between two cells can be an edge. Most grid-based maze generation algorithms can be framed as creating a spanning tree on this graph. A spanning tree is a subgraph that includes all the vertices of the original graph and is a tree (i.e., it's connected and has no cycles). Since a maze by definition has no loops (except perhaps intentionally created ones for challenge), it's inherently a tree-like structure. Algorithms like Kruskal's or Prim's for finding Minimum Spanning Trees can be adapted for maze generation. Instead of minimizing weight, we're simply aiming to connect all nodes randomly.
graph TD
A[Cell A] -- Passage --> B[Cell B]
B -- Passage --> C[Cell C]
A -- Passage --> D[Cell D]
D -- Passage --> C
Consider Kruskal's algorithm adapted for maze generation: Start with all cells as separate sets. Randomly select a wall (potential edge). If the cells on either side of the wall belong to different sets, remove the wall (add the edge) and merge the sets. Repeat until all cells are in the same set. This naturally ensures connectivity without cycles. Prim's algorithm is similar, starting with a single cell and growing the maze by randomly adding adjacent cells connected by a passage.
class DisjointSet {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = Array(n).fill(0);
}
find(i) {
if (this.parent[i] === i) {
return i;
}
this.parent[i] = this.find(this.parent[i]);
return this.parent[i];
}
union(i, j) {
const rootI = this.find(i);
const rootJ = this.find(j);
if (rootI !== rootJ) {
if (this.rank[rootI] < this.rank[rootJ]) {
this.parent[rootI] = rootJ;
} else if (this.rank[rootI] > this.rank[rootJ]) {
this.parent[rootJ] = rootI;
} else {
this.parent[rootJ] = rootI;
this.rank[rootI]++;
}
return true;
}
return false;
}
}
function generateMazeKruskal(width, height) {
const cells = [];
for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
cells.push({ x, y });
}
}
const numCells = width * height;
const ds = new DisjointSet(numCells);
const walls = [];
// Collect all potential walls
for (let y = 0; y < height; y++) {
for (let x = 0; x < width; x++) {
if (x < width - 1) walls.push({ x1: x, y1: y, x2: x + 1, y2: y }); // Vertical wall
if (y < height - 1) walls.push({ x1: x, y1: y, x2: x, y2: y + 1 }); // Horizontal wall
}
}
// Shuffle walls randomly
walls.sort(() => Math.random() - 0.5);
const maze = Array(height).fill(null).map(() => Array(width).fill(0)); // 0 for path, 1 for wall
const passages = [];
for (const wall of walls) {
const cell1Index = wall.y1 * width + wall.x1;
const cell2Index = wall.y2 * width + wall.x2;
if (ds.union(cell1Index, cell2Index)) {
// Remove the wall by marking passage
passages.push(wall);
}
}
// Convert passages to a maze representation (simplified for illustration)
// A more complete representation would be needed to draw the maze
console.log("Generated passages:", passages);
return passages; // In a real maze generator, you'd build the grid from