C++ Maze Generation Algorithm Implementation Help

[Kase42]

Hey everyone.

I am attempting to create a simple console maze generator in C++ for a school project. I've already gotten most of it down but I'm having a problem debugging the actual generation algorithm I've implemented. I've been learning C++ for the past few months now but I haven't ventured into the STL very much. The problem may be I am doing something illegal with the vector but I can't see it.

Here is the code thus far:

// *************************************
// ** M A Z E   C O O R D   C L A S S **
// *************************************

#include <iostream>

enum COORDTYPE { FLOOR, WALL, BORDER };

class MazeCoord
{
    // private data members
    // [x-coordinate, y-coordinate, maximum value of x, maximum value of y,
    //  "wall or floor" variable, total number of coordinates]
    int x, y, maxX, maxY, coordType, numCoord;


public:

    // Constructors
    MazeCoord() { }
    MazeCoord(int xarg, int yarg)  { x = xarg; y = yarg; }
    MazeCoord(const MazeCoord &coordCopy) { x = coordCopy.x; y = coordCopy.y; }

    // Destructor
    ~MazeCoord() { }

    // Get coordinate and coordinate type functions
    // These function return a specified private data member.
    const int getCoordX() { return x; }
    const int getCoordY() { return y; }
    const int getMaxX() { return maxX; }
    const int getMaxY() { return maxY; }
    const int getCoordType() { return coordType; }
    const int getNumCoord() { return numCoord; }

    // Set functions for maze generation
    // These functions assign a specified value to a data member.
    int setMaxX(int maxXArg) { maxX = maxXArg; return maxX; }
    int setMaxY(int maxYArg) { maxY = maxYArg; return maxY; }
    int setFloor() { coordType = FLOOR; return FLOOR; }
    int setWall() { coordType = WALL; return WALL; }
    int setBorder() { coordType = BORDER; return BORDER; }
    int setNumCoord() { numCoord = (maxX + 1) * (maxY + 1); return numCoord; }


    // Operator overloading functions

    // Relational operators
    friend bool operator==(const MazeCoord coordA, const MazeCoord coordB) {
        return (coordA.x == coordB.x && coordA.y == coordB.y) ? 1 : 0;
    }
    friend bool operator!=(const MazeCoord coordA, const MazeCoord coordB) {
        return (coordA.x != coordB.x || coordA.y != coordB.y) ? 1 : 0;
    }
    friend bool operator>=(const MazeCoord coordA, const MazeCoord coordB) {
        return (coordA.x >= coordB.x || coordA.y >= coordB.y) ? 1 : 0;
    }
    friend bool operator<=(const MazeCoord coordA, const MazeCoord coordB) {
        return (coordA.x <= coordB.x || coordA.y <= coordB.y) ? 1 : 0;
    }
    friend bool operator>(const MazeCoord coordA, const MazeCoord coordB) {
        return (coordA.x > coordB.x || coordA.y > coordB.y) ? 1 : 0;
    }
    friend bool operator<(const MazeCoord coordA, const MazeCoord coordB) {
        return (coordA.x < coordB.x || coordA.y < coordB.y) ? 1 : 0;
    }

    // Increment operator
    MazeCoord& operator++() {
        if (x == maxX && y == maxY) return *this;
        else if (x == maxX && y != maxY) { x = 0; y++; return *this; }
        else { x++; return *this; }
    }

    // Assignment operator
    MazeCoord& operator= (const MazeCoord& coord) {
        x = coord.x;
        y = coord.y;
        maxX = coord.maxX;
        maxY = coord.maxY;
        coordType = coord.coordType;
        numCoord = coord.numCoord;
        return *this;
    }

    // Output operator
    friend std::ostream& operator<<(std::ostream& output, MazeCoord& coord) {
        output << "(" << coord.x << "," << coord.y << ")";
        return output;
    }


    // Directional coordinate functions
    // These functions return a coordinate in the given direction by
    // incrementing or decrementing the x or y variables of the this argument.

    MazeCoord getNorth()
    {
        if (y != maxY) y--;     // decrement would cause underflow if false
        MazeCoord coord(x, y);
        return coord;
    }

    MazeCoord getSouth()
    {
        if (y != 0) y++;        // increment would cause overflow if false
        MazeCoord coord(x, y);
        return coord;
    }

    MazeCoord getEast()
    {
        if (x != maxX) x++;     // increment would cause overflow if false
        MazeCoord coord(x, y);
        return coord;
    }

    MazeCoord getWest()
    {
        if (x != 0) x--;        // decrement would cause underflow if false
        MazeCoord coord(x, y);
        return coord;
    }

    MazeCoord getTwoNorth()
    {
        if (y != maxY && y != maxY - 1) { y -= 2; }
        MazeCoord coord(x, y);
        return coord;
    }

    MazeCoord getTwoSouth()
    {
        if (y != 0 && y != 1 ) { y += 2; }
        MazeCoord coord(x, y);
        return coord;
    }

    MazeCoord getTwoEast()
    {
        if (x != maxX && x != maxX - 1) { x += 2; }
        MazeCoord coord(x, y);
        return coord;
    }

    MazeCoord getTwoWest()
    {
        if (x != 0 && x != 1) { x -= 2; }
        MazeCoord coord(x, y);
        return coord;
    }
};

// *********************************************************
// ** M A Z E   C O O R D   C L A S S   F U N C T I O N S **
// *********************************************************

#include "MazeCoord.h"

#include <stack>
#include <vector>

MazeCoord getNorth(MazeCoord coordArg);
MazeCoord getSouth(MazeCoord coordArg);
MazeCoord getEast(MazeCoord coordArg);
MazeCoord getWest(MazeCoord coordArg);
int findNeighbourWalls(std::vector<MazeCoord> &maze, MazeCoord &coordArg);

int findCoord(std::vector<MazeCoord> &maze, int xarg, int yarg);
int findCoord(std::vector<MazeCoord> &maze, MazeCoord &coord);


void setBorder(std::vector<MazeCoord> &maze, MazeCoord &coord);

struct Direction
{
    bool isNorth;
    bool isSouth;
    bool isEast;
    bool isWest;

    Direction(bool north, bool south, bool east, bool west) {
        isNorth = north; isSouth = south; isEast = east; isWest = west;


    }
};

    Direction findDirection(std::vector<MazeCoord> &maze, MazeCoord &coordArg,
                            Direction &direct);

void genMaze(std::vector<MazeCoord> &maze, MazeCoord &coord2)
{
    srand(time(NULL));

    std::stack<MazeCoord> coordinates;
    MazeCoord coord(1, maze[0].getMaxY());
    Direction direct(false, false, false, false);

    int index = findCoord(maze, coord);
    maze[index].setFloor();
    coordinates.push(maze[index]);

    coord = coord.getNorth();
    index = findCoord(maze, coord);
    maze[index].setFloor();

    int visitedCoord = 1;
    int initNumCoord = maze[0].getMaxY() * 2 + (maze[0].getMaxX() - 2) * 2;

    while (visitedCoord <= initNumCoord) {
        findDirection(maze, maze[index], direct);
        int chosenDirection = 0;
        chosenDirection = (rand() % 4) + 1;

        bool isSuccess = false;
        do {
            if (chosenDirection == 1 && direct.isNorth == true) {
                coord = coord.getNorth();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                coord = coord.getNorth();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                visitedCoord += 2;
                isSuccess = true;
            }
            else if (chosenDirection == 2 && direct.isSouth == true) {
                coord = coord.getSouth();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                coord = coord.getSouth();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                visitedCoord += 2;
                isSuccess = true;
            }
            else if (chosenDirection == 3 && direct.isEast == true) {
                coord = coord.getEast();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                coord = coord.getEast();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                visitedCoord += 2;
                isSuccess = true;
            }
            else if (chosenDirection == 4 && direct.isWest == true) {
                coord = coord.getWest();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                coord = coord.getWest();
                index = findCoord(maze, coord);
                maze[index].setFloor();
                visitedCoord += 2;
                isSuccess = true;
            }
            else {
                coordinates.pop();
                maze[index] = coordinates.top();
            }
        } while (isSuccess == false);
    }

    return;
}

int findNeighbourWalls(std::vector<MazeCoord> &maze, MazeCoord &coordArg)
{
    int numWalls = 0;

    int indexA = findCoord(maze, coordArg);
    int indexB = 0;

    MazeCoord coord;

    coord = maze[indexA].getNorth();
    indexB = findCoord(maze, coord);
    if (maze[indexB].getCoordType() == WALL) numWalls++;
    coord = maze[indexA].getSouth();
    indexB = findCoord(maze, coord);
    if (maze[indexB].getCoordType() == WALL) numWalls++;
    coord = maze[indexA].getEast();
    indexB = findCoord(maze, coord);
    if (maze[indexB].getCoordType() == WALL) numWalls++;
    coord = maze[indexA].getWest();
    indexB = findCoord(maze, coord);
    if (maze[indexB].getCoordType() == WALL) numWalls++;

    return numWalls;
}

Direction findDirection(std::vector<MazeCoord> &maze,
                         MazeCoord &coordArg, Direction &direct)
{
    if ((coordArg.getTwoNorth()).getCoordType() == WALL) direct.isNorth = true;
    if ((coordArg.getTwoSouth()).getCoordType() == WALL) direct.isSouth = true;
    if ((coordArg.getTwoEast()).getCoordType() == WALL) direct.isEast = true;
    if ((coordArg.getTwoWest()).getCoordType() == WALL) direct.isWest = true;

    return direct;
}

void display(std::vector<MazeCoord> &maze, MazeCoord &coord)
{
    for (unsigned int i = 0; i < maze.size(); i++) {
        if (maze[i].getCoordType() == FLOOR) std::cout << " ";
        else if (maze[i].getCoordType() == WALL) std::cout << "@";
        else std::cout << "#";
        if (maze[i].getCoordX() == coord.getMaxX()) std::cout << std::endl;
    }
}

void setAllWall(std::vector<MazeCoord> &maze, MazeCoord &coord)
{
    for (unsigned int i = 0; i < maze.size(); i++) {
        maze[i] = coord;
        maze[i].setWall();
        ++coord;
    }
}

void setBorder(std::vector<MazeCoord> &maze, MazeCoord &coord)
{
    for (unsigned int i = 0; i < maze.size(); i++) {
        if (maze[i].getCoordX() == 0 ||
            maze[i].getCoordX() == maze[i].getMaxX() ||
            maze[i].getCoordY() == 0 ||
            maze[i].getCoordY() == maze[i].getMaxY())
            maze[i].setBorder();
    }
}

int findCoord(std::vector<MazeCoord> &maze, int xarg, int yarg)
{
    int index;

    for (unsigned int i = 0; i < maze.size(); i++) {
        if (maze[i].getCoordX() == xarg && maze[i].getCoordY() == yarg) {
            index = i;
            break;
        }
    }

    return index;
}

int findCoord(std::vector<MazeCoord> &maze, MazeCoord &coord)
{
    int index;

    for (unsigned int i = 0; i < maze.size(); i++) {
        if (maze[i].getCoordX() == coord.getCoordX() &&
            maze[i].getCoordY() == coord.getCoordY()) {
            index = i;
            break;
        }
    }

    return index;
}

// *******************************
// ** M A I N   F U N C T I O N **
// *******************************

#include <iostream>
#include <vector>
#include "MazeCoord.h"

using namespace std;

#define MAXVALX 70
#define MAXVALY 20

int findNeighbourWalls(vector<MazeCoord> &maze, MazeCoord &coordArg);
int findCoord(vector<MazeCoord> &maze, int xarg, int yarg);
void genMaze(std::vector<MazeCoord> &maze, MazeCoord &coord);
void display(vector<MazeCoord> &maze, MazeCoord &coord);
void setAllWall(vector<MazeCoord> &maze, MazeCoord &coord);
void setBorder(std::vector<MazeCoord> &maze, MazeCoord &coord);

int main()
{
    MazeCoord coord(0, 0);
    coord.setMaxX(MAXVALX);
    coord.setMaxY(MAXVALY);
    coord.setNumCoord();

    vector<MazeCoord> maze(coord.getNumCoord());

    setAllWall(maze, coord);
    setBorder(maze, coord);

    genMaze(maze, coord);

    display(maze, coord);

    return 0;
}

Wherever there is a triple line // comment and asterisks, the code below it is within a different module. The programme crashes just after entering the do-while loop in the genMaze function. It may just be some simple oversight, but I have spent hours trying to fix it, to no avail.

Any advice and help would be greatly appreciated.

[StuXYZ]

First of all, welcome to Daniweb. Thank-you for writing a coherent, well constructed post, with code tags.

Your problem in this code [which actually causes the core dump] is that both of the findCoord functions can return an undefined number.

Consider your code:

int 
findCoord(std::vector<MazeCoord> &maze, int xarg, int yarg)
{
  int index;   // Uninitialized value
  for (unsigned int i = 0; i < maze.size(); i++) 
    {
      if (maze[i].getCoordX() == xarg && maze[i].getCoordY() == yarg) {
	index = i;
	break;
      }
    }
  // What happens if there was no break????
  return index;
}

As you can see if the condition is not met then you get an uninitialized value on return and that is going to cause problems.

So first decide how likely it is to be like this, e.g. is it always indicative that something terribly wrong has happened elsewhere, e.g. then throw an exception, or it is just run of the mill stuff, then return an error code, e.g. -1.

Let us do the latter, and tidy things up a bit.

int 
findCoord(std::vector<MazeCoord>& maze,const int xarg,const int yarg)
{
  for (unsigned int i = 0; i < maze.size(); i++) 
    if (maze[i].getCoordX() == xarg && maze[i].getCoordY() == yarg) 
      return i;
    
  // no value found:
  return -1;
}

Obviously, you have to change the other findCoord, and you have to start dealing with the error codes, and change your algorithm a bit. Obviously, if you get stuck doing that, please feel free to post the next problem.

I spent about 3 minutes finding that error, which tells me that you are going about debugging in a non-systematic manor. Assuming that you don't have a debugger, (which takes you directly to the error). What you do is put lines like this: std::cerr<<"HERE:1"<<std::endl; into the code, and locate the crash point,
then write out the variables that are close by, e.g. you would have found it was in a copy, but that come from a setting into an index which is clearly insane.

[Kase42]

Thanks for that, and thanks for the welcome. I've now implemented a simple coordCheck(int index) function to check for any errors. When I ran it, the error never came up, however I did try changing the direct struct contstructor's initialiser from (false, false, false, false) to (true, true, true, true) (line 198). I don't actually remember why I set it to false in the first place, but the programme no longer crashes, it just creates some random gaps and stops.

Since the the starting coordinate is one coordinate left and up from the bottom left, I want to set it so that only the east and north coordinates of this one are available, yet even if I change one parameter of the direct struct to false, the programme once again crashes. Any advice on this?

[StuXYZ]

Have you actually fixed the problem of uninitialized values, I ran you program with
these two findCoord, and prints "ERROR HERE" in both cases and exits.

int findCoord(std::vector<MazeCoord> &maze, MazeCoord &coord)
{
    for (unsigned int i = 0; i < maze.size(); i++) 
      {
        if (maze[i].getCoordX() == coord.getCoordX() &&
            maze[i].getCoordY() == coord.getCoordY()) {
	  return i;
        }
    }
    std::cout<<"ERROR HERE:findCoord(V,M)"<<std::endl;
    exit(1);
}
// AND 
int 
findCoord(std::vector<MazeCoord> &maze, int xarg, int yarg)
{
  for (unsigned int i = 0; i < maze.size(); i++) 
      if (maze[i].getCoordX() == xarg && maze[i].getCoordY() == yarg) {
	return i;

  std::cerr<<"ERROR HERE in findCoord(V,x,y)"<<std::endl;
  exit(1);
}

Now what have you changed so that the program never reaches either of the exits, because under the original program, in both cases you will have a completely random value returned, maybe within range, maybe not, but definitely unpredictable and may change as you run the program.

[Kase42]

Ah, my bad. Thought I had fixed it but I hadn't. Could you explain why it may not return a value in range? I realise it's good to account for such things, but in this case strictly, the x and y arguments passed will always be in range, no?

But as you said, the error did come up, about 25 times on the last run.

[StuXYZ]

The error is close to the worst kind because (a) it is at run-time [it is always easier to fix compile-time]. (b) it is random, you can run the program one time, and get a different answer next time -- and you have changed NOTHING.

Ok so what is happening, in simple form you have this:

int index;
for(int i=0;i<10;i++)
   if (i==11)
     index=20;
std::cout<<Index == "<<index<<std::endl;

Can you see that index is not set to anything. there is no initializer. It has no value. You could get round that by writing int index(10); then index would always be 10 in the above code.

Now, maybe the question, is why is it that the condition I set in my findCoord is not met. For the first case, consider a point at the left edge of the maze, then it cannot have a point to the left, hence you cannot satisfy the condition maze[i].getCoordX() == xarg && maze[i].getCoordY() == yarg since you are calling it with (effectivley) xarg = maze[i].getCoordX()-1; I notice a number of annoying errors [NOT ALL ERRORS!!!!]:

(a) your copy constructor doesn't copy everything, but that isn't your main problem.
(b) getNorth and getSouth test on y!=maxY and y!=0 which are the wrong way round.
(c) same problem with 2south /2north.

However, I really think you are going to have to add some error code. But before you do please tidy up the program, because as you add complexity, it gets more difficult to deal with. E.g. remove all the friend functions, that can all be class members, add const to all methods that don't or should not change the class, and const to all referenced objects that should not change.

[Kase42]

I see. Thank you very much for the help. I'll spend some time to clean up the code and add your suggestions; possibly re-post it if I get really stuck.

Thanks again.