Marcus_Maze_Generation

#include <iostream>
#include "Maze.h"
#include <stack>
#include <stdlib.h>
#include <algorithm> // random_shuffle
#include <ctime>
#include <sstream>
typedef unsigned int Uint;
enum { north, east, south, west };
const char Maze::WALL = '#';
const char Maze::PATH = ' ';
//const char Maze::VISITED = '_';
//const unsigned int Maze::SIZE = 100;

unsigned int VisitedCells, TotalCells, x, y;
std::pair <unsigned int, unsigned int> CurrentCell;
std::vector< std::pair<unsigned int, unsigned int> > NeighboursToVisit;
std::vector<unsigned int> Direction;
std::stack< std::pair<Uint, Uint> > CellStack;


void Maze::Create_maze(Uint row, Uint col){
    // Fill the vector<vector> with astrix
    Map = std::vector< std::vector<char> >(row, std::vector<char>(col, WALL));
    // CellStack to hold list of all cell locations
    // Number of cells in the grid/map
    TotalCells = row*col;
    // Mark first CurrentCell as (1,1)
    CurrentCell = std::make_pair(1,1);
    // Set visited cells to 1
    VisitedCells = 1;
    Generate_maze(CurrentCell);
}
void Maze::Generate_maze(std::pair<Uint, Uint> CurrentCell){
    srand (time(NULL));
    int RandElement;
    //while (VisitedCells < TotalCells){
    for(int i = 0;i<15;i++){
        // To check the direction of neighbour
        x = CurrentCell.first, y = CurrentCell.second;
        std::string s;
        std::stringstream out;
        out << i;
        s = out.str();
        Map[x][y]=s[0];
        // NeighboursToVisit is an vector<pair<Uint, Uint> >
        NeighboursToVisit.clear();
        NeighboursToVisit = Find_neighbours(CurrentCell);
        RandElement = rand()%NeighboursToVisit.size();
        if (!NeighboursToVisit.empty()){
            // Shuffle the order to make it random
            //std::random_shuffle ( NeighboursToVisit.begin(), NeighboursToVisit.end() );
            // Keep track of the direction
            Direction = Check_direction(x, y, NeighboursToVisit);
            // Knock down the wall between this random cell and CurrentCell
            Crush_wall(NeighboursToVisit[RandElement], Direction[RandElement]);
            // Push CurrentCell to the cellStack
            CellStack.push(std::make_pair(CurrentCell.first, CurrentCell.second));
            CurrentCell = std::make_pair(NeighboursToVisit[RandElement].first, NeighboursToVisit[RandElement].second);
            VisitedCells++;
        }
        else{
            if(!CellStack.empty()){
                CurrentCell = CellStack.top();
                CellStack.pop();
            }
        }
    }
}
// x, y is the previous value of CurrentCell
std::vector<Uint> Maze::Check_direction(Uint x, Uint y, std::vector<std::pair <Uint, Uint> > v){
    std::vector<Uint> dir;
    int dx, dy;
    dir.clear();
    for (int i = 0; i < v.size(); i++)
    {
        dx = (v[i].first - x); // Computing the direction
        dy = (v[i].second - y); // Computing the direction
        std::cout << dx << " " << dy << std::endl;

        if (dx == 2)            // If east
            dir.push_back(1); // Push 1 (east by the enumeration)
        else if (dx == -2)  // if west
            dir.push_back(3); // Push 3 (west by the enumeration)
        else if (dy == -2)  // if north
            dir.push_back(0); // push 0 (north by the enumeration)
        else if (dy == 2)   // if south
            dir.push_back(2); // push 2 (south by the enumeration)
        std::cout << dir.back() << std::endl;
    }
    return dir;
}

std::vector< std::pair<Uint, Uint> > Maze::Find_neighbours(std::pair<Uint, Uint> CurrentCell){
    std::vector<std::pair <Uint, Uint> > v;
    CurrentCell.first+=2;   // East of original Cell
    if (Walls_Intact(CurrentCell))
        v.push_back(CurrentCell);

    CurrentCell.first-=4;   // West of original cell
    if (Walls_Intact(CurrentCell))
        v.push_back(CurrentCell);

    CurrentCell.first+=2;   // Back to original cell
    CurrentCell.second+=2;  // South of original cell
    if (Walls_Intact(CurrentCell))
        v.push_back(CurrentCell);

    CurrentCell.second-=4;  // North of original cell
    if (Walls_Intact(CurrentCell))
        v.push_back(CurrentCell);

    //CurrentCell.second-=2;    // Back to original cell
    return v;
}
bool Maze::Walls_Intact(std::pair<Uint, Uint> CurrentCell){ // Returns wether all walls intact or not
    int row = CurrentCell.first;
    int col = CurrentCell.second;
    if (col-1 >= Map.size() || row-1 >= Map[col-1].size())
        return false;
    if(col < Map.size() && row < Map[row].size()){
        if(
            (Map[row+1][col] == WALL) &&    // check east wall
            (Map[row-1][col] == WALL) &&    // check west wall
            (Map[row][col-1] == WALL) &&    // check north wall
            (Map[row][col+1] == WALL))      // check south wall
        {
            return true;
        }else{
            return false;
        }
        return false;
    }
    return false;
}


void Maze::Crush_wall(std::pair<Uint, Uint> CurrentCell, int dir){
    if (dir == north){
        Map[CurrentCell.first][CurrentCell.second+1] = 'w';
    }
    else if (dir == east){
        Map[CurrentCell.first-1][CurrentCell.second] = 's';
    }
    else if (dir == south){
        Map[CurrentCell.first][CurrentCell.second-1] = 'e';
    }
    else if (dir == west){
        Map[CurrentCell.first+1][CurrentCell.second] = 'n';
    }
}


void Maze::Print_maze() const{
    for (int i = 0; i < Map.size(); i++)
    {
        for (int j = 0; j < Map[i].size(); j++)
        {
            std::cout << Map[i][j];
        }
        std::cout << std::endl;
    }
}