   Recursion, C++, Pointers...
  Hello all,So, I had posted a few questions in regards to an old assignment I had with C++ and pointers. I know that homework help is sort of frowned upon around these parts, however, my semester for this assignment was over a year ago. I am just revisiting it because I still am at a lapse of how to solve it appropriately, despite being given an A for my effort (at least I think it was my effort, I annoyed the hell out of my professor at the time of this assignment).Without further ado, here is a scan of the original assignment: Questions:1. Seems there are alot of conditions that makes the "createMaze" function quite cumbersome in regards to recursion....NO/YES? I don't know, I am asking!!2. In regards to number one, conditions of being a corner of the maze, top of maze, left, right, bottom.....am I reading too much into the problem?3. Based on the assignment parameters, which are loose, we are free to interpret/add variables as we see fit. Should a cell ("MazeCell") know its position within the maze? I thought the maze should make that distinction, but, seems to me that "MazeCell" would then need some local variables to account for that, or no?So, thats my initial set of questions. I am wondering what some more experienced would say based on the "assignment parameters."Thanks everyone!!!Shawn   
  It looks to me like the given algorithms for building and solving the maze are very well suited to recursion. If you implement them step-for-step, it should become clear how things work. On that note, post your best shot at implementing the code, and we can work through it from there [smile]Also, I see no reason why a maze cell would ever need to know its position... the only time you care about positions is when you already know where you are in the maze grid (i.e. building or solving the maze) so you can look up and manipulate the correct cell directly without needing the cell itself to know where it is.   ;  I kind of feel like clarifying a few of my questions stated above.My first implementation of this problem indeed used a 6x6 maze to at least generate a maze. My solution however, left (on occasion) a few cells as still have 4 walls, which to me failed.At a subsequent point, along with the C# class that was held here on gamedev.net, I tried again but this time using a dynamic (read that as user supplied values for dimensions of the maze) array for the maze. I was again left with some cells (granted it was occasional) left unvisited (meaning they still had four walls).That is the basis of why I revisited this problem from my class, basically trying to understand where my logic fell apart.....   ;  Thank you Apoch for the reply, not sure how to list this so, within code blocks:Main.cpp/*Shawn ElswickMay 4, 2008*/#include <iostream>#include "Maze.h"using namespace std;int main(){Maze * maze = new Maze();cout << "Maze created with all walls up..." << endl;maze->createMaze();cout << "Returned from createMaze..." << endl;delete maze;maze = NULL;return 0;}That is my original maze function that I called to create the maze. Following are the supplementary .h and .cpp files to support that main function.Maze.h/*Shawn ElswickMay 4, 2008*/#ifndef MAZE_H#define MAZE_H#include "MazeCell.h"class Maze{public:Maze();void createMaze();~Maze();private:const int ROWS;const int COLS;const int MIN;const int MAX;MazeCell * mazeCell[6][6];int createPaths(int, int, int);bool checkDeadEnd(int, int);};#endifMaze.cpp/*Shawn ElswickMay 4, 2008*/#include <ctime>#include <cstdlib>#include <iostream>#include "Maze.h"using namespace std;Maze::Maze() : ROWS(6), COLS(6), MIN(0), MAX(5){for (int row=0; row < ROWS; row++){for (int col=0; col < COLS; col++){this->mazeCell[row][col] = new MazeCell();}}}void Maze::createMaze(){//Seed with timesrand((int)time(0));//Create start pointthis->mazeCell[MIN][MIN]->breakWall(MazeCell::NORTH);//Create end pointthis->mazeCell[MAX][MAX]->breakWall(MazeCell::SOUTH);//Create initial *startRow, *startColint startRow = rand() % ROWS;int startCol = rand() % COLS;//Create a total visited variableint totalVisited = 0;//Call createPaths helper function//totalVisited += createPaths(startRow, startCol, totalVisited);cout << "Total visits: " << totalVisited << endl;while(totalVisited < ROWS*COLS){int total=0;total+=createPaths(startRow, startCol, total);totalVisited += total;cout << "Total visits: " << totalVisited << endl;cin.get();}return;}Maze::~Maze(){for (int row=0; row < ROWS; row++){for (int col=0; col < COLS; col++){delete this->mazeCell[row][col];this->mazeCell[row][col] = NULL;}}}//Helper functions(createPaths, checkDeadEnd)int Maze::createPaths(int startRow, int startCol, int totalVisited){cout << "Row, Col: " << startRow << ", " << startCol << " Moving....";//Pick a random direction to travelint d = rand() % 4;switch(d){case MazeCell::NORTH:cout << "North" << endl;if ((startRow)-1 >= MIN && mazeCell[(startRow)-1][startCol]->wasVisited()==false &&mazeCell[(startRow)-1][startCol]->isDeadEnd()==false){cout << "You can move here." << endl;//Mark current cell as visitedmazeCell[startRow][startCol]->markVisited();//Break current cell North WallmazeCell[startRow][startCol]->breakWall(MazeCell::NORTH);//Increment totalVisited by 1totalVisited++;//If less than total cells callback createPathsif (totalVisited < ROWS*COLS){//First change *startRow to new value(startRow)--;//Break new cells opposite wallmazeCell[startRow][startCol]->breakWall(MazeCell::SOUTH);createPaths(startRow, startCol, totalVisited);}//If greater then end recursive callselse{return totalVisited;}}else{cout << "You cannot move here." << endl;//Check for dead endif (checkDeadEnd(startRow, startCol)){mazeCell[startRow][startCol]->markDeadEnd();return totalVisited;}else{createPaths(startRow, startCol, totalVisited);}}break;case MazeCell::SOUTH:cout << "South" << endl;if ((startRow)+1 <= MAX && mazeCell[(startRow)+1][startCol]->wasVisited()==false &&mazeCell[(startRow)+1][startCol]->isDeadEnd()==false){cout << "You can move here." << endl;//Mark current cell as visitedmazeCell[startRow][startCol]->markVisited();//Break current cell South WallmazeCell[startRow][startCol]->breakWall(MazeCell::SOUTH);//Increment totalVisited by 1totalVisited++;//If less than total cells callback createPathsif (totalVisited < ROWS*COLS){//First change *startRow to new value(startRow)++;//Break new cells opposite wallmazeCell[startRow][startCol]->breakWall(MazeCell::NORTH);createPaths(startRow, startCol, totalVisited);}//If greater then end recursive callselse{return totalVisited;}}else{cout << "You cannot move here." << endl;//Check for dead endif (checkDeadEnd(startRow, startCol)){mazeCell[startRow][startCol]->markDeadEnd();return totalVisited;}else{createPaths(startRow, startCol, totalVisited);}}break;case MazeCell::EAST:cout << "East" << endl;if ((startCol)+1 <= MAX && mazeCell[startRow][(startCol)+1]->wasVisited()==false &&mazeCell[startRow][(startCol)+1]->isDeadEnd()==false){cout << "You can move here." << endl;//Mark current cell as visitedmazeCell[startRow][startCol]->markVisited();//Break current cell East WallmazeCell[startRow][startCol]->breakWall(MazeCell::EAST);//Increment totalVisited by 1totalVisited++;//If less than total cells callback createPathsif (totalVisited < ROWS*COLS){//First change *startRow to new value(startCol)++;//Break new cells opposite wallmazeCell[startRow][startCol]->breakWall(MazeCell::WEST);createPaths(startRow, startCol, totalVisited);}//If greater then end recursive callselse{return totalVisited;}}else{cout << "You cannot move here." << endl;//Check for dead endif (checkDeadEnd(startRow, startCol)){mazeCell[startRow][startCol]->markDeadEnd();return totalVisited;}else{createPaths(startRow, startCol, totalVisited);}}break;case MazeCell::WEST:cout << "West" << endl;if ((startCol)-1 >= MIN && mazeCell[startRow][(startCol)-1]->wasVisited()==false &&mazeCell[startRow][(startCol)-1]->isDeadEnd()==false){cout << "You can move here." << endl;//Mark current cell as visitedmazeCell[startRow][startCol]->markVisited();//Break current cell West WallmazeCell[startRow][startCol]->breakWall(MazeCell::WEST);//Increment totalVisited by 1totalVisited++;//If less than total cells callback createPathsif (totalVisited < ROWS*COLS){//First change *startRow to new value(startCol)--;//Break new cells opposite wallmazeCell[startRow][startCol]->breakWall(MazeCell::EAST);createPaths(startRow, startCol, totalVisited);}//If greater then end recursive callselse{return totalVisited;}}else{cout << "You cannot move here." << endl;//Check for dead endif (checkDeadEnd(startRow, startCol)){mazeCell[startRow][startCol]->markDeadEnd();return totalVisited;}else{createPaths(startRow, startCol, totalVisited);}}break;}}bool Maze::checkDeadEnd(int startRow, int startCol){bool isDeadEnd;//Try north, south, east, westif ((startRow)-1 >= MIN && mazeCell[(startRow)-1][startCol]->wasVisited()==true &&(startRow)+1 <= MAX && mazeCell[(startRow)+1][startCol]->wasVisited()==true &&(startCol)+1 <= MAX && mazeCell[startRow][(startCol)+1]->wasVisited()==true &&(startCol)-1 >= MIN && mazeCell[startRow][(startCol)-1]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}//Could be on the edges, check for thatif (startRow == MIN){//Means only South, East or Westif((startCol)+1 <= MAX && mazeCell[startRow][(startCol)+1]->wasVisited()==true &&   (startCol)-1 >= MIN && mazeCell[startRow][(startCol)-1]->wasVisited()==true &&   (startRow)+1 <= MAX && mazeCell[(startRow)+1][startCol]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}if (startRow == MAX){//Means only North, East or Westif((startCol)+1 <= MAX && mazeCell[startRow][(startCol)+1]->wasVisited()==true &&   (startCol)-1 >= MIN && mazeCell[startRow][(startCol)-1]->wasVisited()==true &&   (startRow)-1 <= MAX && mazeCell[(startRow)-1][startCol]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}if (startCol == MIN){//Means only North, South, East if((startRow)+1 <= MAX && mazeCell[(startRow)+1][(startCol)]->wasVisited()==true &&   (startRow)-1 >= MIN && mazeCell[(startRow)-1][(startCol)]->wasVisited()==true &&   (startCol)+1 <= MAX && mazeCell[(startRow)][(startCol)+1]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}if (startCol == MAX){//Means only North, South, West if((startRow)+1 <= MAX && mazeCell[(startRow)+1][(startCol)]->wasVisited()==true &&   (startRow)-1 >= MIN && mazeCell[(startRow)-1][(startCol)]->wasVisited()==true &&   (startCol)-1 <= MAX && mazeCell[(startRow)][(startCol)-1]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}//Could be in the corners alsoif (startRow == MIN && startCol == MIN){//Means upper left corner, only south or eastif((startRow)+1 <= MAX && mazeCell[(startRow)+1][(startCol)]->wasVisited()==true &&  (startCol)+1 <= MAX && mazeCell[(startRow)][(startCol)+1]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}if (startRow == MAX && startCol == MIN){//Means bottm left corner, only north or eastif((startRow)-1 <= MAX && mazeCell[(startRow)-1][(startCol)]->wasVisited()==true &&  (startCol)+1 <= MAX && mazeCell[(startRow)][(startCol)+1]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}if (startRow == MIN && startCol == MAX){//Means upper right corner, only south or westif((startRow)+1 <= MAX && mazeCell[(startRow)+1][(startCol)]->wasVisited()==true &&  (startCol)-1 <= MAX && mazeCell[(startRow)][(startCol)-1]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}if (startRow == MAX && startCol == MAX){//Means lower right corner, only north or westif((startRow)-1 <= MAX && mazeCell[(startRow)-1][(startCol)]->wasVisited()==true &&  (startCol)-1 <= MAX && mazeCell[(startRow)][(startCol)-1]->wasVisited()==true){isDeadEnd = true;}else{isDeadEnd = false;}}return isDeadEnd;}MazeCell.h/*Shawn ElswickMay 4, 2008*/#ifndef MAZECELL_H#define MAZECELL_Hclass MazeCell{public:enum Direction {NORTH, SOUTH, EAST, WEST};MazeCell();bool hasWall(Direction);void breakWall(Direction);bool wasVisited();void markVisited();bool isDeadEnd();void markDeadEnd();~MazeCell();private:bool northWall;bool southWall;bool eastWall;bool westWall;bool visited;bool deadEnd;};#endifMazeCell.cpp/*Shawn ElswickMay 4, 2008*/#include <iostream>#include "MazeCell.h"using namespace std;MazeCell::MazeCell(){this->northWall = true;this->southWall = true;this->eastWall = true;this->westWall = true;this->visited = false;this->deadEnd = false;}bool MazeCell::hasWall(Direction d){switch (d){case NORTH:return this->northWall;break;case SOUTH:return this->southWall;break;case EAST:return this->eastWall;break;case WEST:return this->westWall;break;}}void MazeCell::breakWall(Direction d){switch (d){case NORTH:this->northWall = false;break;case SOUTH:this->southWall = false;break;case EAST:this->eastWall = false;break;case WEST:this->westWall = false;break;}}void MazeCell::markVisited(){this->visited = true;}bool MazeCell::wasVisited(){return this->visited;}bool MazeCell::isDeadEnd(){return this->deadEnd;}void MazeCell::markDeadEnd(){cout << "Marking as a dead end." << endl;this->deadEnd = true;}MazeCell::~MazeCell(){//nothing to clean up};  I didn't look at your code, but I read the assignment and the way it was given leaves the possibility for some cells to have 4 walls - so I don't think you did anything wrong.  It can easily happen with this algorithm because your last one or 2 (or however many) unvisited cells may be surrounded by visited cells, in which case you just mark them visited but don't destroy any walls.  If you want a "perfect" maze that never leaves a cell with 4 walls you will have to come up with a different algorithm.[edit] oh and...1) It could be recursive.  You could also just use a loop.  Eventually you'll realize they're the same thing algorithmically and you can always use one to replace the other (personally I always use loops for my recursion so I don't blow up the stack and because it tends to be faster, but some things like c++ template metaprogramming favor recursion).2) You would have to account for left, right, top and bottom yes (which would automatically account for corners of course).  That's not exactly cumbersome though...3) As ApochPiQ said, no way.  Why do you need to track this?  If you make a 2d array of cells (probably by treating a 1d array as 2d), then your current position will always be known.a) Using recursion, you will most likely be passing your (x, y) into each recursively called functionb) Using a loop or 2, the values are likely to be readily available.  I'm not sure how you could even possibly do it this way without already knowing the position.;  In regards to question #1 in my original post though.....again maybe i am reading too much into it, but, as far as recursion goes, should it not just be related to a quick and easy subset that does not necessarily have pre or post conditions associated with it? Or should it have pre or post conditions? Again asking to try to comprehend....seems this problem, as far as implementation presents quite a few conditions...no/yes?;  Again an edit...seems to me the end condition is basically a dead end, at which case we are popping some original calls.....so why then, when we do have another move would a cell not state so? See what I am saying?   ;Quote:Original post by popsoftheyearI didn't look at your code, but I read the assignment and the way it was given leaves the possibility for some cells to have 4 walls - so I don't think you did anything wrong.  It can easily happen with this algorithm because your last one or 2 (or however many) unvisited cells may be surrounded by visited cells, in which case you just mark them visited but don't destroy any walls.  If you want a "perfect" maze that never leaves a cell with 4 walls you will have to come up with a different algorithm.The description in the assignment of how to create a maze looks like it would not leave any blocks unexplored.  If an unexplored block were surrounded by explored blocks, then it would be explored when the algorithm backtracks from it's various dead-ends back to the start.  There would have to be a time when it backtracked past this enclosed area, and would explore it then.   ;Quote:Original post by DrigovasIf an unexplored block were surrounded by explored blocks, then it would be explored when the algorithm backtracks from it's various dead-ends back to the start.I posted an example but it was incorrect.Now I'll post a correct one:Take a 3x3 grid.  All decisions are random, for future reference.  We start at (1, 0).  Move to (1, 1).  Move to (1, 2).  Move to (2, 2).  Move to (2, 1). Move to (2, 0).  All directions are dead ends, so we are at a dead end.  Mark all these spaces as visited.  This leaves us with (0, 0), (0, 1), and (0, 2).Start at (0, 1).  Move to (0, 2).  All directions are dead ends, so we mark all these spaces as visited.  Now (0, 0) is the only space unvisited.  We go to it, and there are no unvisited spaces, and all directions are dead ends.  It's marked visited, making the maze complete, but it still has all 4 sides.  There are more cases where these can end up in the middle as well, but not on a 3x3 grid.;Quote:Original post by shawnreIn regards to question #1 in my original post though.....again maybe i am reading too much into it, but, as far as recursion goes, should it not just be related to a quick and easy subset that does not necessarily have pre or post conditions associated with it? Or should it have pre or post conditions? Again asking to try to comprehend....seems this problem, as far as implementation presents quite a few conditions...no/yes?What conditions?  If you can move in any direction, recurse to that direction.  To test if you can move in a direction, see if 1) it is an edge, in which case you can NOT.  But if it is not an edge then you go ahead and test 2) if it has been visited already.  If either test fails (and only test #2 if #1 passes), then you are at a dead end, and you recurse backwards to the start, supposedly marking them visited at this point.The only thing that confuses me about the given algorithm, is shouldn't you mark the spaces as visited as you go?  vs after you hit a dead end?  Come to think of it, the way it's presented, you will never, ever hit a dead end unless you mark them as you go.It's an iffy description of maze generation...In fact my example in the previous post would only work if you marked them visited as you went...... huh.   