When I set out to create a maze map for the , I initially expected to find a quick and easy way to accomplish this task. However, I quickly found myself immersed in the vast and fascinating world of mazes and labyrinths. Wall-E project I was unaware of the breadth and depth of this topic before. I discovered that mazes can be classified in seven different ways, each with numerous variations and countless for generating them. algorithms Surprisingly, I couldn't find any algorithmic books that comprehensively covered this topic, and even the didn't provide a systematic overview. Fortunately, I stumbled upon a fantastic resource that covers , which I highly recommend exploring. Wikipedia-page various maze types and algorithms I embarked on a journey to learn about the different classifications of mazes, including dimensional and hyperdimensional variations, perfect mazes versus unicursal labyrinths, planar and sparse mazes, and more. How to create a maze My primary goal was to generate a 2D map representing a maze. While it would have been enticing to implement various maze-generation algorithms to compare them, I also wanted a more efficient approach. The quickest solution I found involved randomly selecting connected cells. That's precisely what I did with . This one-file application creates a grid table of 20 x 20 cells and then randomly connects them using a Depth-First Search (DFS) traversal. In other words, we're simply carving passages in the grid. Mazerandom If you were to do this manually on paper, it would look something like this: To achieve this algorithmically, we apply Depth-First Search to the grid of cells. Let's take a look at how it's done in the . Main.cpp As usual, we represent the grid of cells as an array of arrays, and we use a stack for DFS: vector<vector<int>> maze_cells; // A grid 20x20
stack<Coord> my_stack;      // Stack to traverse the grid by DFS
my_stack.push(Coord(0, 0)); // Starting from very first cell We visit every cell in the grid and push its neighbors onto the stack for deep traversal: ...
while (visitedCells < HORIZONTAL_CELLS * VERTICAL_CELLS)
{
    vector<int> neighbours;
    // Step 1: Create an array of neighbour cells that were not yet visited (from North, East, South and West).
    // North is not visited yet?
    if ((maze_cells[offset_x(0)][offset_y(-1)] & CELL_VISITED) == 0) 
    {
        neighbours.push_back(0);
    }
    // East is not visited yet?
    if ((maze_cells[offset_x(1)][offset_y(0)] & CELL_VISITED) == 0) 
    {
        neighbours.push_back(1);
    }
    ... // Do the same for West and South... The most complex logic involves marking the node as reachable (i.e., no wall in between) with CELL_PATH_S, CELL_PATH_N, CELL_PATH_W, or CELL_PATH_E: ...
    // If we have at least one unvisited neighbour 
    if (!neighbours.empty()) 
    {
        // Choose random neighbor to make it available
        int next_cell_dir = neighbours[rand() % neighbours.size()];

        // Create a path between the neighbour and the current cell
        switch (next_cell_dir)
        {
        case 0: // North
            // Mark it as visited. Mark connection between North and South in BOTH directions.
            maze_cells[offset_x(0)][offset_y(-1)] |= CELL_VISITED | CELL_PATH_S;
            maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_N;
            // 
            my_stack.push(Coord(offset_x(0), offset_y(-1)));
            break;

        case 1: // East
            // Mark it as visited. Mark connection between East and West in BOTH directions.
            maze_cells[offset_x(1)][offset_y(0)] |= CELL_VISITED | CELL_PATH_W;
            maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_E;
            my_stack.push(Coord(offset_x(1), offset_y(0)));
            break;
        ... // Do the same for West and South...
        }
        visitedCells++;
    }
    else
    {
        my_stack.pop();
    }
... Finally, it calls the method to draw the maze on the screen using the SFML library. It draws a wall between two cells if the current cell isn't marked with CELL_PATH_S, CELL_PATH_N, CELL_PATH_W, or CELL_PATH_E. drawMaze However, this maze doesn't guarantee a solution. In many cases, it will generate a map with no clear path between two points. While this randomness might be interesting, I wanted something more structured. The only way to ensure a solution for the maze is to use a predetermined structure that connects every part of the maze in some way. Creating a Maze Using Graph Theory Well-known maze generation algorithms rely on graphs. Each cell is a node in the graph, and every node must have at least one connection to other nodes. As mentioned earlier, mazes come in many forms. Some, called "unicursal" mazes, act as labyrinths with only one entrance, which also serves as the exit. Others may have multiple solutions. However, the process of generation often starts with creating a "perfect" maze. A "perfect" maze, also known as a simply-connected maze, lacks loops, closed circuits, and inaccessible areas. From any point within it, there is precisely one path to any other point. The maze has a single, solvable solution. If we use a graph as the internal representation of our maze, constructing a ensures that there is a path from the start to the end. Spanning Tree In computer science terms, such a maze can be described as a over the set of cells or vertices. Spanning Tree Multiple Spanning Trees may exist, but the goal is to ensure at least one solution from the start to the end, as shown in the example below: The image above depicts only one solution, but there are actually multiple paths. No cell is isolated and impossible to reach. So, how do we achieve this? I discovered a well-designed codebase by that accomplishes this, generating mazes in SVG file format. mazegenerator @razimantv Therefore, I forked the repository and based my solution on it. Kudos to for the elegant OOP design, which allowed me to customize the results to create visually appealing images using the SFML library or generate a text file with the necessary map description for my . @razimantv Wall-E project I refactored the code to remove unnecessary components and focus exclusively on rectangular mazes. However, I retained support for various algorithms to build a spanning tree. I also added comments throughout the codebase for easier comprehension, so I don't need to explain it in every detail here. The main pipeline can be found in : \mazegenerator\maze\mazebaze.cpp /**
 * \param algorithm Algorithm that is used to generate maze spanning tree.
 */
void MazeBase::GenerateMaze(SpanningtreeAlgorithmBase* algorithm)
{
    // Generates entire maze spanning tree
    auto spanningTreeEdges = algorithm->SpanningTree(_verticesNumber, _edgesList);

    // Find a solution of a maze based on Graph DFS.
    _Solve(spanningTreeEdges);

    // Build a maze by removing unnecessary edges.
    _RemoveBorders(spanningTreeEdges);
} I introduced visualization using the SFML graphics library, thanks to a straightforward function. Draw While DFS is the default algorithm for creating a Spanning Tree, there are multiple algorithms available as options. The result is a handy utility that generates rectangular "perfect" mazes and displays them on the screen: As you can see, it contains exactly one input and one output at the left top and right bottom corners. The code still generates an SVG file, which is a nice addition (though it is the core function of the original codebase). Now, I can proceed with my experiments in the , and I leave you here, hoping that you're inspired to explore this fascinating world of mazes and embark on your own journey. Wall-E project Stay tuned! Also published . here

This story contains new, firsthand information uncovered by the writer.

Crafting Mazes With Graph Theory

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Algorithmic Wizardry: Exploiting Graph Theory in the Foreign Exchange

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Algorithmic Wizardry: Exploiting Graph Theory in the Foreign Exchange

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps