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.");
}
}