c++depth-first-searchmaze

Why is my DFS maze generation algorithm not working?

I have a DFS maze generation algorithm implementation in c++ that seems to consistently create multiple distinct areas. The maze is represented as a 2d vector of Node objects, which create a connected graph. print_maze prints nodes and their parents, which I have been using for debugging.

I am new to c++ but not to programming - I am sure this is a logic error but any help is appreciated.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>


class Node {
public:
    int x;
    int y;
    Node* parent;
    Node(int x, int y, Node* parent = nullptr) {
        this->x = x;
        this->y = y;
        this->parent = parent;
    };
};

std::vector<std::vector<Node*>> generate_full_maze(int columns, int rows) {
    std::vector<std::vector<Node*>> maze(columns, std::vector<Node*>(rows));

    for (int i = 0; i < columns; i++) {
        for (int j = 0; j < rows; j++) {
            maze[i][j] = new Node(i, j);
        }
    }

    return maze;
}


void print_maze(std::vector<std::vector<Node*>> maze) {
    for (int i = 0; i < maze.size(); i++) {
        for (int j = 0; j < maze[i].size(); j++) {
            // Print current cell and parent cell
            std::cout << maze[i][j]->x << "," << maze[i][j]->y << " ";
            if (maze[i][j]->parent != nullptr) {
                std::cout << "Parent: " << maze[i][j]->parent->x << "," << maze[i][j]->parent->y << std::endl;
            }
            else {
                std::cout << "Parent: None" << std::endl;
            }
        }
    }
};

bool is_visited(int x, int y, std::vector<Node*> visited) {    
    for (size_t i = 0; i < visited.size(); i++) {
        if (visited[i]->x == x && visited[i]->y == y) {
            return true;
        }
    }

    return false;
}

void carve_walls(int maxx, int maxy, std::vector<std::vector<Node*>> maze) {
    std::vector<Node*> visited;
    std::stack<Node*> stack;

    int x = 0;
    int y = 0;

    visited.push_back(maze[y][x]);
    stack.push(maze[y][x]);

    while (!stack.empty()) {
        Node* current_cell = stack.top();
        stack.pop();

        std::vector<Node*> neighbours;

        if (current_cell->x > 0) {
            neighbours.push_back(maze[current_cell->y][current_cell->x - 1]);
        }
        if (current_cell->x < maxx - 1) {
            neighbours.push_back(maze[current_cell->y][current_cell->x + 1]);
        }
        if (current_cell->y > 0) {
            neighbours.push_back(maze[current_cell->y - 1][current_cell->x]);
        }
        if (current_cell->y < maxy - 1) {
            neighbours.push_back(maze[current_cell->y + 1][current_cell->x]);
        }

        std::random_shuffle(neighbours.begin(), neighbours.end());

        for (size_t i = 0; i < neighbours.size(); i++) {
            if (!is_visited(neighbours[i]->x, neighbours[i]->y, visited)) {
                maze[neighbours[i]->y][neighbours[i]->x]->parent = current_cell;
                visited.push_back(neighbours[i]);
                stack.push(neighbours[i]);
            }
        }
    }
}

int main() {
    int x = 5;
    int y = 5;
    std::vector<std::vector<Node*>> maze = generate_full_maze(x, y);

    // Initialize the starting node
    Node* startNode = new Node(0, 0);
    maze[0][0] = startNode;

    carve_walls(x, y, maze);

    print_maze(maze);

    // Clean up maze memory
    for (int i = 0; i < y; i++) {
        for (int j = 0; j < x; j++) {
            delete maze[i][j];
        };
    };


    return 0;
}

I am expecting a complete maze where all Nodes are accessible, as following the stack implementation described at https://en.wikipedia.org/wiki/Maze_generation_algorithm#Iterative_implementation_(with_stack) but end up with a maze with multiple areas

Example output:

0,0 Parent: None
0,1 Parent: 0,0
0,2 Parent: 0,3
0,3 Parent: 0,2
0,4 Parent: 1,4
1,0 Parent: 0,0
1,1 Parent: 1,0
1,2 Parent: 0,2
1,3 Parent: 2,3
1,4 Parent: 0,4
2,0 Parent: 1,0
2,1 Parent: 2,2
2,2 Parent: 3,2
2,3 Parent: 2,4
2,4 Parent: 2,3
3,0 Parent: 4,0
3,1 Parent: 3,0
3,2 Parent: 2,2
3,3 Parent: 3,2
3,4 Parent: 2,4
4,0 Parent: 3,0
4,1 Parent: 4,2
4,2 Parent: 4,1
4,3 Parent: 4,2
4,4 Parent: 3,4

Which translates to a maze that looks like this (hand drawn): Hand drawn maze from above program output

Solution

  • There are two issues in your code:

    1. There is a mixup between x/y coordinates. In most of your code you consider y to be the row, i.e. the first dimension of your matrix, and x the column, i.e. the second dimension of your matrix. Except in the initialisation code where you have the inverse. You could correct that as follows:

      std::vector<std::vector<Node*>> generate_full_maze(int columns, int rows) {
    // first dimension is rows!:
    std::vector<std::vector<Node*>> maze(rows, std::vector<Node*>(columns));

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            maze[i][j] = new Node(j, i); // note the order of i and j
        }
    }

    return maze;
}

    2. When the algorithm finds an non-visited neighbor, it should push the current cell first back on the stack, and only then push the neighbor. Also, it should exit the inner loop and not push more neighbors: just that one only.

      Not a problem, but you can simplify the notion of "visited" by re-using the parent member for that purpose: whenever a node has a non-null parent, it means it has been visited. Only for the very first node you need a special treatment: make its parent a self-reference.

      Here is the adaptation to the relevant function:

      void carve_walls(int maxx, int maxy, std::vector<std::vector<Node*>> maze) {
    // No need of a separate visited vector
    std::stack<Node*> stack;

    int x = 0;
    int y = 0;

    maze[y][x]->parent = maze[y][x]; // self-reference
    stack.push(maze[y][x]);

    while (!stack.empty()) {
        Node* current_cell = stack.top();
        stack.pop();

        std::vector<Node*> neighbours;

        if (current_cell->x > 0) {
            neighbours.push_back(maze[current_cell->y][current_cell->x - 1]);
        }
        if (current_cell->x < maxx - 1) {
            neighbours.push_back(maze[current_cell->y][current_cell->x + 1]);
        }
        if (current_cell->y > 0) {
            neighbours.push_back(maze[current_cell->y - 1][current_cell->x]);
        }
        if (current_cell->y < maxy - 1) {
            neighbours.push_back(maze[current_cell->y + 1][current_cell->x]);
        }

        std::random_shuffle(neighbours.begin(), neighbours.end());

        for (size_t i = 0; i < neighbours.size(); i++) {
            if (!neighbours[i]->parent) { // easier check
                // Easier assignment:
                neighbours[i]->parent = current_cell;
                stack.push(current_cell); // push again!!
                stack.push(neighbours[i]);
                break; // Don't consider another neighbor now
            }
        }
    }
}

    Unrelated, but also take note of Why is std::random_shuffle method deprecated in C++14?