Recursive Maze Visit

--D. Thiebaut (talk) 20:55, 22 October 2014 (EDT)

---

/**
 * VisitMaze.java
 * @author D. Thiebaut
 */


@SuppressWarnings( "all")
public class VisitMaze {
	static char maze[][] = null;
	static int  dim = 0;
	
	/**
	 * createRow: takes a string representing a row of the maze
	 * and breaks it down into an array of chars.
	 * @param index
	 * @param s
	 * @return
	 */
	private static char[] createRow( String s ) {
		char[] temp = new char[s.length()];
		
		for ( int i=0; i<s.length(); i++ )
			temp[i] = s.charAt(i);
		return temp;
	}	
	
	/**
	 * creates a maze by taking strings and breaking them
	 * down into a 2D array of chars.
	 */
	private static void createMaze() {
		dim = 10;
		maze = new char[dim][];
		
		for ( int i=0; i<dim; i++ ) 
			maze[i] = new char[dim];
		
		maze[0] = createRow(  "###############" );
		maze[1] = createRow(  "      #   #   #" );
		maze[2] = createRow(  "##### # ### # #" );
		maze[3] = createRow(  "#   #   # # # #" );
		maze[4] = createRow(  "# # # ### # # #" );
		maze[5] = createRow(  "# # # # # # # #" );
		maze[6] = createRow(  "#     #   # # E" );
		maze[7] = createRow(  "# ##### # # # #" );
		maze[8] = createRow(  "#       #   # #" );
		maze[9] = createRow(  "###############" );
	}
	
	/**
	 * creates a maze by taking strings and breaking them
	 * down into a 2D array of chars.
	 */
	private static void createMaze1() {
		dim = 10;
		maze = new char[dim][];
		
		for ( int i=0; i<dim; i++ ) 
			maze[i] = new char[dim];
		
		maze[0] = createRow(  "###############" );
		maze[1] = createRow(  "              #" );
		maze[2] = createRow(  "#             #" );
		maze[3] = createRow(  "#             #" );
		maze[4] = createRow(  "#             #" );
		maze[5] = createRow(  "#             #" );
		maze[6] = createRow(  "#             #" );
		maze[7] = createRow(  "#             #" );
		maze[8] = createRow(  "E             #" );
		maze[9] = createRow(  "###############" );
	}

	/**
	 * creates a maze by taking strings and breaking them
	 * down into a 2D array of chars.
	 */
	private static void createMaze2() {
		dim = 10;
		maze = new char[dim][];
		
		for ( int i=0; i<dim; i++ ) 
			maze[i] = new char[dim];
		
		maze[0] = createRow(  "###############" );
		maze[1] = createRow(  "       #      #" );
		maze[2] = createRow(  "#      #      #" );
		maze[3] = createRow(  "E      #      #" );
		maze[4] = createRow(  "#             #" );
		maze[5] = createRow(  "#             #" );
		maze[6] = createRow(  "#             #" );
		maze[7] = createRow(  "#             #" );
		maze[8] = createRow(  "#             #" );
		maze[9] = createRow(  "###############" );
	}

	/**
	 * clears the screen (works only in Terminal/Console)
	 */
	private static void clearScreen() {
        System.out.print("\033[2J\033[;H");
    }
	
	/**
	 * displays the maze, as a 2D array on screen.
	 */
	private static void displayMaze() {
		// bring cursor back to top-left (works only in Terminal/Console)
		System.out.println("\033[;H");
		
		for ( int i=0; i< maze.length; i++ ) {
			for ( int j=0; j < maze[i].length; j++ )
				System.out.print( maze[i][j] );
			System.out.println();
		}
		
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
			//e.printStackTrace();
		}
	}

	
	
	/**
	 * Visit the maze.
	 */
	private static boolean visitMaze() {
		boolean success = recurseVisit( 1, 0 );
		return success;
	}

	/**
	 * recurseVisit.  Lands on cell [i,j] of the maze, and
	 * explore where to go from here, either up, down, right,
	 * or left.
	 * @param i
	 * @param j
	 * @return
	 */
	private static boolean recurseVisit(int i, int j) {
		
		// exit?
		if ( maze[i][j] == 'E' ) 
			return true;
		
		// no, put bread crumb where we landed
		maze[i][j] = '.';
		
		// display the maze in current 
		displayMaze();
		
		// look in all 4 directions around where we are...
		int newi =i, newj =j;
		for ( int dir = 0; dir < 4; dir++ ) {
			switch ( dir ) {
				case 0: newi = i-1; newj=j;   break;
				case 1: newi = i;   newj=j+1; break; 
				case 2: newi = i+1; newj=j;   break;
				case 3: newi = i;   newj=j-1; break;
			}
			
			// we are now looking in a particular direction, 1 
			// square away, at coordinates (newi, newj)  
			
			// invalid coordinates, outside the maze?
			if ( newi<0 || newj<0 
					|| newj >= maze[0].length 
					|| newi >= maze.length ) 
				continue;
			
			// the cell at (newi, newj) is empty and hasn't 
			// been visited yet?
			if ( maze[newi][newj] == ' ' || maze[newi][newj] == 'E'  ) {
				
				// YES!  We can explore going that way!
				boolean success = recurseVisit( newi, newj );
				
				// Did we find the exit going that way?
				if ( !success ) {
					// Nope... ok, let's backtrack and try another direction
					maze[newi][newj] = 'b';
					displayMaze();
				}
				else {
					// YEAH!  Found the exit that way... no
					// need to explore more... we just return
					// Mark where we are as one cell belonging
					// to the path to the Exit.
					maze[i][j] = '*';
					return true;
				}
			}
		}
		// if we're here, it's because we've explored all directions
		// we could from here, and haven't found a successful path 
		// to the exit.  So we can't go nowhere interesting from here.
		// Return false.
		return false;
	}

	/**
	 * main entry point.
	 * @param args
	 */
	public static void main(String[] args) {
		// put the maze on the screen.
		clearScreen();
		createMaze();
		displayMaze();
		
		// visit the maze
		boolean success = visitMaze();
		
		// clean up the maze, remove back=tracks...
		displayMaze();

                if ( success ) 
			System.out.println( "Success, found a path!");
		else
			System.out.println( "No path found.");
	}
}

...