/*******************************************************************************
Method: genMaze (COORDTYPE v)
Purpose: Generates maze in local grid.
Input: COORDTYPE vertex
Output: none
Returns: none
Note: Maze is generated using Depth-First Search (DFS) algorithm
Pre condition: first element is pushed onto stack by calling method.
Post condition: A less-than perfect maze in 2D grid

      dfs(vertex v) { -- dfs pseudocode for binary tree branching --
         visit(v);
         for each neighbor w of v
           if w is unvisited {
             dfs(w);
             add edge vw to tree T
           }
      }
      
      DFS is frequently implemented using backtracking:

      1. Make the initial cell the current cell and mark it as visited
      2. While there are unvisited cells
         1. If the current cell has any unvisited neighbours
             a) Choose randomly one of the unvisited neighbours
             b) Push the chosen one onto stack
             c) Remove the wall between the current cell and the chosen one
             d) Make the chosen one the current cell and mark it as visited
         2. Else
             a) Pop a cell from the stack
             b) Make it the current cell
      struct mazeNode {  // maze linked-list type
         sqMatrix grid;
         mazeNav move;
         mazePtr next;
      };

*******************************************************************************/
void Maze::genMaze (COORDTYPE v) {
char buf[50];
int i = 0;
bool dHood[4]; // flags to what neightbours to visit
COORDTYPE curr; // current cell
COORDTYPE nlist[4]; // neighbourhood list
COORDTYPE wall[4]; // wall between current and neighbouring cells

curr = v; // 1. Make the initial cell the current cell

//snprintf(buf,37,"grid[%d][%d] being marked as visited\n",v.row,v.col);
//write(1,buf,37);

grid[v.row][v.col] = _MAZEWALL;// and mark it as visited (grid set as NOTFREEFLAG)

while ( !mazestack.empty() ) { // 2. any unvisited cells neighbours
if ( unvisited(curr,dHood,nlist,wall) ) {
while ( !dHood[i=rand()%4] );// a) Choose random neighbour
mazestack.push(nlist[i]); // b) Push cell to the stack
grid [wall[i].row][wall[i].col] = _MAZEWALL; // c) connect the walls
genMaze(nlist[i]); // d) Make the chosen cell current
}
else { // dead-end
curr = mazestack.top();// a) Pop a cell from the stack
mazestack.pop(); // b) Make it the current cell
}
}
}