MORTAL2000/maze00.cpp

## maze00.cpp
/*******************************************************************************************
* Name:             Jay Seong                                                              *
* Description:      Randomly generates a perfect maze using depth-first search algorithm   *
* Date:             02/11/2010                                                             *
* Data Structures:  Double array of structs for cells, stack for back-tracking             *
* Others:           fstream is used to save maze into a file                               *
*                                                                                          *
* NOTE: Transcribed from a YouTube video https://www.youtube.com/watch?v=EvAzVhAii_o by    *
* Stephen Pendley to distribute for public use.  All credit for this version of the code   *
* and it's original goes to Jay Seong.                                                     *
*******************************************************************************************/

#include <iostream>
#include <ctime>
#include <windows.h>
#include <conio.h>
#include <stack>
#include <fstream>
//#include "stdafx.h" //http://sourceforge.net/p/wpbdc/website/ci/master/tree/Judge/StdAfx.h

using namespace std;

/********************************
* USED FOR THE SIZE OF THE MAZE *
*   Must be an odd number for   *
*    maze traversal reasons     *
********************************/
#define SIZE 11

// CELL STRUCTURE
struct Cell
{
	bool visited;
	bool top_wall;
	bool bot_wall;
	bool left_wall;
	bool right_wall;
	char display;
};

// FUNCTION DECLARATIONS
void Initialize(Cell Level[][SIZE]);
void ClearScreen();
void Redraw(Cell Level[][SIZE]);
void GenerateMaze(Cell Level[][SIZE], int &posX, int &posY, int &goalX, int &goalY);
void SaveMaze(Cell Level[][SIZE]);

// MAIN
int main() {
	Cell Level[SIZE][SIZE];
	int posX = 0;
	int posY = 0;
	int goalX = 0;
	int goalY = 0;
	bool game_over = false;

	while(!game_over) {
		system("cls");
		Initialize(Level);
		Redraw(Level);
		GenerateMaze(Level, posX, posY, goalX, goalY);
		SaveMaze(Level);

		char input;
		cout << "Create a new Maze? (Y)/(N): ";
		cin >> input;

		if((input != 'n') && (input != 'N') && (input != 'y') && (input != 'Y'))
			cout << "Invalid option" << endl;
		else if((input == 'n') || (input == 'N')) {
			game_over = true;
			cout << "Good bye!" << endl;
		}
	}

	_getch();
	return 0;
}

// INITIALIZE MAZE
void Initialize(Cell Level[][SIZE]) {
	for(int i=0; i<SIZE; i++) {
		for(int j=0; j<SIZE; j++) {
			Level[i][j].display = '*';
			Level[i][j].visited = false;
			Level[i][j].top_wall = true;
			Level[i][j].bot_wall = true;
			Level[i][j].left_wall = true;
			Level[i][j].right_wall = true;
		}
	}
	for(int i=1; i<SIZE-1; i++) {
		for(int j=1; j<SIZE-1; j++) {
			// Border Cells have fewer accessible walls
			Level[1][j].top_wall = false;
			Level[SIZE-2][j].bot_wall = false;
			Level[i][1].left_wall = false;
			Level[i][SIZE-2].right_wall = false;
		}
	}
}

// CLEAR SCREEN
void ClearScreen()
{
	HANDLE hOut;
	COORD Position;
	hOut = GetStdHandle(STD_OUTPUT_HANDLE);
	Position.X = 0;
	Position.Y = 0;
	SetConsoleCursorPosition(hOut, Position);
}

// REDRAW MAZE
void Redraw(Cell Level[][SIZE]) {
	for(int i=0; i<SIZE; i++) {
		cout << endl;
		for(int j=0; j< SIZE; j++)
			cout << " " << Level[i][j].display;
	}
}

// GENERATE MAZE
void GenerateMaze(Cell Level[][SIZE], int &posX, int &posY, int &goalX, int &goalY) {
	srand((unsigned)time(NULL));				        					// Pick random start cell
	int random = 0;
	int randomX = ((2*rand())+1)%(SIZE-1);						// Generate a random odd number between 1 and SIZE
	int randomY = ((2*rand())+1)%(SIZE-1);						// Generate a random odd number between 1 and SIZE
	posX = randomX;                       						// Save player's initial X position
	posY = randomY;                      						// Save player's initial Y position
	int visitedCells = 1;
	int totalCells = ((SIZE-1)/2)*((SIZE-1)/2);
	int percent = 0;
	stack<int> back_trackX, back_trackY; 						// Stack is used to trace the reverse path

	Level[randomY][randomX].display = 'S';						// Set S as the start cell
	Level[randomY][randomX].visited = true;						// Set start cell as visited;

	while(visitedCells < totalCells)
	{
		if(((Level[randomY-2][randomX].visited == false)
        && (Level[randomY][randomX].top_wall == true
        && Level[randomY-2][randomX].bot_wall == true)) ||
		   ((Level[randomY+2][randomX].visited == false)
        && (Level[randomY][randomX].bot_wall == true
        && Level[randomY+2][randomX].top_wall == true)) ||
		   ((Level[randomY][randomX-2].visited == false)
        && (Level[randomY][randomX].left_wall == true
        && Level[randomY][randomX-2].right_wall == true)) ||
		   ((Level[randomY][randomX+2].visited == false)
        && (Level[randomY][randomX].right_wall == true
        && Level[randomY][randomX+2].left_wall == true)))
		{
			random = (rand() % 4) + 1;		// Pick a random wall 1-4 to knock down

			 // GO UP
			if((random == 1) && (randomY > 1)) {
				if(Level[randomY-2][randomX].visited == false) {	// If not visited
					Level[randomY-1][randomX].display = ' ';	// Delete display
					Level[randomY-1][randomX].visited = true;	// Mark cell as visited
					Level[randomY][randomX].top_wall = false;	// Knock down wall

					back_trackX.push(randomX); 			// Push X for back track
					back_trackY.push(randomY);			// Push Y for back track

					randomY -= 2;					// Move to next cell
					Level[randomY][randomX].visited = true;		// Mark cell moved to as visited
					Level[randomY][randomX].display = ' ';		// Update path
					Level[randomY][randomX].bot_wall = false;	// Knock down wall
					visitedCells++;					// Increase visitedCells counter
				}
				else
					continue;
			}

			// GO DOWN
			else if((random == 2) && (randomY < SIZE-2)) {
				if(Level[randomY+2][randomX].visited == false) {	// If not visited
					Level[randomY+1][randomX].display = ' ';	// Delete display
					Level[randomY+1][randomX].visited = true;	// Mark cell as visited
					Level[randomY][randomX].bot_wall = false;	// Knock down wall

					back_trackX.push(randomX); 			// Push X for back track
					back_trackY.push(randomY);			// Push Y for back track

					randomY += 2;					// Move to next cell
					Level[randomY][randomX].visited = true;		// Mark cell moved to as visited
					Level[randomY][randomX].display = ' ';		// Update path
					Level[randomY][randomX].top_wall = false;	// Knock down wall
					visitedCells++;					// Increase visitedCells counter
				}
				else
					continue;
			}

			// GO LEFT
			else if((random == 3) && (randomX > 1)) {
				if(Level[randomY][randomX-2].visited == false) {	// If not visited
					Level[randomY][randomX-1].display = ' ';	// Delete display
					Level[randomY][randomX-1].visited = true;	// Mark cell as visited
					Level[randomY][randomX].left_wall = false;	// Knock down wall

					back_trackX.push(randomX); 			// Push X for back track
					back_trackY.push(randomY);			// Push Y for back track

					randomX -= 2;					// Move to next cell
					Level[randomY][randomX].visited = true;		// Mark cell moved to as visited
					Level[randomY][randomX].display = ' ';		// Update path
					Level[randomY][randomX].right_wall = false;	// Knock down wall
					visitedCells++;					// Increase visitedCells counter
				}
				else
					continue;
			}

			// GO RIGHT
			else if((random == 4) && (randomX < SIZE-2)) {
				if(Level[randomY][randomX+2].visited == false) {	// If not visited
					Level[randomY][randomX+1].display = ' ';	// Delete display
					Level[randomY][randomX+1].visited = true;	// Mark cell as visited
					Level[randomY][randomX].right_wall = false;	// Knock down wall

					back_trackX.push(randomX); 			// Push X for back track
					back_trackY.push(randomY);			// Push Y for back track

					randomX += 2;					// Move to next cell
					Level[randomY][randomX].visited = true;		// Mark cell moved to as visited
					Level[randomY][randomX].display = ' ';		// Update path
					Level[randomY][randomX].left_wall = false;	// Knock down wall
					visitedCells++;					// Increase visitedCells counter
				}
				else
					continue;
			}

			percent = (visitedCells*100/totalCells*100)/100;		// Progress in percentage
			cout << endl << "	Generating a Random Maze... " << percent << "%" << endl;
		}
		else {
			randomX = back_trackX.top();
			back_trackX.pop();

			randomY = back_trackY.top();
			back_trackY.pop();
		}

		ClearScreen();
		Redraw(Level);
	}

	goalX = randomX;
	goalY = randomY;
	Level[goalY][goalX].display = 'E';
	system("cls");
	ClearScreen();
	Redraw(Level);
	cout << endl << "\a\t	Complete!" << endl;
}

// SAVE MAZE
void SaveMaze(Cell Level[][SIZE]) {
	ofstream output;
	char file[20];
	char input;

	cout << endl << "Save Maze? (Y)/(N): ";
	cin >> input;

	if ((input == 'y') || (input == 'Y')) {
		cout << endl << "Save as: ";
		cin >> file;

		output.open(file);

		for (int i = 0; i < SIZE; i++) {
			output << endl;
			for (int j = 0; j < SIZE; j++) {
				output << Level[i][j].display << " ";
			}
		}

		cout << "Maze has been saved to" << "\"" << file << "\"" << endl;
		output.close();
	}

}

## maze01.cpp
#include <fstream>
#include <iostream>
#include <memory>
#include <vector>
#include <cstdio>
#include <random>
#include <ctime>


//DEFINITON
std::mt19937 mt(time(NULL));

int randomize(int min, int max)
{
    std::uniform_int_distribution<int> dist_int(min, max);
    return dist_int(mt);
}

int randomize(int max)
{
    std::uniform_int_distribution<int> dist_int(0, max);
    return dist_int(mt);
}

//FORWARD DECLARATION
class Dungeon {
public:
    explicit Dungeon(int, int);
    const std::vector<char>& operator[] (int y) const;
    std::vector<char>& operator[] (int y);
    void generate();

    void setMin(int,int);
    void setMax(int,int);
    void setChars(char,char,char);
    void setMinRoomNum(int);

private:
    //User-defined types
    enum class dir_t {s_e, s_w, n_e, n_w};
    struct Room {
        int start_x, start_y;
        int end_x, end_y;
        dir_t dir;

        Room(int x, int y, int xx, int yy, const dir_t &d)
            : start_x{x}, start_y{y}, end_x{xx}, end_y{yy}, dir{d} {};
    };

    //Methods
    bool genRoom();
    bool check(const dir_t &, int, int);
    void genPassages();
    void genVestibule(const dir_t &, int);

    //Variables
    const int D_HEIGHT_, D_WIDTH_;
    std::vector<Room> room_vec_;
    int r_min_height_, r_min_width_;
    int r_max_height_, r_max_width_;
    char wall_, floor_, nothing_;
    int x_pos_, y_pos_;
    int counter_;
    int min_room_num_;
    //char** dungeon_;
    std::vector<std::vector<char>> dungeon_;
    bool is_executed_;
};


//DEFINITION
void Dungeon::setMin(int height, int width)
{
    if (height < 3 || height > D_HEIGHT_
        || width < 3 || width > D_WIDTH_)
    perror("Wrong setMin() parameters. It has to be more than 2 and less than or equal to D_HEIGHT_/D_WIDTH_");
    Dungeon::r_min_height_ = height;
    Dungeon::r_min_width_ = width;
}


void Dungeon::setMax(int height, int width)
{
    if (height < r_min_height_ || height > D_HEIGHT_
        || width < r_min_width_ || width > D_WIDTH_)
    perror("Wrong setMax() parameters. It should be more than r_min_height_/r_min_width_ and less than or equal to D_HEIGHT_/D_WIDTH_");
    Dungeon::r_max_height_ = height;
    Dungeon::r_max_width_ = width;
}


void Dungeon::setChars(char wall, char floor, char nothing)
{
    Dungeon::wall_ = wall;
    Dungeon::floor_ = floor;
    Dungeon::nothing_ = nothing;

//    for (int y = 0; y < D_HEIGHT_; y++) {
//        for (int x = 0; x < D_WIDTH_; x++) {
    for (auto& y : dungeon_) {
        for (auto& x : y) {
            x = nothing_;
        }
    }
}


void Dungeon::setMinRoomNum(int num)
{
    if (num < 0)
    perror("Wrong setMinRoomNum() parameter. It has to be more than or equal to 0");
    Dungeon::min_room_num_ = num;
}


Dungeon::Dungeon(int height, int width) : D_HEIGHT_{height}, D_WIDTH_{width}, dungeon_(D_HEIGHT_, std::vector<char>(D_WIDTH_))
{
//Make the "canvas"
//    dungeon_ = new char*[D_HEIGHT_];
//    for (int i = 0; i < D_HEIGHT_; i++)
//        dungeon_[i] = new char[D_WIDTH_];

//Set the default parameters
    setMin(4,4);
    setMax(D_HEIGHT_/4, D_WIDTH_/7);
    setChars('#','-','.');
    setMinRoomNum(30);

//Starting point of the first room
    y_pos_ = randomize(D_HEIGHT_);
    x_pos_ = randomize(D_WIDTH_);

//This is needed for genRoom() (recursive calls)
    counter_ = 1;
    is_executed_ = false;
}


//Dungeon::~Dungeon()
//{
//    //De-Allocate memory
////    for (int i = 0; i < D_HEIGHT_; ++i)
////        delete [] dungeon_[i];
////    delete [] dungeon_;
//}


void Dungeon::generate()
{
    //Draw the "dungeon" on a "canvas"
    while(!genRoom());
    genPassages();
}


//char Dungeon::operator[](int y)
//{
//    return dungeon_[y];
//}
const std::vector<char>& Dungeon::operator[] (int y) const { return dungeon_.at(y); }
std::vector<char>& Dungeon::operator[] (int y) { return dungeon_.at(y); }

bool Dungeon::genRoom()
{
//Room width and height
    int width = randomize(r_min_width_, r_max_width_);
    int height = randomize(r_min_height_, r_max_height_);

//s_e - south east; s_w - south west; n_e - north east; n_w - north west;
    dir_t s_e = dir_t::s_e;  dir_t n_e = dir_t::n_e;
    dir_t s_w = dir_t::s_w;  dir_t n_w = dir_t::n_w;

//Store possible directions in %dir_vec vector
    std::vector<dir_t> dir_vec;
    if (check(s_e, width, height)) {
        dir_vec.push_back(s_e);
    }
    if (check(s_w, width, height)) {
        dir_vec.push_back(s_w);
    }
    if (check(n_e, width, height)) {
        dir_vec.push_back(n_e);
    }
    if (check(n_w, width, height)) {
        dir_vec.push_back(n_w);
    }

//Do a little trick if there is no possible directions and less than %min_room_num rooms
    //!!! It is not guaranteed that the number of rooms will be equal to %min_room_num
    if (dir_vec.empty() && room_vec_.size() < min_room_num_) {
        if (room_vec_.size() - counter_ > 0) {
            x_pos_ = room_vec_[room_vec_.size() - counter_].end_x;
            y_pos_ = room_vec_[room_vec_.size() - counter_].end_y;
            counter_++;
            while (!genRoom());
            while (!genRoom());
        } else if (!is_executed_ && room_vec_.size() - counter_ == 0) {
            x_pos_ = room_vec_[0].start_x;
            y_pos_ = room_vec_[0].start_y;
            is_executed_ = true; //This condition should be executed only ONCE
            genRoom();
        }
    }

//Break if no possible directions
    if (dir_vec.empty()) return true;

//Make room in randomly selected direction
    dir_t rnd_dir = dir_vec[randomize(dir_vec.size() - 1)];
    switch (rnd_dir) {
    case dir_t::s_e:{
        for (int y = y_pos_; y < y_pos_ + height; y++) {
            for (int x = x_pos_; x < x_pos_ + width; x++) {
                if (y == y_pos_ || y == y_pos_ + (height-1)
                        || x == x_pos_ || x == x_pos_ + (width-1)) {
                    dungeon_[y][x] = wall_;
                } else {
                    dungeon_[y][x] = floor_;
                }
            }
        }
        //Keep track of all rooms
       // Room r {x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ + (height-1), s_e};
        room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ + (height-1), s_e);
        //Set y&&x position to the opposite corner
        y_pos_ += (height - 1);
        x_pos_ += (width - 1);
    }
        break;
    case dir_t::s_w: {
        for (int y = y_pos_; y < y_pos_ + height; y++) {
            for (int x = x_pos_; x > x_pos_ - width; x--) {
                if (y == y_pos_ || y == y_pos_ + (height-1)
                        || x == x_pos_ || x == x_pos_ - (width-1)) {
                    dungeon_[y][x] = wall_;
                } else {
                    dungeon_[y][x] = floor_;
                }
            }
        }
        //Room r {x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ + (height-1), s_w};
        room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ + (height-1), s_w);
        y_pos_ += (height - 1);
        x_pos_ -= (width - 1);
    }
        break;
    case dir_t::n_e: {
        for (int y = y_pos_; y > y_pos_ - height; y--) {
            for (int x = x_pos_; x < x_pos_ + width; x++) {
                if (y == y_pos_ || y == y_pos_ - (height-1)
                        || x == x_pos_ || x == x_pos_ + (width-1)) {
                    dungeon_[y][x] = wall_;
                } else {
                    dungeon_[y][x] = floor_;
                }
            }
        }
        //Room r {x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ - (height-1), n_e};
        room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ - (height-1), n_e);
        y_pos_ -= (height - 1);
        x_pos_ += (width - 1);
    }
        break;
    case dir_t::n_w: {
        for (int y = y_pos_; y > y_pos_ - height; y--) {
            for (int x = x_pos_; x > x_pos_ - width; x--) {
                if (y == y_pos_ || y == y_pos_ - (height-1)
                        || x == x_pos_ || x == x_pos_ - (width-1)) {
                    dungeon_[y][x] = wall_;
                } else {
                    dungeon_[y][x] = floor_;
                }
            }
        }
        //Room r {x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ - (height-1), n_w};
        room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ - (height-1), n_w);
        y_pos_ -= (height - 1);
        x_pos_ -= (width - 1);
    }
        break;
    }

//Signal that there is still possible directions left
    return false;
}


bool Dungeon::check(const dir_t& dir, int width, int height)
{
    //Check if it's possible to make room in the direction(%dir) that was passed
    switch(dir) {
    case dir_t::s_e:
        if (y_pos_ + height <= D_HEIGHT_ && x_pos_ + width <= D_WIDTH_) {
            for (int y = y_pos_; y < y_pos_ + height; y++) {
                for (int x = x_pos_; x < x_pos_ + width; x++) {
                    if (y == y_pos_ || y == y_pos_ + (height-1)
                            || x == x_pos_ || x == x_pos_ + (width-1)) continue; //Ignore wall_ collision
                    if (dungeon_[y][x] != nothing_) return false;
                }
            }
        } else return false;
        return true;
    case dir_t::s_w:
        if (y_pos_ + height <= D_HEIGHT_ && x_pos_ - width >= 0) {
            for (int y = y_pos_; y < y_pos_ + height; y++) {
                for (int x = x_pos_; x > x_pos_ - width; x--) {
                    if (y == y_pos_ || y == y_pos_ + (height-1)
                            || x == x_pos_ || x == x_pos_ - (width-1)) continue;
                    if (dungeon_[y][x] != nothing_) return false;
                }
            }
        } else return false;
        return true;
    case dir_t::n_e:
        if (y_pos_ - height >= 0 && x_pos_ + width <= D_WIDTH_) {
            for (int y = y_pos_; y > y_pos_ - height; y--) {
                for (int x = x_pos_; x < x_pos_ + width; x++) {
                    if (y == y_pos_ || y == y_pos_ - (height-1)
                            || x == x_pos_ || x == x_pos_ + (width-1)) continue;
                    if (dungeon_[y][x] != nothing_) return false;
                }
            }
        } else return false;
        return true;
    case dir_t::n_w:
        if (y_pos_ - height >= 0 && x_pos_ - width >= 0) {
            for (int y = y_pos_; y > y_pos_ - height; y--) {
                for (int x = x_pos_; x > x_pos_ - width; x--) {
                    if (y == y_pos_ || y == y_pos_ - (height-1)
                            || x == x_pos_ || x == x_pos_ - (width-1)) continue;
                    if (dungeon_[y][x] != nothing_) return false;
                }
            }
        } else return false;
        return true;
    }

    //Something went wrong if program reached this
    perror("Something wrong in check() function");
}


void Dungeon::genPassages()
{
    //Make passage between rooms
    for (int i = 1; i < room_vec_.size(); ++i) {
        for (int n = 1; n <= i; ++n) {
            if (room_vec_[i-n].end_y == room_vec_[i].start_y
                    && room_vec_[i-n].end_x == room_vec_[i].start_x) {
                switch (room_vec_[i-n].dir) {
                case dir_t::s_e :
                    if (room_vec_[i].dir == dir_t::s_e) {  //Because nested switches look ugly
                        genVestibule(dir_t::s_e, i);
                    } else if (room_vec_[i].dir == dir_t::s_w) {
                        dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
                    } else if (room_vec_[i].dir == dir_t::n_e) {
                        dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
                    }
                    break;
                case dir_t::s_w :
                    if (room_vec_[i].dir == dir_t::s_e) {
                        dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
                    } else if (room_vec_[i].dir == dir_t::s_w) {
                        genVestibule(dir_t::s_w, i);
                    } else if (room_vec_[i].dir == dir_t::n_w) {
                        dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
                    }
                    break;
                case dir_t::n_e :
                    if (room_vec_[i].dir == dir_t::s_e) {
                        dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
                    } else if (room_vec_[i].dir == dir_t::n_e) {
                        genVestibule(dir_t::n_e, i);
                    } else if (room_vec_[i].dir == dir_t::n_w) {
                        dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
                    }
                    break;
                case dir_t::n_w :
                    if (room_vec_[i].dir == dir_t::s_w) {
                        dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
                    } else if (room_vec_[i].dir == dir_t::n_e) {
                        dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
                    } else if (room_vec_[i].dir == dir_t::n_w) {
                        genVestibule(dir_t::n_w, i);
                    }
                    break;
                }
            }
        }
    }
}


void Dungeon::genVestibule(const dir_t& dir, int i)
{
    //This belongs to genPassages()
    //Have put this in separate method for the sake of clarity
    switch (dir) {
    case dir_t::s_w :
    case dir_t::n_e :
        //Draw the wall_s if this vestibule is not collapsing with other rooms
        if (dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 1] == nothing_) {
            dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x + 1] = wall_;
            dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x + 2] = wall_;
            dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 2] = wall_;
        }
        if (dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 1] == nothing_) {
            dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x - 2] = wall_;
            dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x - 1] = wall_;
            dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 2] = wall_;
        }

        dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
        dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 1] = floor_;
        dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 1] = floor_;
        dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 1] = floor_;
        dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
        dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 1] = floor_;
        dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
        dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
        dungeon_[room_vec_[i].start_y][room_vec_[i].start_x] = floor_;
        break;
    case dir_t::s_e :
    case dir_t::n_w :
        if (dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 1] == nothing_) {
            dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x - 1] = wall_;
            dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x - 2] = wall_;
            dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 2] = wall_;
            dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 1] = floor_;
            dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
            dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 1] = floor_;
            dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
            dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
            dungeon_[room_vec_[i].start_y][room_vec_[i].start_x] = floor_;
        }
        if (dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 1] == nothing_) {
            dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x + 2] = wall_;
            dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x + 1] = wall_;
            dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 2] = wall_;
            dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
            dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 1] = floor_;
            dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 1] = floor_;
            dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
            dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
            dungeon_[room_vec_[i].start_y][room_vec_[i].start_x] = floor_;
        }
        break;
    }
}

int main()
{
//Set the file stream
//    std::ofstream out("Output/dungeon.txt");
//    if(out.fail()){
//        perror("dungeon.txt");
//        return 1;
//    }

//Generate dungeon
    const int Height = 25;
    const int Width = 79;
    Dungeon dungeon(Height, Width);
    dungeon.setMax(Height/5, Width/9);
    dungeon.setMinRoomNum(60);
    dungeon.setChars('#','.',' ');
    dungeon.generate();

//Print dungeon to stream
    for (int y = 0; y < Height; y++){
        for (int x = 0; x < Width; x++){
            std::cout << dungeon[y][x];
        }
        std::cout << "\n";
    }
}
	/*******************************************************************************************
	* Name: Jay Seong *
	* Description: Randomly generates a perfect maze using depth-first search algorithm *
	* Date: 02/11/2010 *
	* Data Structures: Double array of structs for cells, stack for back-tracking *
	* Others: fstream is used to save maze into a file *
	* *
	* NOTE: Transcribed from a YouTube video https://www.youtube.com/watch?v=EvAzVhAii_o by *
	* Stephen Pendley to distribute for public use. All credit for this version of the code *
	* and it's original goes to Jay Seong. *
	*******************************************************************************************/

	#include <iostream>
	#include <ctime>
	#include <windows.h>
	#include <conio.h>
	#include <stack>
	#include <fstream>
	//#include "stdafx.h" //http://sourceforge.net/p/wpbdc/website/ci/master/tree/Judge/StdAfx.h

	using namespace std;

	/********************************
	* USED FOR THE SIZE OF THE MAZE *
	* Must be an odd number for *
	* maze traversal reasons *
	********************************/
	#define SIZE 11

	// CELL STRUCTURE
	struct Cell
	{
	bool visited;
	bool top_wall;
	bool bot_wall;
	bool left_wall;
	bool right_wall;
	char display;
	};

	// FUNCTION DECLARATIONS
	void Initialize(Cell Level[][SIZE]);
	void ClearScreen();
	void Redraw(Cell Level[][SIZE]);
	void GenerateMaze(Cell Level[][SIZE], int &posX, int &posY, int &goalX, int &goalY);
	void SaveMaze(Cell Level[][SIZE]);

	// MAIN
	int main() {
	Cell Level[SIZE][SIZE];
	int posX = 0;
	int posY = 0;
	int goalX = 0;
	int goalY = 0;
	bool game_over = false;

	while(!game_over) {
	system("cls");
	Initialize(Level);
	Redraw(Level);
	GenerateMaze(Level, posX, posY, goalX, goalY);
	SaveMaze(Level);

	char input;
	cout << "Create a new Maze? (Y)/(N): ";
	cin >> input;

	if((input != 'n') && (input != 'N') && (input != 'y') && (input != 'Y'))
	cout << "Invalid option" << endl;
	else if((input == 'n') \|\| (input == 'N')) {
	game_over = true;
	cout << "Good bye!" << endl;
	}
	}

	_getch();
	return 0;
	}

	// INITIALIZE MAZE
	void Initialize(Cell Level[][SIZE]) {
	for(int i=0; i<SIZE; i++) {
	for(int j=0; j<SIZE; j++) {
	Level[i][j].display = '*';
	Level[i][j].visited = false;
	Level[i][j].top_wall = true;
	Level[i][j].bot_wall = true;
	Level[i][j].left_wall = true;
	Level[i][j].right_wall = true;
	}
	}
	for(int i=1; i<SIZE-1; i++) {
	for(int j=1; j<SIZE-1; j++) {
	// Border Cells have fewer accessible walls
	Level[1][j].top_wall = false;
	Level[SIZE-2][j].bot_wall = false;
	Level[i][1].left_wall = false;
	Level[i][SIZE-2].right_wall = false;
	}
	}
	}

	// CLEAR SCREEN
	void ClearScreen()
	{
	HANDLE hOut;
	COORD Position;
	hOut = GetStdHandle(STD_OUTPUT_HANDLE);
	Position.X = 0;
	Position.Y = 0;
	SetConsoleCursorPosition(hOut, Position);
	}

	// REDRAW MAZE
	void Redraw(Cell Level[][SIZE]) {
	for(int i=0; i<SIZE; i++) {
	cout << endl;
	for(int j=0; j< SIZE; j++)
	cout << " " << Level[i][j].display;
	}
	}

	// GENERATE MAZE
	void GenerateMaze(Cell Level[][SIZE], int &posX, int &posY, int &goalX, int &goalY) {
	srand((unsigned)time(NULL)); // Pick random start cell
	int random = 0;
	int randomX = ((2*rand())+1)%(SIZE-1); // Generate a random odd number between 1 and SIZE
	int randomY = ((2*rand())+1)%(SIZE-1); // Generate a random odd number between 1 and SIZE
	posX = randomX; // Save player's initial X position
	posY = randomY; // Save player's initial Y position
	int visitedCells = 1;
	int totalCells = ((SIZE-1)/2)*((SIZE-1)/2);
	int percent = 0;
	stack<int> back_trackX, back_trackY; // Stack is used to trace the reverse path

	Level[randomY][randomX].display = 'S'; // Set S as the start cell
	Level[randomY][randomX].visited = true; // Set start cell as visited;

	while(visitedCells < totalCells)
	{
	if(((Level[randomY-2][randomX].visited == false)
	&& (Level[randomY][randomX].top_wall == true
	&& Level[randomY-2][randomX].bot_wall == true)) \|\|
	((Level[randomY+2][randomX].visited == false)
	&& (Level[randomY][randomX].bot_wall == true
	&& Level[randomY+2][randomX].top_wall == true)) \|\|
	((Level[randomY][randomX-2].visited == false)
	&& (Level[randomY][randomX].left_wall == true
	&& Level[randomY][randomX-2].right_wall == true)) \|\|
	((Level[randomY][randomX+2].visited == false)
	&& (Level[randomY][randomX].right_wall == true
	&& Level[randomY][randomX+2].left_wall == true)))
	{
	random = (rand() % 4) + 1; // Pick a random wall 1-4 to knock down

	// GO UP
	if((random == 1) && (randomY > 1)) {
	if(Level[randomY-2][randomX].visited == false) { // If not visited
	Level[randomY-1][randomX].display = ' '; // Delete display
	Level[randomY-1][randomX].visited = true; // Mark cell as visited
	Level[randomY][randomX].top_wall = false; // Knock down wall

	back_trackX.push(randomX); // Push X for back track
	back_trackY.push(randomY); // Push Y for back track

	randomY -= 2; // Move to next cell
	Level[randomY][randomX].visited = true; // Mark cell moved to as visited
	Level[randomY][randomX].display = ' '; // Update path
	Level[randomY][randomX].bot_wall = false; // Knock down wall
	visitedCells++; // Increase visitedCells counter
	}
	else
	continue;
	}

	// GO DOWN
	else if((random == 2) && (randomY < SIZE-2)) {
	if(Level[randomY+2][randomX].visited == false) { // If not visited
	Level[randomY+1][randomX].display = ' '; // Delete display
	Level[randomY+1][randomX].visited = true; // Mark cell as visited
	Level[randomY][randomX].bot_wall = false; // Knock down wall

	back_trackX.push(randomX); // Push X for back track
	back_trackY.push(randomY); // Push Y for back track

	randomY += 2; // Move to next cell
	Level[randomY][randomX].visited = true; // Mark cell moved to as visited
	Level[randomY][randomX].display = ' '; // Update path
	Level[randomY][randomX].top_wall = false; // Knock down wall
	visitedCells++; // Increase visitedCells counter
	}
	else
	continue;
	}

	// GO LEFT
	else if((random == 3) && (randomX > 1)) {
	if(Level[randomY][randomX-2].visited == false) { // If not visited
	Level[randomY][randomX-1].display = ' '; // Delete display
	Level[randomY][randomX-1].visited = true; // Mark cell as visited
	Level[randomY][randomX].left_wall = false; // Knock down wall

	back_trackX.push(randomX); // Push X for back track
	back_trackY.push(randomY); // Push Y for back track

	randomX -= 2; // Move to next cell
	Level[randomY][randomX].visited = true; // Mark cell moved to as visited
	Level[randomY][randomX].display = ' '; // Update path
	Level[randomY][randomX].right_wall = false; // Knock down wall
	visitedCells++; // Increase visitedCells counter
	}
	else
	continue;
	}

	// GO RIGHT
	else if((random == 4) && (randomX < SIZE-2)) {
	if(Level[randomY][randomX+2].visited == false) { // If not visited
	Level[randomY][randomX+1].display = ' '; // Delete display
	Level[randomY][randomX+1].visited = true; // Mark cell as visited
	Level[randomY][randomX].right_wall = false; // Knock down wall

	back_trackX.push(randomX); // Push X for back track
	back_trackY.push(randomY); // Push Y for back track

	randomX += 2; // Move to next cell
	Level[randomY][randomX].visited = true; // Mark cell moved to as visited
	Level[randomY][randomX].display = ' '; // Update path
	Level[randomY][randomX].left_wall = false; // Knock down wall
	visitedCells++; // Increase visitedCells counter
	}
	else
	continue;
	}

	percent = (visitedCells100/totalCells100)/100; // Progress in percentage
	cout << endl << " Generating a Random Maze... " << percent << "%" << endl;
	}
	else {
	randomX = back_trackX.top();
	back_trackX.pop();

	randomY = back_trackY.top();
	back_trackY.pop();
	}

	ClearScreen();
	Redraw(Level);
	}

	goalX = randomX;
	goalY = randomY;
	Level[goalY][goalX].display = 'E';
	system("cls");
	ClearScreen();
	Redraw(Level);
	cout << endl << "\a\t Complete!" << endl;
	}

	// SAVE MAZE
	void SaveMaze(Cell Level[][SIZE]) {
	ofstream output;
	char file[20];
	char input;

	cout << endl << "Save Maze? (Y)/(N): ";
	cin >> input;

	if ((input == 'y') \|\| (input == 'Y')) {
	cout << endl << "Save as: ";
	cin >> file;

	output.open(file);

	for (int i = 0; i < SIZE; i++) {
	output << endl;
	for (int j = 0; j < SIZE; j++) {
	output << Level[i][j].display << " ";
	}
	}

	cout << "Maze has been saved to" << "\"" << file << "\"" << endl;
	output.close();
	}

	}
	#include <fstream>
	#include <iostream>
	#include <memory>
	#include <vector>
	#include <cstdio>
	#include <random>
	#include <ctime>


	//DEFINITON
	std::mt19937 mt(time(NULL));

	int randomize(int min, int max)
	{
	std::uniform_int_distribution<int> dist_int(min, max);
	return dist_int(mt);
	}

	int randomize(int max)
	{
	std::uniform_int_distribution<int> dist_int(0, max);
	return dist_int(mt);
	}

	//FORWARD DECLARATION
	class Dungeon {
	public:
	explicit Dungeon(int, int);
	const std::vector<char>& operator[] (int y) const;
	std::vector<char>& operator[] (int y);
	void generate();

	void setMin(int,int);
	void setMax(int,int);
	void setChars(char,char,char);
	void setMinRoomNum(int);

	private:
	//User-defined types
	enum class dir_t {s_e, s_w, n_e, n_w};
	struct Room {
	int start_x, start_y;
	int end_x, end_y;
	dir_t dir;

	Room(int x, int y, int xx, int yy, const dir_t &d)
	: start_x{x}, start_y{y}, end_x{xx}, end_y{yy}, dir{d} {};
	};

	//Methods
	bool genRoom();
	bool check(const dir_t &, int, int);
	void genPassages();
	void genVestibule(const dir_t &, int);

	//Variables
	const int D_HEIGHT_, D_WIDTH_;
	std::vector<Room> room_vec_;
	int r_min_height_, r_min_width_;
	int r_max_height_, r_max_width_;
	char wall_, floor_, nothing_;
	int x_pos_, y_pos_;
	int counter_;
	int min_room_num_;
	//char** dungeon_;
	std::vector<std::vector<char>> dungeon_;
	bool is_executed_;
	};


	//DEFINITION
	void Dungeon::setMin(int height, int width)
	{
	if (height < 3 \|\| height > D_HEIGHT_
	\|\| width < 3 \|\| width > D_WIDTH_)
	perror("Wrong setMin() parameters. It has to be more than 2 and less than or equal to D_HEIGHT_/D_WIDTH_");
	Dungeon::r_min_height_ = height;
	Dungeon::r_min_width_ = width;
	}


	void Dungeon::setMax(int height, int width)
	{
	if (height < r_min_height_ \|\| height > D_HEIGHT_
	\|\| width < r_min_width_ \|\| width > D_WIDTH_)
	perror("Wrong setMax() parameters. It should be more than r_min_height_/r_min_width_ and less than or equal to D_HEIGHT_/D_WIDTH_");
	Dungeon::r_max_height_ = height;
	Dungeon::r_max_width_ = width;
	}


	void Dungeon::setChars(char wall, char floor, char nothing)
	{
	Dungeon::wall_ = wall;
	Dungeon::floor_ = floor;
	Dungeon::nothing_ = nothing;

	// for (int y = 0; y < D_HEIGHT_; y++) {
	// for (int x = 0; x < D_WIDTH_; x++) {
	for (auto& y : dungeon_) {
	for (auto& x : y) {
	x = nothing_;
	}
	}
	}


	void Dungeon::setMinRoomNum(int num)
	{
	if (num < 0)
	perror("Wrong setMinRoomNum() parameter. It has to be more than or equal to 0");
	Dungeon::min_room_num_ = num;
	}


	Dungeon::Dungeon(int height, int width) : D_HEIGHT_{height}, D_WIDTH_{width}, dungeon_(D_HEIGHT_, std::vector<char>(D_WIDTH_))
	{
	//Make the "canvas"
	// dungeon_ = new char*[D_HEIGHT_];
	// for (int i = 0; i < D_HEIGHT_; i++)
	// dungeon_[i] = new char[D_WIDTH_];

	//Set the default parameters
	setMin(4,4);
	setMax(D_HEIGHT_/4, D_WIDTH_/7);
	setChars('#','-','.');
	setMinRoomNum(30);

	//Starting point of the first room
	y_pos_ = randomize(D_HEIGHT_);
	x_pos_ = randomize(D_WIDTH_);

	//This is needed for genRoom() (recursive calls)
	counter_ = 1;
	is_executed_ = false;
	}


	//Dungeon::~Dungeon()
	//{
	// //De-Allocate memory
	//// for (int i = 0; i < D_HEIGHT_; ++i)
	//// delete [] dungeon_[i];
	//// delete [] dungeon_;
	//}


	void Dungeon::generate()
	{
	//Draw the "dungeon" on a "canvas"
	while(!genRoom());
	genPassages();
	}


	//char Dungeon::operator[](int y)
	//{
	// return dungeon_[y];
	//}
	const std::vector<char>& Dungeon::operator[] (int y) const { return dungeon_.at(y); }
	std::vector<char>& Dungeon::operator[] (int y) { return dungeon_.at(y); }

	bool Dungeon::genRoom()
	{
	//Room width and height
	int width = randomize(r_min_width_, r_max_width_);
	int height = randomize(r_min_height_, r_max_height_);

	//s_e - south east; s_w - south west; n_e - north east; n_w - north west;
	dir_t s_e = dir_t::s_e; dir_t n_e = dir_t::n_e;
	dir_t s_w = dir_t::s_w; dir_t n_w = dir_t::n_w;

	//Store possible directions in %dir_vec vector
	std::vector<dir_t> dir_vec;
	if (check(s_e, width, height)) {
	dir_vec.push_back(s_e);
	}
	if (check(s_w, width, height)) {
	dir_vec.push_back(s_w);
	}
	if (check(n_e, width, height)) {
	dir_vec.push_back(n_e);
	}
	if (check(n_w, width, height)) {
	dir_vec.push_back(n_w);
	}

	//Do a little trick if there is no possible directions and less than %min_room_num rooms
	//!!! It is not guaranteed that the number of rooms will be equal to %min_room_num
	if (dir_vec.empty() && room_vec_.size() < min_room_num_) {
	if (room_vec_.size() - counter_ > 0) {
	x_pos_ = room_vec_[room_vec_.size() - counter_].end_x;
	y_pos_ = room_vec_[room_vec_.size() - counter_].end_y;
	counter_++;
	while (!genRoom());
	while (!genRoom());
	} else if (!is_executed_ && room_vec_.size() - counter_ == 0) {
	x_pos_ = room_vec_[0].start_x;
	y_pos_ = room_vec_[0].start_y;
	is_executed_ = true; //This condition should be executed only ONCE
	genRoom();
	}
	}

	//Break if no possible directions
	if (dir_vec.empty()) return true;

	//Make room in randomly selected direction
	dir_t rnd_dir = dir_vec[randomize(dir_vec.size() - 1)];
	switch (rnd_dir) {
	case dir_t::s_e:{
	for (int y = y_pos_; y < y_pos_ + height; y++) {
	for (int x = x_pos_; x < x_pos_ + width; x++) {
	if (y == y_pos_ \|\| y == y_pos_ + (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ + (width-1)) {
	dungeon_[y][x] = wall_;
	} else {
	dungeon_[y][x] = floor_;
	}
	}
	}
	//Keep track of all rooms
	// Room r {x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ + (height-1), s_e};
	room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ + (height-1), s_e);
	//Set y&&x position to the opposite corner
	y_pos_ += (height - 1);
	x_pos_ += (width - 1);
	}
	break;
	case dir_t::s_w: {
	for (int y = y_pos_; y < y_pos_ + height; y++) {
	for (int x = x_pos_; x > x_pos_ - width; x--) {
	if (y == y_pos_ \|\| y == y_pos_ + (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ - (width-1)) {
	dungeon_[y][x] = wall_;
	} else {
	dungeon_[y][x] = floor_;
	}
	}
	}
	//Room r {x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ + (height-1), s_w};
	room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ + (height-1), s_w);
	y_pos_ += (height - 1);
	x_pos_ -= (width - 1);
	}
	break;
	case dir_t::n_e: {
	for (int y = y_pos_; y > y_pos_ - height; y--) {
	for (int x = x_pos_; x < x_pos_ + width; x++) {
	if (y == y_pos_ \|\| y == y_pos_ - (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ + (width-1)) {
	dungeon_[y][x] = wall_;
	} else {
	dungeon_[y][x] = floor_;
	}
	}
	}
	//Room r {x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ - (height-1), n_e};
	room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ + (width-1), y_pos_ - (height-1), n_e);
	y_pos_ -= (height - 1);
	x_pos_ += (width - 1);
	}
	break;
	case dir_t::n_w: {
	for (int y = y_pos_; y > y_pos_ - height; y--) {
	for (int x = x_pos_; x > x_pos_ - width; x--) {
	if (y == y_pos_ \|\| y == y_pos_ - (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ - (width-1)) {
	dungeon_[y][x] = wall_;
	} else {
	dungeon_[y][x] = floor_;
	}
	}
	}
	//Room r {x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ - (height-1), n_w};
	room_vec_.emplace_back(x_pos_, y_pos_, x_pos_ - (width-1), y_pos_ - (height-1), n_w);
	y_pos_ -= (height - 1);
	x_pos_ -= (width - 1);
	}
	break;
	}

	//Signal that there is still possible directions left
	return false;
	}


	bool Dungeon::check(const dir_t& dir, int width, int height)
	{
	//Check if it's possible to make room in the direction(%dir) that was passed
	switch(dir) {
	case dir_t::s_e:
	if (y_pos_ + height <= D_HEIGHT_ && x_pos_ + width <= D_WIDTH_) {
	for (int y = y_pos_; y < y_pos_ + height; y++) {
	for (int x = x_pos_; x < x_pos_ + width; x++) {
	if (y == y_pos_ \|\| y == y_pos_ + (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ + (width-1)) continue; //Ignore wall_ collision
	if (dungeon_[y][x] != nothing_) return false;
	}
	}
	} else return false;
	return true;
	case dir_t::s_w:
	if (y_pos_ + height <= D_HEIGHT_ && x_pos_ - width >= 0) {
	for (int y = y_pos_; y < y_pos_ + height; y++) {
	for (int x = x_pos_; x > x_pos_ - width; x--) {
	if (y == y_pos_ \|\| y == y_pos_ + (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ - (width-1)) continue;
	if (dungeon_[y][x] != nothing_) return false;
	}
	}
	} else return false;
	return true;
	case dir_t::n_e:
	if (y_pos_ - height >= 0 && x_pos_ + width <= D_WIDTH_) {
	for (int y = y_pos_; y > y_pos_ - height; y--) {
	for (int x = x_pos_; x < x_pos_ + width; x++) {
	if (y == y_pos_ \|\| y == y_pos_ - (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ + (width-1)) continue;
	if (dungeon_[y][x] != nothing_) return false;
	}
	}
	} else return false;
	return true;
	case dir_t::n_w:
	if (y_pos_ - height >= 0 && x_pos_ - width >= 0) {
	for (int y = y_pos_; y > y_pos_ - height; y--) {
	for (int x = x_pos_; x > x_pos_ - width; x--) {
	if (y == y_pos_ \|\| y == y_pos_ - (height-1)
	\|\| x == x_pos_ \|\| x == x_pos_ - (width-1)) continue;
	if (dungeon_[y][x] != nothing_) return false;
	}
	}
	} else return false;
	return true;
	}

	//Something went wrong if program reached this
	perror("Something wrong in check() function");
	}


	void Dungeon::genPassages()
	{
	//Make passage between rooms
	for (int i = 1; i < room_vec_.size(); ++i) {
	for (int n = 1; n <= i; ++n) {
	if (room_vec_[i-n].end_y == room_vec_[i].start_y
	&& room_vec_[i-n].end_x == room_vec_[i].start_x) {
	switch (room_vec_[i-n].dir) {
	case dir_t::s_e :
	if (room_vec_[i].dir == dir_t::s_e) { //Because nested switches look ugly
	genVestibule(dir_t::s_e, i);
	} else if (room_vec_[i].dir == dir_t::s_w) {
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
	} else if (room_vec_[i].dir == dir_t::n_e) {
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
	}
	break;
	case dir_t::s_w :
	if (room_vec_[i].dir == dir_t::s_e) {
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
	} else if (room_vec_[i].dir == dir_t::s_w) {
	genVestibule(dir_t::s_w, i);
	} else if (room_vec_[i].dir == dir_t::n_w) {
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
	}
	break;
	case dir_t::n_e :
	if (room_vec_[i].dir == dir_t::s_e) {
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
	} else if (room_vec_[i].dir == dir_t::n_e) {
	genVestibule(dir_t::n_e, i);
	} else if (room_vec_[i].dir == dir_t::n_w) {
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
	}
	break;
	case dir_t::n_w :
	if (room_vec_[i].dir == dir_t::s_w) {
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
	} else if (room_vec_[i].dir == dir_t::n_e) {
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
	} else if (room_vec_[i].dir == dir_t::n_w) {
	genVestibule(dir_t::n_w, i);
	}
	break;
	}
	}
	}
	}
	}


	void Dungeon::genVestibule(const dir_t& dir, int i)
	{
	//This belongs to genPassages()
	//Have put this in separate method for the sake of clarity
	switch (dir) {
	case dir_t::s_w :
	case dir_t::n_e :
	//Draw the wall_s if this vestibule is not collapsing with other rooms
	if (dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 1] == nothing_) {
	dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x + 1] = wall_;
	dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x + 2] = wall_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 2] = wall_;
	}
	if (dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 1] == nothing_) {
	dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x - 2] = wall_;
	dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x - 1] = wall_;
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 2] = wall_;
	}

	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 1] = floor_;
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 1] = floor_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 1] = floor_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x] = floor_;
	break;
	case dir_t::s_e :
	case dir_t::n_w :
	if (dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 1] == nothing_) {
	dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x - 1] = wall_;
	dungeon_[room_vec_[i].start_y + 2][room_vec_[i].start_x - 2] = wall_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 2] = wall_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x - 1] = floor_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x] = floor_;
	dungeon_[room_vec_[i].start_y + 1][room_vec_[i].start_x + 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x] = floor_;
	}
	if (dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 1] == nothing_) {
	dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x + 2] = wall_;
	dungeon_[room_vec_[i].start_y - 2][room_vec_[i].start_x + 1] = wall_;
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 2] = wall_;
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x] = floor_;
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x + 1] = floor_;
	dungeon_[room_vec_[i].start_y - 1][room_vec_[i].start_x - 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x - 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x + 1] = floor_;
	dungeon_[room_vec_[i].start_y][room_vec_[i].start_x] = floor_;
	}
	break;
	}
	}

	int main()
	{
	//Set the file stream
	// std::ofstream out("Output/dungeon.txt");
	// if(out.fail()){
	// perror("dungeon.txt");
	// return 1;
	// }

	//Generate dungeon
	const int Height = 25;
	const int Width = 79;
	Dungeon dungeon(Height, Width);
	dungeon.setMax(Height/5, Width/9);
	dungeon.setMinRoomNum(60);
	dungeon.setChars('#','.',' ');
	dungeon.generate();

	//Print dungeon to stream
	for (int y = 0; y < Height; y++){
	for (int x = 0; x < Width; x++){
	std::cout << dungeon[y][x];
	}
	std::cout << "\n";
	}
	}