C++

Forum

 
Perfect Maze algorithm

zantocon (7)
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: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
#include "Cell.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>

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<Cell> trail;

   // Create a vector of DIR values named live.
   vector<DIR> 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<COLS-1)
      if(maze[curX][curY+1].getWalls()==Cell::WALL_ALL) // east has all walls
         live.push_back(EAST);
      if(curX)
      if(maze[curX-1][curY].getWalls()==Cell::WALL_ALL) // North has all walls
         live.push_back(NORTH);
      if(curX<ROWS-1)
      if(maze[curX+1][curY].getWalls()==Cell::WALL_ALL) // South has all walls
         live.push_back(SOUTH);
      // If the live vector is not empty:
      if(live.empty()==false) {
         // Choose one of the directions in the live vector at random
         // ran_dir=rand() % live.size();
         // cout << "Random dir " << ran_dir << " out of " << live.size() << "\n";
         // Remove the walls between the current cell and the neighbor in that direction
         // and Change curX and curY to refer to the neighbor
         maze[curX][curY].setVisited(true);
         switch(live[rand() % live.size()]) {
            case 0:
               maze[curX][curY].removeWall(Cell::WALL_NORTH);
               curX--;
               break;
            case 1:
               maze[curX][curY].removeWall(Cell::WALL_SOUTH);
               curX++;
               break;
            case 2:
               maze[curX][curY].removeWall(Cell::WALL_EAST);
               curY++;
               break;
            case 3:
               maze[curX][curY].removeWall(Cell::WALL_WEST);
               curY--;
               break;
         }
         // Push the new current cell onto the trail stack
         /*cout << "Maze " << curX << ", " << curY << "\n";
         cin.ignore(); */
         trail.push_back(maze[curX][curY]);
      } //If the live vector was emtpy:
      else {
         // Pop the top item from the trail stack
         trail.pop_back();

         // If the trail stack is not empty, set curX and curY to refer to the 
         // position of the top item in the trail stack.
         if(trail.empty()==false) {
            curX=trail[0].getRow();
            curY=trail[0].getColumn();
         }
      }
   }

   // Do the following to display the maze:
    int r, c;
    for (c=0; c<COLS; c++) {
        if (c == 0) cout << " _";
        else cout << "__";
    }
    cout << '\n';
    for (r=0; r<ROWS; r++) {
        for (c=0; c<COLS; c++) {
            cout << maze[r][c];
        }
        cout << "|\n";
    }
   return 0;
}


Cell implementation:
cell.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#ifndef __CELL_H_
#define __CELL_H_

#include <string>
#include <iostream>

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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include "Cell.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>



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.



jsmith (5804)
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]?
zantocon (7)
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.
zantocon (7)
Yer a genious :)

I changed the code to this and it works:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
            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.