Create a Java program to explore a 2D cave using recursion and pathfinding algorithms. Learn how to model a cave, find a path to the mirror pool (M), read layouts from a text file, and return the direction path (N, S, E, W). This step-by-step solution covers constructors, file parsing, DFS search, and path retrieval.
This assignment lets you build a set of classes to support a program to find paths through a cave. By the end of Unit 4, you will have a program that can read a 2-dimensional cave layout from a file, search the layout to find a path to a mirror pool, then print the path to take. This unit, you will build the infrastructure for this project, including storing data in a two dimensional structure, searching the data structure for a simple path from start to finish and reading data from a text file.
Preparation
See the announcements for the link
to the GitHub repository for this assignment.
Directions
Write a class CaveExplorer, that has
the following methods:
- Constructor with no parameters. It should create
the two-dimensional structure shown below, where the characters in
the layout are 'R' for rock, '.' for a clear path, 'M' for mirror
pool, and 'S' for self. This constructor hardcodes the cave without
reading from a file.
- toString - no parameters, returns a string
(including new lines) showing the current state of the cave
exploration. For the initial configuration, this string would be
"RRRRRR\nR..SRR\nR.RRRR\nR.MRRR\nRRRRRR\n" - solve - no parameters, returns a boolean true if
there is a path to the mirror pool, and false if there is not. This
method is where you will spend some time figuring out the logic.
Even though there is only one path, you still have to search in four
different directions and make sure you don't get caught in an
infinite loop. How you do this is up to you.
- getPath - no parameters, returns a String showing the
path taken to get to the mirror pool. In the example, this path
would be the string of directions "wwsse" for West, West,
South, South, East. The method should return the empty string if
there is no path.
- Constructor with one String parameter - the name
of a text file with the cave layout. The file has a line with two
integers, the number of rows and columns of the cave layout,
followed by the layout itself. For exampleYou will have to
modify the text file with the cave data using your favorite editor.
Your cave layout should contain a path requiring at least 4 moves in
two different directions. There must be exactly one path through the
cave, that is, from any location, there is only at most one location
to move to next that hasn't already been visited. If you need help
reading from a file, there are many resources on the web regarding
using the Scanner class to read text data. A short one is the
section on Scanners at https://math.hws.edu/javanotes/c11/s1.html (Links
to an external site.)
- main - test your class by writing a main method
that creates at least 2 CaveExplorer objects, solves each one, then
prints the starting layout, the final layout, and the path taken, if
it exists, for each one. Be sure to follow this order of operations.
Answer
import
java.io.*;
import
java.util.*;
public
class CaveExplorer {
// data
fields
char
[][] structure ;
static
ArrayList<Character> ThePath ;
static
ArrayList<String> readFromFile ;
//Constructor
with no parameters
public
CaveExplorer() {
structure = new char[][] { { 'R', 'R', 'R', 'R', 'R',
'R' },
{
'R', '.', '.', 'S', 'R' , 'R'},
{
'R', '.', 'R', 'R', 'R' , 'R'},
{
'R', '.', 'M', 'R', 'R' , 'R'},
{
'R', 'R', 'R', 'R', 'R', 'R' }, };
ThePath
= new ArrayList();
readFromFile
= new ArrayList();
}
//toString
- no parameters, returns a string
public
String toString(){
String
result ="";
for(int
i = 0 ; i < structure.length ; i++){
for(int j = 0 ; j <
structure[0].length ; j++){
result +=
structure[i][j];
}
result +="\n";
}
return
result;
}
//solve
- no parameters, returns a boolean true if there is a path to the mirror pool,
and false if there is not
public
boolean solve(){
boolean
travel[][] = new boolean[structure.length][structure[0].length];
boolean
checked = false;
for
(int i = 0; i < structure.length; i++) {
for
(int j = 0; j < structure[0].length; j++) {
if (structure[i][j] == 'S'&&
!travel[i][j])
if (checkpath(structure, i, j, travel)) {
checked = true;
break;
}
}}
if
(checked)
return true;
else
return false;
}
//
checkpath to pass through 2d array character
to find the path
public
boolean checkpath(char structure[][],int i, int j,boolean travel[][]){
if ((i
>= 0 && i < structure.length&& j >= 0&& j <
structure[0].length)&& structure[i][j] != 'R'&& !travel[i][j])
{
travel[i][j] = true;
if
(structure[i][j] == 'M')
return true;
if
(checkpath(structure, i - 1,j, travel)) {
ThePath.add('N');
return true;
}
if
(checkpath(structure, i, j - 1, travel)) {
ThePath.add('W');
return true;
}
if
(checkpath(structure, i + 1, j, travel)) {
ThePath.add('S');
return true;
}
if
(checkpath(structure, i, j + 1,travel)) {
ThePath.add('E');
return true;
}
}
return
false;
}
//getPath
- no parameters, returns a String showing the path taken to get to the mirror
pool
public
String getPath() {
if(ThePath.size()
== 0)
solve();
String
result ="";
Collections.reverse(ThePath);
for(Character
getpath :ThePath)
result
+= getpath;
return
result;
}
//
Constructor with one String parameter
public
CaveExplorer (String fname) throws Exception {
Scanner
input =null;
ThePath
= new ArrayList();
readFromFile
= new ArrayList();
ThePath.clear();
int row
, col;
try{
input = new Scanner(new File(fname));
} catch
(FileNotFoundException e ) {
System.out.println("File not
found " );
}
catch (Exception e ) {
System.out.println(e );
}
row =
input.nextInt();
col =
input.nextInt();
input.nextLine();
structure = new char[row][col];
String
value ="";
while
(input.hasNextLine()) {
value = input.nextLine() ;
readFromFile.add(value);
}
int
index = 0 ;
for(String
data:readFromFile) {
if(data.length()==col) {
structure[index++] =
data.toCharArray();
}
else {
throw new Exception("Error
");
}
}
}
public
static void main(String[] args) {
//
first object
CaveExplorer cave = new CaveExplorer();
System.out.println(cave.toString());
System.out.println("There
is a path : "+cave.solve());
System.out.println("getPath:
"+cave.getPath());
//
second object
try {
CaveExplorer
cave2 = new CaveExplorer("testcave.txt");
System.out.println("\n\n"+cave2.toString());
System.out.println("There
is a path : "+cave2.solve());
System.out.println("getPath:
"+cave2.getPath());
}catch
(Exception e) {
System.out.println(e );
}
}
}
testcave.txt
5 6
RRRRRR
R..SRR
R.RRRR
R.MRRR
RRRRRR