In this blog post, we’ll explore the principles behind the mazes we commonly encounter and examine the process of generating mazes using the depth-first search (DFS) algorithm.
Most of us have probably tried solving a “maze” hidden in a magazine or newspaper at least once. Complex and challenging mazes can be frustrating to solve, but reaching the end brings a great sense of accomplishment. However, whenever we’ve seen a maze, we’ve always focused on how to solve it. Conversely, what principles are actually used to create these complex and challenging mazes?
One of the simplest ways to create a maze is to use the “Depth-First Search (DFS)” algorithm, a graph traversal method. To briefly explain graphs and graph traversal, a graph is a data structure that structurally represents the relationships between various objects. A graph consists of nodes and edges; nodes can store data, and edges represent the connections between nodes. In other words, graph traversal refers to moving between nodes along edges to find a specific node or to examine the structure of the graph. The DFS algorithm, one such graph traversal method, starts from the root node of the graph, explores a path as deeply as possible, and when it can no longer reach an unvisited node, backtracks to the previous node to explore another path.
To understand how the DFS algorithm can generate a maze, let’s briefly explain its basic principles. To make it easier to understand, let’s assume that each node in the graph is a “room” and that these rooms are connected to one another via the graph’s edges. The rules of the DFS algorithm based on these assumptions are as follows.
Rule a. Select a target room from among the rooms in the graph and choose a starting point at random. In some cases, the starting point is predetermined.
Rule b. Move to an unvisited room that is connected to the current room.
Rule c. If you have visited all rooms connected to the current room, return to the room you were in immediately before.
Rule d. If the target room is visited during the search, terminate the search.
Using these four rules, you can traverse the graph using the DFS algorithm. DFS works by following unvisited adjacent nodes as deeply as possible and then returning to the previous step when no further progress is possible.
Now, let’s explain how to apply the DFS algorithm to the graph above. First, according to Rule a, we set Room 6 as the destination and decide to start from Room 1. According to Rule b, we move from the starting point, Room 1, to Room 2, which is adjacent to Room 1 and has not yet been visited. After continuing on to Room 4, we have now visited all rooms adjacent to Room 4, including Room 3, so we must follow Rule c. Therefore, we return to Room 3—the room we visited most recently—and move to Room 5, which has not yet been visited. By applying the same rule, we will soon reach Room 6. In this way, as we move by applying the rules of the DFS algorithm, we will eventually visit the target room, and the search will end successfully.
Now that we’ve learned the DFS algorithm, let’s apply it to create a maze. The first thing to decide is the goal to be found using the DFS algorithm. Typically, when traversing a graph, the main goal is to reach a specific node, but when creating a maze, the goal should be to explore every room. After setting the goal, determine the size of the maze and create rooms within it that are completely blocked by walls. Here, we’ll create a draft of a 4×4 maze. Next, following Rule a, we’ll select a starting point. Then, according to Rule b, we must choose an adjacent room that hasn’t been visited yet and move to it. The key point here is that since we’re building a “maze,” we must always choose our direction of movement at random so that the path cannot be predicted. Therefore, we’ll randomly select north, move to the room to the north, and then remove the northern wall corresponding to the path we took. For convenience, we’ll color visited rooms yellow as shown in the diagram as we move. Following the same rules, moving west leads to the next scenario, and moving south leads to yet another scenario. After repeating the above process a few more times, you’ll reach a situation where the current room and all surrounding rooms have been visited. At this point, if the current room is red and all surrounding rooms are yellow (indicating they’ve been visited), you must return to the previous room according to rule c and then move to another unvisited room according to rule b. Since the goal of creating a maze is not to reach a specific room but to visit every room, the search ends once all rooms are colored yellow after repeating the previous steps. Finally, after the DFS algorithm completes its search, a maze is completed by creating the starting point and destination at appropriate locations.
The DFS algorithm works by following a path deeply into the graph during the search and backtracking to the previous step if it encounters a dead end. Therefore, stacks or recursive calls can be used to manage the current path and search state, and in general graph traversal, a data structure that records whether a node has been visited is also used. The time complexity of DFS is O(V+E) based on the standard adjacency list representation, where V represents the number of nodes and E represents the number of edges. Furthermore, while DFS has the advantage of being able to explore a specific path first if it is located deep within the graph, it does not guarantee the shortest path to the target node. Therefore, if the goal is to find the shortest path in a problem where the target can be reached via multiple paths, DFS alone may not be sufficient. Furthermore, if the goal does not exist or the selected path is very deep, it may take a long time to check other paths; in the worst case, all searchable nodes and edges must be checked. Thus, DFS can be described as an algorithm that, while offering the advantage of performing deep searches with minimal space, also has the limitation that, depending on the search order, the goal may be discovered late or the shortest path may not be guaranteed.
