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 */
