The Maze In C++

Introduction:

A labyrinth in C++ commonly denotes a software or algorithm crafted for constructing, exploring, or resolving a maze. Mazes present captivating challenges for computational puzzle-solving, frequently featuring grid-based arrangements with barriers, passages, and an initial and final destination. Developing a maze in C++ utilizes essential programming principles like arrays or vectors for depicting the grid, and techniques such as depth-first search (DFS) or breadth-first search (BFS) for traversal or resolution of the maze.

The first step is to establish the layout of the maze. Typically, this involves using a two-dimensional array where individual cells can either represent walls or pathways. Algorithms such as Recursive Backtracking, Prim's, or Kruskal's are commonly utilized for maze generation to guarantee the development of a solvable maze with an unbroken path from the beginning to the end. Upon creation, navigating the maze requires determining a route across the grid, employing algorithms like Depth-First Search (DFS), Breadth-First Search (BFS), or A* algorithm.

Approach 1: Implementation Maze in C++

Program:

#include <iostream>
#include <vector>
#include <stack>
#include <cstdlib>
#include <ctime>
const int WIDTH = 10;
const int HEIGHT = 10;
enum Cell {
    WALL,
    PATH,
    START,
    END
};
struct Position {
    int x, y;
};
std::vector<std::vector<Cell>> createMaze(int width, int height) {
    std::vector<std::vector<Cell>> maze(height, std::vector<Cell>(width, WALL));
    std::stack<Position> stack;
    Position current{1, 1};
    stack.push(current);
    maze[current.y][current.x] = PATH;
    while (!stack.empty()) {
        std::vector<Position> neighbors;
        if (current.x > 1 && maze[current.y][current.x - 2] == WALL)
            neighbors.push_back({current.x - 2, current.y});
        if (current.x < width - 2 && maze[current.y][current.x + 2] == WALL)
            neighbors.push_back({current.x + 2, current.y});
        if (current.y > 1 && maze[current.y - 2][current.x] == WALL)
            neighbors.push_back({current.x, current.y - 2});
        if (current.y < height - 2 && maze[current.y + 2][current.x] == WALL)
            neighbors.push_back({current.x, current.y + 2});
        if (!neighbors.empty()) {
            Position next = neighbors[rand() % neighbors.size()];
            stack.push(next);
            maze[(current.y + next.y) / 2][(current.x + next.x) / 2] = PATH;
            maze[next.y][next.x] = PATH;
            current = next;
        } else {
            current = stack.top();
            stack.pop();
        }
    }
    maze[1][1] = START;
    maze[height - 2][width - 2] = END;
    return maze;
}
bool solveMaze(std::vector<std::vector<Cell>>& maze, Position current, std::vector<Position>& path) {
    if (current.x < 0 || current.x >= WIDTH || current.y < 0 || current.y >= HEIGHT)
        return false;
    if (maze[current.y][current.x] == WALL || maze[current.y][current.x] == START)
        return false;
    if (maze[current.y][current.x] == END) {
        path.push_back(current);
        return true;
    }
    maze[current.y][current.x] = START; // Mark as part of the solution path
    static const std::vector<Position> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    for (const auto& dir : directions) {
        Position next{current.x + dir.x, current.y + dir.y};
        if (solveMaze(maze, next, path)) {
            path.push_back(current);
            return true;
        }
    }
    maze[current.y][current.x] = PATH; // Unmark if it is not the solution path
    return false;
}
void printMaze(const std::vector<std::vector<Cell>>& maze) {
    for (const auto& row : maze) {
        for (const auto& cell : row) {
            if (cell == WALL)
                std::cout << "#";
            else if (cell == PATH)
                std::cout << " ";
            else if (cell == START)
                std::cout << "S";
            else if (cell == END)
                std::cout << "E";
        }
        std::cout << std::endl;
    }
}
int main() {
    srand(time(nullptr));
    std::vector<std::vector<Cell>> maze = createMaze(WIDTH, HEIGHT);
    std::cout << "Generated Maze:" << std::endl;
    printMaze(maze);
    std::vector<Position> path;
    if (solveMaze(maze, {1, 1}, path)) {
        std::cout << "\nSolved Maze:" << std::endl;
        for (const auto& pos : path) {
            maze[pos.y][pos.x] = START;
        }
        maze[1][1] = START;
        maze[HEIGHT - 2][WIDTH - 2] = END;
        printMaze(maze);
    } else {
        std::cout << "\nNo solution found." << std::endl;
    }
    return 0;
}

Output:

Generated Maze:
##########
#S#       
# ##### # 
#   #   # 
### # ### 
# # #   # 
# # ### # 
# #   # # 
# ### # E 
#       # 
No solution found.

Explanation:

• ✅ Initialization:

The maze is depicted as a two-dimensional grid containing cells that can either be walls or pathways. The size of the maze is determined by the constants WIDTH and HEIGHT.

The maze begins with every cell designated as barriers.

• ✅ Algorithm Selection:

The maze is created through the Recursive Backtracking technique. This approach employs a stack to maintain the current location and adjacent cells.

• ✅ Initial Position:

The initial starting point is usually selected at the coordinates (1, 1) and is designated as the starting point for initiating the maze generation process.

• ✅ Creating Pathways:

The procedure involves selecting a current cell in a step-by-step manner, followed by a random selection of an adjacent unvisited cell that is precisely two steps away to guarantee the creation of pathways separated by walls.

It eliminates the barrier between the present cell and the selected adjacent cell, effectively creating a passage.

The selected adjacent cell becomes the current cell, initiating the repetition of this process. In case there are no unexplored neighboring cells, the algorithm retraces its steps back to the preceding cell by utilizing the stack until it locates a cell with unvisited neighbors.

• ✅ Finishing the Maze:

The procedure persists until every cell is explored, guaranteeing that the complete grid transforms into a unified maze.

The beginning and conclusion coordinates are clearly designated, typically at (1, 1) for the starting point and (width-2, height-2) for the endpoint.

Maze Solving

• ✅ Initialization:

The solver implements a recursive depth-first search (DFS) strategy to locate a route from the initial point to the final destination.

The initial location is identified, and the algorithm endeavors to explore in all four potential directions (up, down, left, right) starting from the current cell.

• ✅ Exploration for Paths:

For every action, the algorithm verifies if it falls within the boundaries of the maze and if it directs to either an unexplored route or the final cell.

If the endpoint is reached in the grid, it signifies the discovery of a viable path, and the current coordinates are appended to the solution pathway.

• ✅ Backtracking:

If a move fails to result in a solution, the algorithm backtracks by reassigning the cell as a path and proceeds with exploring the following potential direction.

This process of backtracking persists until either a valid route to the conclusion is discovered or all potential options have been tried.

• ✅ Indication of Resolution:

Once a path to the solution is determined, it is highlighted within the maze. The cells along this path are distinctly marked, typically by altering their status to signify their inclusion in the solution.

Output

• ✅ Maze Display:

The console displays the maze twice, first in its unsolved state and then after being solved. During the initial display, walls are denoted by a designated symbol like '#' while paths are indicated by blank spaces. Additionally, the starting point is marked with 'S' and the endpoint with 'E'.

• ✅ Resolved Maze:

Once the solver completes the task, the identified path is showcased on the maze, illustrating a direct pathway from the initial point to the final destination.

Complexity Analysis:

Time Complexity

Maze Generation:

The time complexity associated with constructing the maze through the Recursive Backtracking technique is O(W * H), with W representing the width and H denoting the height of the maze. This is due to the fact that every cell within the maze is explored once to establish pathways.

Maze Solving:

The computational complexity of navigating the maze with the Depth-First Search (DFS) technique is O(W * H). This arises from the requirement to potentially traverse every cell under the most unfavorable scenario to locate the route from the initial point to the destination.

Space Complexity

Maze Generation:

The maze creation process requires O(W * H) space complexity to store the maze grid.

The stack employed for backtracking has the capacity to store a maximum of O(W * H) cells in the scenario where each cell is added to the stack prior to commencing the backtracking process.

Maze Solving:

The space efficiency for navigating the maze is O(W * H) concerning the storage of the path.

Moreover, the recursive function stack for Depth-First Search (DFS) has the potential to reach a depth of O(W + H) in the most unfavorable scenario, usually equivalent to O(W * H) when dealing with grid-based mazes.

Approach 2: Using Prim's Algorithm for Maze Generation

Introduction:

Prim's algorithm is a well-known method initially employed to determine the minimum spanning tree within a graph with weights. Nonetheless, it can be modified to produce mazes by considering the maze as an undirected graph, with each cell acting as a node and each wall separating cells serving as an edge. The algorithm guarantees the creation of a flawless maze, ensuring the absence of loops and establishing a singular distinct route between any pair of points.

Program:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <set>
const int WIDTH = 10;
const int HEIGHT = 10;
enum Cell {
    WALL,
    PATH,
    START,
    END
};
struct Position {
    int x, y;
};
std::vector<std::vector<Cell>> createMaze(int width, int height) {
    std::vector<std::vector<Cell>> maze(height, std::vector<Cell>(width, WALL));
    std::set<std::pair<int, int>> frontier;
    auto addFrontier = [&](int x, int y) {
        if (x >= 1 && x < width - 1 && y >= 1 && y < height - 1 && maze[y][x] == WALL) {
            frontier.insert({x, y});
        }
    };
    srand(time(nullptr));
    Position start = {1, 1};
    maze[start.y][start.x] = PATH;
    addFrontier(start.x, start.y);
    while (!frontier.empty()) {
        auto it = frontier.begin();
        std::advance(it, rand() % frontier.size());
        Position current = {it->first, it->second};
        frontier.erase(it);
        std::vector<Position> neighbors;
        if (maze[current.y - 2][current.x] == PATH) neighbors.push_back({current.x, current.y - 2});
        if (maze[current.y + 2][current.x] == PATH) neighbors.push_back({current.x, current.y + 2});
        if (maze[current.y][current.x - 2] == PATH) neighbors.push_back({current.x - 2, current.y});
        if (maze[current.y][current.x + 2] == PATH) neighbors.push_back({current.x + 2, current.y});
        if (!neighbors.empty()) {
            Position neighbor = neighbors[rand() % neighbors.size()];
            maze[(current.y + neighbor.y) / 2][(current.x + neighbor.x) / 2] = PATH;
            maze[current.y][current.x] = PATH;
            addFrontier(current.x + 2, current.y);
            addFrontier(current.x - 2, current.y);
            addFrontier(current.x, current.y + 2);
            addFrontier(current.x, current.y - 2);
        }
    }
    maze[1][1] = START;
    maze[height - 2][width - 2] = END;
    return maze;
}
void printMaze(const std::vector<std::vector<Cell>>& maze) {
    for (const auto& row : maze) {
        for (const auto& cell : row) {
            if (cell == WALL)
                std::cout << "#";
            else if (cell == PATH)
                std::cout << " ";
            else if (cell == START)
                std::cout << "S";
            else if (cell == END)
                std::cout << "E";
        }
        std::cout << std::endl;
    }
}
int main() {
    std::vector<std::vector<Cell>> maze = createMaze(WIDTH, HEIGHT);
    std::cout << "Generated Maze:" << std::endl;
    printMaze(maze);
    return 0;
}

Output:

Generated Maze:
##########
#S########
##########
##########
##########
##########
##########
##########
########E#
##########

Explanation:

• ✅ Initialization:

Begin with a grid where every cell is a wall.

Select a random initial cell and designate it as a section of the maze by transforming it from a solid barrier to a passageway.

• ✅ Frontier List:

Manage a collection of frontier cells, which are neighboring cells to those that have been transformed into paths but are still considered walls.

• ✅ Identifying Frontier Cells:

Randomly select a cell from the frontier list.

This arbitrary selection guarantees that the maze possesses a less predictable and diverse layout.

• ✅ Linking Cells:

Identify the adjacent cells to the chosen frontier cell that have already been transformed from walls to pathways within the maze.

If the chosen cell has precisely one adjacent cell that forms part of the maze, eliminate the barrier between them. This step transforms the selected cell into a pathway and links it to the current maze.

• ✅ Modifying the List of Frontier Cells:

Designate the chosen frontier cell as a component of the maze.

Add the recently neighboring wall cells to the frontier collection since they are now neighboring the newly transformed path cell and have the potential to be transformed subsequently.

• ✅ Iterate the process:

Repeat the procedure of choosing a random frontier cell, linking it to the maze, and refreshing the frontier list until all cells are integrated into the maze.

Complexity Analysis:

Time Complexity

The time complexity of generating a maze using Prim's algorithm is O(W * H), with W representing the maze's width and H representing its height. This is due to the fact that each cell within the maze is examined and handled only once.

Space Complexity

The storage space required for the maze grid is O(W H) in terms of space complexity. The frontier list (or set) has the potential to contain a maximum of O(W H) cells at its peak, although in reality, this number tends to be significantly lower due to the continuous addition and removal of cells. Consequently, the total space complexity continues to be O(W * H).

Approach 3: Using Kruskal's Algorithm for Maze

Kruskal's technique for creating mazes relies on constructing a minimum spanning tree (MST) within the maze layout. Initially, each cell in the maze is separate, and the walls between neighboring cells act as the graph's edges. The algorithm proceeds by randomly picking edges (representing walls) and including them in the maze only if they do not create a cycle. This process repeats until all cells are linked together. The outcome is a maze devoid of loops or disconnected areas, guaranteeing a single pathway between any pair of points within the maze.

Program:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
const int WIDTH = 10;
const int HEIGHT = 10;
struct Edge {
    int cell1, cell2;
};
std::vector<int> parent;
int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    parent[rootX] = rootY;
}
std::vector<Edge> generateEdges(int width, int height) {
    std::vector<Edge> edges;
    for (int y = 1; y < height - 1; ++y) {
        for (int x = 1; x < width - 1; ++x) {
            edges.push_back({y * width + x, y * width + x + 1});
            edges.push_back({y * width + x, (y + 1) * width + x});
        }
    }
    std::random_shuffle(edges.begin(), edges.end());
    return edges;
}
std::vector<std::vector<char>> createMaze(int width, int height) {
    std::vector<std::vector<char>> maze(height, std::vector<char>(width, '#'));
    parent.resize(width * height);
    for (int i = 0; i < width * height; ++i) parent[i] = i;
    std::vector<Edge> edges = generateEdges(width, height);
    for (const auto& edge : edges) {
        int cell1 = edge.cell1;
        int cell2 = edge.cell2;
        if (find(cell1) != find(cell2)) {
            unite(cell1, cell2);
            if (cell2 - cell1 == 1) maze[cell1 / width][cell1 % width] = ' ';
            else maze[cell2 / width][cell2 % width] = ' ';
        }
    }
    return maze;
}
void printMaze(const std::vector<std::vector<char>>& maze) {
    for (const auto& row : maze) {
        for (char cell : row) std::cout << cell;
        std::cout << std::endl;
    }
}
int main() {
    srand(time(nullptr));
    std::vector<std::vector<char>> maze = createMaze(WIDTH, HEIGHT);
    std::cout << "Generated Maze:" << std::endl;
    printMaze(maze);
    return 0;
}

Output:

Generated Maze:
##########
# #      #
# #    # #
## #  ## #
#        #
#        #
# ##     #
#        #
#   # #  #
#        #

Explanation:

• ✅ Disjoint Set Data Structure:

A Disjoint Set Data Structure, also known as a Union-Find Data Structure, is utilized to efficiently manage a collection of disjoint sets.

The algorithm employs a disjoint set data structure to handle sets of connected cells, with each set denoting a separate component within the maze.

• ✅ Union and Find Operations:

The find operation identifies the root (representative) of a set by recursively navigating parents.

The unite operation combines two sets by assigning the root of one set as the parent of the root of the other set.

• ✅ Creating Edges:

The generate edges function generates a collection of edges (representing walls) that connect neighboring cells within the maze grid.

Edges are depicted using pairs of cell indexes.

• ✅ Generating a Maze:

The createMaze function sets up the maze grid by assigning walls ('#') to each cell and establishing separate sets for individual cells.

It cycles through the randomized list of edges, aiming to merge the groups of cells linked by each edge.

If the sets are separate, signifying that introducing the edge does not lead to a cycle, the edge gets included in the maze by eliminating the barrier between the cells.

The labyrinth is systematically built, guaranteeing connections while avoiding circular paths.

• ✅ Displaying the Maze:

The printMaze function displays the maze grid created on the console, using '#' to symbolize walls and spaces to represent paths.

Complexity Analysis:

Time Complexity

The time complexity of Kruskal's algorithm for generating mazes relies on the sorting of edges and the operations performed by the union-find data structure:

Sorting the edges in edge sorting usually requires O(E log E) time complexity, with E representing the total count of edges present within the maze grid.

Performing union-find operations for every edge requires around O(E α(V)) time, where V represents the quantity of nodes (vertices), and α stands for the inverse Ackermann function, which increases at an extremely gradual pace and is essentially stable for real-world applications.

The arrangement of edges plays a significant role in determining the total time complexity, usually around O(E log E).

Space Complexity

The main factor contributing to the space complexity of Kruskal's algorithm is the storage required for both the maze grid and the disjoint set data structure:

The maze grid itself consumes O(W * H) memory space, with W representing the width and H representing the height of the maze.

The disjoint set data structure utilizes O(W * H) space to store the parents and sizes of sets.

Hence, the overall space complexity is O(W * H).

Properties:

• ✅ Connectivity:

A linked maze guarantees the presence of a pathway from the starting point to the endpoint, ensuring accessibility to all cells from any location. This characteristic is vital to ensure the solvability of the maze and avoid isolated areas that might obstruct movement.

• ✅ Distinctiveness:

Uniqueness in maze creation suggests that every maze generated is different from the rest, offering a fresh challenge or adventure for users. While absolute uniqueness may not be possible or crucial, reducing duplicates increases the attraction and diversity of the mazes generated.

• ✅ Complexity:

The intricacy of a maze includes elements like wall density, dead-end frequency, path branching, and size. A maze with higher complexity usually presents a tougher puzzle to crack, demanding more thorough exploration and strategic thinking from the solver.

• ✅ Solvability:

Ensuring solvability guarantees the presence of a valid route from the maze's beginning to its end. While certain scenarios might incorporate unsolvable mazes as a challenge, confirming solvability is essential for maze-solving algorithms to generate valuable outcomes.