Question
Overall, you will design a recursive method solution in an executable class source code file named LostPuppy.java that allows a puppy to find his way
Overall, you will design a recursive method solution in an executable class source code file named LostPuppy.java that allows a puppy to find his way out of a maze at an exit point once he has entered it from an entry point.
Entry and exit points never occur at a corner of the maze, i.e. given the maze is stored in a 2D array named maze, entry and exit points will never occur at locations:
maze[0][0]
maze[0][maze[0].length -1]
maze[maze.length 1][0]
maze[maze.length 1][ maze[0].length -1]
Facts:
The walls of the maze are indicated with Xs
The paths are indicated with spaces
The entry or starting point is indicated with an ' S '
The exit point is indicated with an ' E '
The input file is named MazeData#.txt where the # indicates a single numeric digit
You can only read the input file once
The number of columns is unknown, but can be determined from the string length of the first line
The number of rows is unknown, but can be determined by counting the number of lines read
Once the input data is read and stored, you can then instantiate the 2D array of char (as a hint, you might want to read lines into a string onto which you continually concatenate subsequent lines while counting each line read)
Place each character from the stored input data into the 2D array
Place an asterisk * in each move location
Place a minus sign - in cells where backtracking occurs
The following processes should not appear in main, but decomposed into separate methods (only suggesting method names and possible processing, but not requiring an exact naming or process):
getMaze:
Using the opened input Scanner, returns a 2D array containing the characters that make up the maze. If you apply the suggested method of continually reading and concatenating lines of input, while sequentially traversing a 2D array in row major order, you can use a separate index variable that is set to 0 before the loops begin and only increment after each character is copied from the String into the 2D array.
getStartLocationAndDirection:
Once the array is filled, you need to locate the start position and the current direction the puppy is traveling when first entering the building. Depending on how you are solving this assignment, you will probably want to replace the S which indicates the start position, with the first asterisk *. The direction would be related to which side of the maze on which the S is found, i.e.
- If on row 0, direction would be South (note, I avoid using down, as associated words such as left and right are only clearly defined based on the current direction the puppy is traveling).
- If on row 7 (Yes. This literal constant or magic number would be fine here as chess boards always have 8 rows and 8 columns, i.e. never a possibility or need to change it in the future. 7 is used, as the indexing of arrays start at 0), then the direction is North.
- If on col 0 (left side), the entry direction would be East.
- If on col 7 (right side), the entry direction would be West.
You may also want to locate and return the Ending position (exit point containing the E) and replace the E with a space.
Up to you about everything the recursive method will need to know. However, since much of this data is primitive and methods can only return a single entity, you may need to consider creative means to pass so many primitives back to main so main can send them on to the actual recursive maze path solution method. One possibility is to store the row/column values in 2 element arrays. One for the start and one for the exit positions. Again, these are all matter you need to resolve and how you do it is up to you as long as you follow the basics:
Do your own work
See either me or the TA for assistance
Decompose each operation/process into separate methods
Never use class wide variables in an executable class (class that contains main), constants are fine
canMove:
Checks the row and column indices for a move about to be made for validity, i.e. indices are within acceptable bounds of the array and the location in the array contains a space or possibly the letter E depending how you design your solution. Returns a Boolean. This will be used by the recursive maze solution method just prior to a desired move.
doMaze (or some useful name):
Recursive solution to navigating the paths found within a given maze. Overall, needs to be passed the various data (including the maze) needed and returns false for each recursive call unless the exit location is reached which should set the variable used for the return statement to true.
Several approaches can be applied. However, fundamentally you need a:
Base Case: The currently passed Row and Column values indicate the mazes exit. Sets the return variable to true.
General (Recursive) Case: Based on the currently received row and column position, a move in 1 of 3 directions needs to be made (obviously a fourth move option would simply return the puppy to the location from which he had just come which you want to avoid). However, before making the next move, that move needs to be validated through a call to canMove. If canMove returns true, then the location to where the move will be made needs to be assigned an asterisk *. The move then is made by recursively calling doMaze by adding or subtracting 1 from one of the current indices based on the direction the puppy needs to proceed. If doMaze returns false, you need to assign a minus sign - to the attempted location and you proceed to another possible move. Each recursive call should assign the returned value (true or false) to the local return variable which, in turn, is returned.
displayMaze:
Simply outputs the contents of the maze array in row major order main: Declares the various variables needed that are passed between the various methods and opens the input file. Calls the methods listed above as:
getMaze
getStartLocationAndDirection
doMaze: If returns false, display No Path Found!, otherwise call displayMaze
Keep in mind, various data needs to be passed between the methods and the array is needed by nearly all the methods.
Though the maze solution may lend itself to less concerns of passing information to and from methods as an instantiable class with a constructor and class fields, this assignment is intended to help reinforce a CS majors ability to solve problems in a non-Object Oriented Programming design as with procedural languages which you will likely encounter during your career.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Moving Objects Databases
Authors: Ralf Hartmut Güting, Markus Schneider
1st Edition
0120887991, 978-0120887996
