This article will outline the algorithm for random maze generation with backtracking and show code examples of the steps of the process. This algorithm is obviously useful for random maze generation, but the concepts can also be applied to other areas where random input or path generation is needed.
The basics of this algorithm are as follows
- Initialize an object to track nodes that are visited
- Generate the nodes in the maze. Generally you'll want to track the node's edges. You may also want to give the node an ID of some sort. If you want to cut down on recursive calls, you'll also want to track its possible edges (aka all its neighbors). You'll also want to store this as an object instead of an array as it speeds up lookup times.
- Choose a starting point in the maze
- Mark the node as visited
- while there are potential neighbors to visit
- Randomly select a possible edge to visit
- Add that node to the edges for the current node
- Add the current node as an edge on the selected node (note: if you're generating a DAG, you wouldn't do this step)
- Remove the selected node from the potential edges
- Recursively call the method to generate the path in the maze using the selected node
- Once there are no more neighbors to visit, return
These steps will generate an object that contains all the nodes in the graph with randomly selected edges to other nodes in the graph. It's guaranteed to have connections to all nodes and a single path through the maze.
Let's take a play by play using this algorithm. Say we are starting with a blank slate. We have a new set of nodes with no edges set yet. We'll start at position 0, 0 (the top left of the maze) and start building connections. The maze could look something like this.
Starting from the upper-left, we'll examine that node's possible neighbors. That node will have two potential neighbors: position 1, 0 and position 0, 1. All other nodes are not potential neighbors for the starting node. We'll randomly select one of those neighbors. Let's say we select position 0, 1. We'll check to make sure we haven't visited that node. Unsurprisingly, we'll find we haven't visited it, so we're good to proceed. By choosing this node, it means we'll move down one node in the above graph. Before we visit that node, we'll add it to the starting node's edges and remove it from its neighbors. We'll also add the current node as an edge to that node.
We then visit the node at position 0, 1. We'll mark the node as visited and get the list of its neighbors. We'll randomly choose one and check if we've visited it. Let's say we choose position 0, 0. When we check if we've visited that node, it will come back as true which means we won't move to that node. Instead, we'll select another node. Let's say we choose position 1, 1. We'll see that we haven't visited this node, so we'll add it as an edge to the current node, add the current node as an edge to the new node, remove the new node as a neighbor for the current node, then repeat this process again for the new node.
This process will repeat until the algorithm reaches a dead end. When this occurs and there are no more neighbors for it to visit, it will return and make its way back up the call stack until it reaches a node that has neighbors that haven't yet been visited. Once it finds a node that has an unvisited neighbor, it then continues with the algorithm again until it reaches a dead end. In the end, you'll end up with a maze.
Here is the JavaScript code to generate the maze:
const generateMaze = (height, width) => {
let maze = {}; // Initialize an empty object to build the maze in
// Loop over the entire height and width
for (let y = 0; y < width; y++) {
for (let x = 0; x < height; x++) {
// Create an object with a unique key in the maze object and store things of interest.
// Mostly care about edges and potential edges, but can store othes things as needed.
maze[_Position(x, y)] = {id: `${x}.${y}`, position: [x, y], weight: 0, edges: [], potentialEdges: []};
}
}
// Loop over the whole maze again to get potential edges
for (let y = 0; y < width; y++) {
for (let x = 0; x < height; x++) {
// Helper for the current node
let p = _Position(x, y);
for (let x2 = -1; x2 <= 1; x2++) {
for (let y2 = -1; y2 <= 1; y2++) {
// A little math to make sure we're only moving left, right, up, or down
if ((x2 === 0 && y2 === 0) || (Math.abs(x2) + Math.abs(y2) !== 1)) {
continue;
}
// Helper for the potential neighbor
let p2 = _Position(x + x2, y + y2);
// If it is a node in the maze...
if (p2 in maze) {
// It's a valid potential edge and ew can add it
maze[p].potentialEdges.push(p2);
}
}
}
}
}
// We'll get to this in a moment. This method generates the path in the maze.
maze = generateMazePath(maze, _Position(0, 0));
return maze; // Return the generated maze
};
Once the maze is generated, we'll have an object that has nodes. Each node will have a list of potential edges (neighbors) and an empty list of connected edges (neighbors it's connected to on a path). If we were to visualize this maze, it would be like the first image above with a bunch of cells all walled in with no connections to other nodes. So, with this set up out of the way, we can now consider the actual algorithm to generate the path through the maze.
const generateMazePath = (maze, currentPosition) => {
// (this variable is initialized in a higher scope to an empty object)
visited[currentPosition] = true; // Mark the current node as visited
const node = maze[currentPosition]; // Get a reference to the node
const neighbors = [...node.potentialEdges]; // Copy all potential edges (all neighbors)
while (neighbors.length > 0) { // While there are neighbors remaining to visit
const nextPosition = RandomEdge(neighbors); // Choose a neighbor to visit at random
if (!(nextPosition in visited)) { // If we haven't visited the chosen neighbor
const adjacentNode = maze[nextPosition]; // Get a reference to that node
node.edges.push(nextPosition); // Add a connection to the chosen node from the current node
adjacentNode.edges.push(currentPosition); // Add a connection to the current node from the chosen node
generateMazePath(maze, nextPosition); // Move to the chosen node and repeat the process
}
}
return maze; // When all nodes are visited, return the updated objects
// Because JS is pass by reference for non-primitive types, the updates we make to the nodes
// in the code above are automatically reflected in the maze object itself.
};
The above method will traverse the entire maze generated in the previous method. It will visit every node and connect it to other nodes in such a way that it forms a path to every node in the maze. Because we're only visiting neighboring cells and we're ensuring we visit all neighboring cells, we can guarantee that all cells will be connected to neighboring cells in such a way that a path is formed through the entire maze.
One thing I think is amazing about this (and most algorithms) is how simple it really is. Before learning this algorithm, the problem seemed somewhat complicated. But after thinking about it and walking through it, it became much simpler. Then when researching the algorithm, it became even more clear and easy to understand.
The next time I revisit this project, I'll be implementing the A* algorithm which is used widely in pathfinding problems such as navigation like Google Maps or moving characters in video games.
Comments
Post a Comment