Maze generation

Question

I have been working on a maze generator in C++ in an effort to learn the language and brush up on some long lost knowledge. I want to ensure that I am using best practices, and really doing things the way that they should be done.

My code is safely tucked into a GitHub repository. I would like to have two specific classes reviewed: Maze.h (154 lines) (and MazeConstants.h if possible), as well as MazePosition.h (45 lines).

I also had a couple questions. Is it advisable to overload operator!= in addition to operator==? I overload operator== in the MazePosition class, but not operator!=. Is it good practice to provide copy constructors and overloaded assignment operators as well? I am mostly confused about best practices in these areas, and the info I have found online has been sparse and mostly just pages with illustrated examples. I plan on disabling any sort of copying ability in the Maze.h class by doing something like this: (boost.org/doc/libs/1_47_0/boost/noncopyable.hpp) because it does not make sense to copy that object for any reason (too slow anyway, right?).

File: MazePosition.h (45 Lines)

/*
* File: MazePosition.h
* Author: mattosaurus
*
* Created on August 6, 2011, 4:26 PM
*/

#ifndef MAZEPOSITION_H
#define MAZEPOSITION_H

class MazePosition{
public:
    MazePosition(int row, int col) : _row(row), _col(col){}

    int getRow() const{
        return _row;
    }
    int getCol() const{
        return _col;
    }

    MazePosition operator+(MazePosition & p2) const{
        int newX = _row + p2.getRow();
        int newY = _col + p2.getCol();
        MazePosition local(newX, newY);
        return local;
    }

    friend bool operator==(MazePosition const&p1, MazePosition const&p2);

private:
    int _row;
    int _col;

};
bool operator==(MazePosition const&p1, MazePosition const&p2) {
        if(p1.getRow() == p2.getRow()){
            return (p1.getCol() == p2.getCol());
        }
        return false;
    }

#endif /* MAZEPOSITION_H */

File: Maze.h (145 Lines)

/*
* File: Maze.h
* Author: mattosaurus
*
* Created on August 5, 2011, 3:34 PM
*/

#ifndef MAZE_H
#define MAZE_H
#include <iostream>
#include <exception>
#include <time.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <stdexcept>
#include "MazePosition.h"
#include "MazeConstants.h"
using std::vector;
using std::stack;
typedef vector< vector<int> > IntMaze;
class Maze {
public:
    Maze(int width, int height) : _width(width+2), _height(height+2), _maze(_height, vector<int>(_width))
    {
        MazeInit(_maze, MazeConstants::UNVISITED);
        MazeCarve(_maze, _exitList);
    }

    int getHeight(){
      return _height;
    }
    int getWidth(){
      return _width;
    }

    void MazeInit( IntMaze & maze, int init){
        //initialize all cells to 0 (unvisited)
        //surround with a border of out of bounds cells (-1)

        for(int i = 0; i < maze.capacity(); i++){
            for(int j = 0; j < maze.at(i).capacity(); j++){
                if(i == 0 || i == maze.capacity() -1 ){
                   maze.at(i).at(j) = MazeConstants::INVALID;
                }
                else if(j == 0 || j == maze.at(i).capacity() -1 ){
                    maze.at(i).at(j) = MazeConstants::INVALID;
                }
                else{
                    maze.at(i).at(j) = init;
                }
            }
        }//end initial initialization
    }

    void MazeCarve(IntMaze & maze, vector<MazePosition> & exitList){
        //Pick a starting location (pick something along the height(x) and width(0).
        int row = (rand() % (_height));
        int col = (rand() % (_width));

        MazePosition start(row, col);

        //mark start as visited (non-zero)
        maze.at(start.getRow()).at(start.getCol()) = MazeConstants::START;

        //begin the grunt work
        CarveFrom(maze, start, exitList);
    }

    void CarveFrom(IntMaze & maze, MazePosition & start, vector<MazePosition> & exitList){

        vector<MazePosition> dirCopy = MazeConstants::directions;
        std::random_shuffle(dirCopy.begin(), dirCopy.end());

        for(int i = 0; i < dirCopy.size(); i++){
            MazePosition temp = dirCopy.at(i);
            MazePosition newPos = start + temp;
            //is position valid
            int tile;
            try{
                tile = maze.at(newPos.getRow()).at(newPos.getCol());
            }
            catch(std::out_of_range e){
                continue;
            }
            if(tile == MazeConstants::INVALID){
                exitList.push_back(temp);
                continue;
            }
            if(tile == MazeConstants::UNVISITED){
                maze.at(newPos.getRow()).at(newPos.getCol()) = MazeConstants::FLOOR;
                //since we jump multiple tiles, set the prev one to FLOOR

                //we came from the south
                if(MazeConstants::N == temp){
                    maze.at(newPos.getRow() -1).at(newPos.getCol()) = MazeConstants::FLOOR;
                }
                //came from north
                if( temp == MazeConstants::S ){
                    maze.at(newPos.getRow()+1).at(newPos.getCol()) = MazeConstants::FLOOR;
                }
                //came from west
                if(MazeConstants::E ==temp){
                    maze.at(newPos.getRow()).at(newPos.getCol()-1) = MazeConstants::FLOOR;
                }
                //came from east
                if(MazeConstants::W == temp){
                    maze.at(newPos.getRow()).at(newPos.getCol()+1) = MazeConstants::FLOOR;
                }
                //start looking at the new spot.
                CarveFrom(maze, newPos, exitList);
            }
        }
    }

    friend std::ostream& operator<<(std::ostream& stream, const Maze& m);

private:
    const int _height;
    const int _width;
    IntMaze _maze;
    vector<MazePosition> _exitList;
};

std::ostream& operator<<(std::ostream& stream, const Maze& m) {
    for(int i = 0; i < m._maze.capacity(); i++){
        for(int j = 0; j < m._maze.at(i).capacity(); j++){

/*
* this was added for the pgm output to make things look
* more uniform on the final image, instead of two shades for out of bounds squares.
* Internally, the maze still uses 1 for unvisited - and 0 for invalid. These are only
* altered artificially when the maze is being sent to cout.
*/

int temp = m._maze.at(i).at(j);
if(temp == MazeConstants::UNVISITED){
stream << (temp-1) << " ";

}
else{
stream << temp << " ";

}
        }
        stream << std::endl;
    }
    return stream;
}


#endif /* MAZE_H */

Answer 1

My biggest bugbear:

Why are you exposing internal members via getters!!!
Do other people need to know what position the MazeLocation points at?

int getRow() const{
    return _row;
}
int getCol() const{
    return _col;
}

And

int getHeight(){
  return _height;
}
int getWidth(){
  return _width;
}

Exposing them tightly binds your object to anything that uses them. As far as I can tell the only thing that will ever need it to know the maze position is a Maze. Thus you should Make 'Maze' a friend of 'MazePosition' and remove the getters (if you are going to tightly bind stuff together make the number of bindings as small as possible.

As pointed out elsewhere: you only need to use at() if you have unvalidated input and are using it to index the array. Your code is using validated input (as you are looping from start to end), unfortunately you make the mistake of using capacity() rather than size() which is why it was throwing.

for(int j = 0; j < maze[i].size(); j++)
{                   //        ^^^^^^
   maze[i][j] = MazeConstants::INVALID;
   //  ^^^^^^ guranteed to be good

But I would rather user iterators:

for(IntMaze::iterator loop = maze.begin(); loop != maze.end(); ++loop)
{                                                       //    ^^ Prefer pre-increment

   for(IntRow::iterator inner = loop->begin(); inner != loop->end(); ++inner)
   {

This makes the code easier to translate for the standard algorithms when you learn how to use them.

Answer 2

1. If you overload an operator, make sure that the corresponding operators behave accordingly - in your case: yes, overload !=. Make sure not to copy paste code but call operator == instead (or its implementation).

2. Always provide copy and assignment operators. If you do not, document why the default operators work. If you do not want to copy / assign objects of this type (may be expensive), make them private and provide no implementation. This way you won't accidentally copy an object that is not copyable.

Read good C++ books such as Effective C++ and More Effective C++ by Scott Meyers. He provides lots of hints about pitfalls in C++.

---

A remark on commenting when the defaults do: yes, there are (simple) objects where the defaults do. Still for maintenance it is important to detect whether the author of a class knows that the defaults works or just forgot to prohibit them. That's why documenting this fact is necessary. You can't distinguish a class where someone deliberately relies on the default mechanism or just forgot to implement or prohibit the copy constructor / assignment operator.

With a comment in place it is easy. A class has 3 possibilities:

• custom copy & assignment
• prohibited copy & assignment
• comment that the defaults work

Everything else is an error.

Answer 3

You are misusing std::vector, you should look at the reference.

• You should be using size() instead of capacity().
• You could use [x] instead of .at(x).

Are you expecting out_of_range exceptions?

        try{
            tile = maze.at(newPos.getRow()).at(newPos.getCol());
        }
        catch(std::out_of_range e){
            continue;
        }

Exception handling should not be a part of your usual program logic, it should only happen in "exceptional situations".

The friend declaration is not needed.

"friend bool operator==(MazePosition const&p1, MazePosition const&p2);"

Suggestion for MazeInit:

void MazeInit( IntMaze & maze, int init)
{
    maze_.clear();
    maze_.resize(_height, vector<int>(_width, init));

    // Put the borders to MazeConstants::INVALID
    std::fill(maze_.front().begin(), maze_.front().end(), MazeConstants::INVALID);
    std::fill(maze_.back().begin(), maze_.back().end(), MazeConstants::INVALID);
    std::for_each(maze_.begin(), maze_.end(), [](const std::vector<int>& row)
    {
       row.front() = MazeConstants::INVALID;
       row.back()  = MazeConstants::INVALID;
    });
}

Answer 4

Some others are mentioning good points. I would like to get a point or two in about general readability.

It's very hard for me to look at this code as an outsider and realize what it's doing. Here is a list of things that I think could improve the overall "feel" of the code.

• Put newlines between your header guard, your #include directives, "using", etc. and the class definitions. When I read the header, the former categories should read like boiler-plate and the class definition is what should stick out. By not separating them visually, some people might glance over the important details.

  Actually, it is ill-advised to put using inside a header, because it may cause name clashes with files that may #include you and want to use those names.

• MazeInit and MazeCarve. Why start these names with Maze? You're already in the Maze class.

• MazeInit seems like a very verbose way to zero out a buffer. Note that std::vector<T>::resize can set array elements to some initial value. I'm thinking something like this:

  std::vector<int> initialValues;
  
  initialValues.resize(width, MazeConstants::INVALID);
  maze.resize(height, initialValues);</pre></p>
  

• It's somewhat hard for me to guess what Carve is doing. Variable names like temp don't really help. I would add an overall comment to describe the technique. The existing comments in that function assume you already know the algorithm - eg. "came from east" - huh? I'm sure that makes sense in the context of the algorithm but if you're reading this for the first time it's not obvious. (I would also try to make this function a bit less repetitive... Is there some way you can express the various directions east/west/north/south as an array of constants to loop through and perform the repetitive action?)

  Also I have some points about data representation and memory layout that I would like to raise... These are nitpicky and I'm not necessarily suggesting you rewrite your code, just asking to think about this as a thought exercise.

• I may get flamed from C++ people who hate the C style, but you can also imagine a different representation for the matrix. One approach would be to drop the STL containers; a simple integer array might do, and can get you a better memory layout than indirection-laden vectors. (With vector<vector<int>>, every access does 2 pointer dereferences and the rows are potentially non-contiguous.) It would also change your initialization to a simple memset and it wouldn't perform any extra allocations. This will probably not make a huge difference for performance and is a bit of a religious matter for some; take this suggestion with a grain of salt.

• While on the topic of alternate matrix representations, another approach would be to switch from vector<vector<int>> to simply 1-dimensional vector<int>; accessing a location (x,y) would then become an access of (y * width + x). Like the C-style approach, this would also give you less indirection while accessing elements (1 pointer dereference instead of 2, contiguous elements), though you may have to adjust some loops so that they're written in a "line-by-line" fashion. Be careful about doing this multiplication at every point, because in my experience that can add up.