### Perfect Maze algorithm

I've been trying to make a small maze generator to display a maze on the screen. It goes through the algorithm and displays a maze, but it's only changing some of the cells. I've been trying to trouble shoot and not finding anything that I think is wrong, but assume it's in my function calls.

This is my algorithm:
 Create constants (ROWS, COLS) to store the size of the maze. Create an enum named DIR to keep track of the four directions (NORTH, EAST, SOUTH, WEST) Randomize the random number function. Create a 2-D array ([ROWS][COLS]) of Cell objects. For each Cell in the maze: set visited to false set its position to its row and column in the maze set the Cell's walls to Cell::WALL_ALL Create curX and curY variables and set them to a random position in the maze. Create a vector of Cell objects named trail which will be used as a stack. Create a vector of DIR values named live. Grab the Cell at the curX, curY position and push it on the trail stack. While the trail stack is not empty do the following: Empty the live vector. Check the neighbors of the current cell to the north, east, south, and west. If any of the neighbors have all four walls, add the direction to that neighbor to the live vector. If the live vector is not empty: Choose one of the directions in the live vector at random Remove the walls between the current cell and the neighbor in that direction Change curX and curY to refer to the neighbor Push the new current cell onto the trail stack If the live vector was emtpy: Pop the top item from the trail stack If the trail stack is not empty, set curX and curY to refer to the position of the top item in the trail stack.

I've got a class structure that I set up for each cell, but the real code is this:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129`` ``````#include "Cell.h" #include #include #include #include using std::cout; using std::vector; // Create constants (ROWS, COLS) to store the size of the maze. const int ROWS = 20; const int COLS = 20; // Create an enum named DIR to keep track of the four directions (NORTH, EAST, SOUTH, WEST) enum DIR { NORTH, SOUTH, EAST, WEST }; int main(void){ // variables int ran_dir; // Randomize the random number function. srand(time(NULL)); // Create a 2-D array ([ROWS][COLS]) of Cell objects. Cell maze[ROWS][COLS]; // For each Cell in the maze: for(int row = 0; row < ROWS; row++) for(int col = 0; col < COLS; col++) { // set visited to false maze[row][col].setVisited(false); // set its position to its row and column in the maze maze[row][col].setPosition(row, col); // set the Cell's walls to Cell::WALL_ALL maze[row][col].setWalls(Cell::WALL_ALL); } //Create curX and curY variables and set them to a random position in the maze. int curX = rand() % ROWS; int curY = rand() % COLS; // Create a vector of Cell objects named trail which will be used as a stack. vector trail; // Create a vector of DIR values named live. vector live; // Grab the Cell at the curX, curY position and push it on the trail stack. trail.push_back(maze[curX][curY]); // While the trail stack is not empty do the following: while(trail.empty()==false) { // stay in here till display // Empty the live vector. live.clear(); // Check the neighbors of the current cell to the north, east, south, and west. // If any of the neighbors have all four walls, add the direction to that // neighbor to the live vector. if(curY) if(maze[curX][curY-1].getWalls()==Cell::WALL_ALL) // West has all walls live.push_back(WEST); if(curY

Cell implementation:
cell.h
 ``1234567891011121314151617181920212223242526272829303132`` ``````#ifndef __CELL_H_ #define __CELL_H_ #include #include class Cell { private: int row; int col; bool visit; int walls; void init(const int r, const int c, const int walls, const bool v = false); public: enum WALL { WALL_NORTH = 0x0008, WALL_EAST = 0x0004, WALL_SOUTH = 0x0002, WALL_WEST = 0x0001, WALL_ALL = 0x000f, WALL_NONE = 0x0000 }; Cell(); Cell(const int r, const int c); Cell(const int r, const int c, const int stat); bool visited() const; void setVisited(const bool v = true); int getRow() const; int getColumn() const; void removeWall(const int w); int getWalls() const; void setWalls(const int w); void setPosition(const int r, const int c); friend std::ostream& operator<<(std::ostream& strm, const Cell& c); }; #endif ``````

cell.cpp
 ``1234567891011121314151617181920212223242526272829303132333435363738`` ``````#include "Cell.h" #include #include #include #include void Cell::init(const int r, const int c, const int walls, const bool v) { setPosition(r, c); setWalls(walls); setVisited(v); } Cell::Cell() { init(0, 0, 0); } Cell::Cell(const int r, const int c) { init(r, c, 0); } Cell::Cell(const int r, const int c, const int walls) { init(r, c, walls); } bool Cell::visited() const { return visit; } void Cell::setVisited(const bool v) { visit = v; } int Cell::getRow() const { return row; } int Cell::getColumn() const { return col; } void Cell::removeWall(const int w) { if (w!=WALL_NORTH && w!=WALL_EAST && w!=WALL_SOUTH && w!=WALL_WEST) throw std::string("Illegal wall argument"); walls &= ~w; } int Cell::getWalls() const { return walls & WALL_ALL; } void Cell::setWalls(const int w) { walls = w & WALL_ALL; } void Cell::setPosition(const int r, const int c) { row = r; col = c; } std::ostream& operator<<(std::ostream& strm, const Cell& c) { if ((c.getWalls() & Cell::WALL_WEST) != 0) strm << '|'; else strm << ' '; if ((c.getWalls() & Cell::WALL_SOUTH) != 0) strm << '_'; else strm << ' '; return strm; }``````

Any help figuring out where I'm doing something wrong would be greatly appreciated. I tried to comment the code to where it would be easy to see what I was trying to do.

I have not looked at your code in depth, but one thing did occur to me. How do you handle the fact that the east wall in cell (0,0) is the same wall as the west wall of cell (1,0) [etc, etc, etc, etc]?
That's a good point, I need to add in the functionality to remove both of them and not just the one in the current cell. Going to go make that modification.
Yer a genious :)

I changed the code to this and it works:
 ``12345678910111213141516`` `````` case 0: maze[curX][curY].removeWall(Cell::WALL_NORTH); maze[--curX][curY].removeWall(Cell::WALL_SOUTH); break; case 1: maze[curX][curY].removeWall(Cell::WALL_SOUTH); maze[++curX][curY].removeWall(Cell::WALL_NORTH); break; case 2: maze[curX][curY].removeWall(Cell::WALL_EAST); maze[curX][++curY].removeWall(Cell::WALL_WEST); break; case 3: maze[curX][curY].removeWall(Cell::WALL_WEST); maze[curX][--curY].removeWall(Cell::WALL_EAST); break;``````

Thanks so much :)
Topic archived. No new replies allowed.