/**
*		@author Kaushik Raj
*		@see	http://www.cis.syr.edu/~kraj/java/
*		@email	kraj@syr.edu
*	
*		(c) copyright-98 Kaushik Raj
*		All Rights Reserved.
*
*       This source code is free for all non-commercial purposes, as long as the name
*       and the url address given above is written with the modified program. The author does not gives
*       the permission to publish the source code in any book or any other publishing media.
*
*
*       The author doesnot takes any responsibility for the software/hardware damages
*       that may occur due to this program.
*/


/**
*	Part of this program has been taken from MazeGen.java
*
*	@see http://www.mazeworks.com/mazegen/mazegen.htm
*/

/**
*	File : MazeDFS.java
*	Last update : 10 July,1998
*/
import java.awt.*;
import java.util.*;

import Maze;
/******** MAZE DFS ********
   creates maze using Depth-First Search algorithm
*/   
public class MazeDFS extends Maze {
   
   // constructor
   MazeDFS(Dimension d,MazeCanvas mc,MazeGame mg) {
      super(d,mc,mg) ;
      // run the algorithm, set start/end
      setWalls() ;
      setStartEnd() ;
	  mc.drawMaze(this); 
   }
   void setWalls() {
      int direction[]=new int[4], visited=0, candidates=0, choice=0 ;
      // random starting point
      int x=randomInt(cols), y=randomInt(rows) ;

      stackPtr = 0 ;
      visited = 1 ;
      while(visited < totalCells) {
         candidates = 0;
         // find all possible directions for next cell
         // first look for a border, then see if all walls intact
         if (((m[x][y]&N_BORDER)==0)&&((m[x][y-1]&ALL_WALLS)==ALL_WALLS))
            direction[candidates++] = NORTH ;
         if (((m[x][y]&E_BORDER)==0)&&((m[x+1][y]&ALL_WALLS)==ALL_WALLS))
            direction[candidates++] = EAST ;
         if (((m[x][y]&S_BORDER)==0)&&((m[x][y+1]&ALL_WALLS)==ALL_WALLS))
            direction[candidates++] = SOUTH ;
         if (((m[x][y]&W_BORDER)==0)&&((m[x-1][y]&ALL_WALLS)==ALL_WALLS))
            direction[candidates++] = WEST ;
      
         if (candidates != 0) {
            // save current cell, choose a direction at random
            choice = direction[randomInt(candidates)] ;
            stack[stackPtr++] = choice ;
 
            switch (choice) {
               // knock down walls and make new cell the current cell
               case NORTH: m[x][y] &= ~N_WALL ;
                           m[x][--y] &= ~S_WALL ;
                           break ;
               case EAST:  m[x][y] &= ~E_WALL ;
                           m[++x][y] &= ~W_WALL ;
                           break ;
               case SOUTH: m[x][y] &= ~S_WALL ;
                           m[x][++y] &= ~N_WALL ;
                           break ;
               case WEST:  m[x][y] &= ~W_WALL ;
                           m[--x][y] &= ~E_WALL ;
                           break ;
            }         
            visited++ ;
         }
         else {
            // nowhere to go, back up to previous cell
            switch (stack[--stackPtr]) {
               // change current cell
               case NORTH: y++ ; break ;
               case EAST:  x-- ; break ;
               case SOUTH: y-- ; break ;
               case WEST:  x++ ; break ;
            }         
         }
      }               
   }
}