Java Program

CSC220 Lab 11 Path Finding (due Nov. 28th)

This week’s assignment has double the points The goal of this week’s assignment is:

1. Practice using graphs

2. Practice using queues

3. Practice using BFS path finding

4. Practice object oriented programming

5. and more…

Things you must do:

1. There are many details in this assignment. Make sure you read the whole thing carefully

before writing any code and closely follow this instruction.

2. You must complete your assignment individually.

3. Always remember Java is case sensitive.

4. Your file names, class names, package name, and method signatures must match exactly

as they are specified here.

Things you must not do:

1. You must not change the file names, class names, package names.

2. You must not change the signature of any method we have specified (name,

parameters, …).

3. You must not create any different class (other than the ones instructed).

Important Note: This project requires more time to finish and counts twice as much as any

other assignment you have done so far. So start early and try to finish way ahead of the

deadline to give yourself enough time for debugging and testing.

Part 0

• You are going to create a new project for this lab. You learned how to create a project in

Eclipse before. Create a new Java project and call it Lab11 (with no space and no other

name – notice the capital ‘L’)

• Create a package inside your project and call it lab11 (no space and no other name – all

lowercase).

• Create another class (or Java file) in this package and call it: PathFinder.java (nothing

else). You will be working on developing methods for this class.

• Create another class (or Java file) in this package and call it: Node.java (nothing else).

This class will represent a node of the graph.

• You are fully in charge of implementing these two classes based on the description

below.

Part 1 – The problem description

DO NOT MOVE TO NEXT STEPS BEFORE READING THIS PART CAREFULLY

For this lab, you are asked to create a tool to help Pacman solve mazes. You must create a

program that can find the shortest path from one location to another in any enclosed field of

obstacles. You are given the field as input, represented as a simple text file. The start-point and

end point are indicated in this text file, as well as the layout of the field (the location of the

walls and obstacles). You must produce a similar text file, but with the shortest path from the

start-point to the end-point added to the field. If there is no path at all, the path indicators will

simply not exist in the output. To solve this problem, you must represent the maze as a graph,

and perform a breadth-first search from Pacman's starting location. You will be given some

hints and instruction during Thursday’s lecture to help you solve this problem. The graph in this

case is a simple 2D array of nodes.

PathFinder class:

The PathFinder class is required to have the following function with the following signature and

nothing else:

public static void solveMaze(String inputFile, String outputFile)

Copy and paste the signature. If you change the signature you will be penalized up to 20%.

This method will read a maze from a file with the given input name, and output the solved

maze to a file with the given output name. You must use the filenames exactly as is (do not

change the directory or path). We will provide the full path to files we want to read/write in our

tests. See required specifications below. This method must use a graph and graph pathfinding

to solve the problem. No other solutions are allowed! Your program may contain other

methods necessary for your solution. You will need a queue for breadth-first search, you don’t

have to implement a queue, simply use the one Java provides. You also need various methods

from java.io for reading/writing files as well. Which ones in specific? That is left for you to figure

out. There are some tips below.

Input: The input files are in the following form:

The first line contains two numbers, separated by a space. The first number is the height of the

field, and the second is the width. The rest of the lines contain the layout of the field. The

characters have the following meaning:

X - A single wall segment. Pacman cannot travel on to or through walls.

S - The starting point of the path that we are trying to find (where Pacman starts). This is an

open space (no wall).

G - The ending point of the path we are trying to find (where Pacman wants to be). This is an

open space (no wall).

(space) - An open space on the field. Pacman is free to travel in any open space, assuming he

can get there.

Pacman is free to move from his current location to any adjacent open space. This includes the

space directly above, below, left and right of where he is. It does not include diagonally

adjacent spaces. If any of the adjacent spaces are a wall, Pacman cannot travel in that direction.

The path that your maze solver finds MUST be a connected path (it can't skip spaces and have

Pacman "jumping" over walls or empty spaces).

You can assume that all input mazes will be rectangular. All of the border positions around the

perimeter of the field will be walls (the field is fully enclosed).

An example of reading numbers (height and width) from a file, assuming you're using

a BufferedReader named input to read the file:

String[] dimensions = input.readLine().split(" ");

height = Integer.parseInt(dimensions[0]);

width = Integer.parseInt(dimensions[1]);

Output: The output of your program is a similar file. Output the height and width at the top, just like the

input. The output should also have the same layout of the walls and the same start and end

points. It will, however, replace some of the open spaces (space characters) with dot characters

('.').

The spaces that you replace with dots are the spaces on the shortest path from the start point

to the goal point. For example, given the above input, the following output may be produced:

Some of the empty spaces are now replaced with dots, connecting a path from 'S' to 'G'. There

is a single newline character after the last 'X' in the output.

There are multiple shortest path solutions to the above example. Any connected path from 'S'

to 'G' with length of 4 is a correct solution. For example, another acceptable solution to the

above maze is:

If there is no path from 'S' to 'G', simply do not place any dots in the output file; print the

original maze. We have provided a zip file containing various mazes and their solutions to try

out your code. You have learned how to add a text file to your project in assignment 4. If you

are in doubt consult the instruction for assignment4 in Blackboard (i.e., assignment04-

generics.pdf). If you add the files differently into your project, the TA will have difficulty running

your code and you will lose points.

Note that there might be cases where your code finds a different way. The important thing here

is that the length of the path your code finds is exactly the same as the length of the solution

path. If you have a longer path, something is wrong in your code. You need to go back and

debug it.

An example of creating a file and writing to it in Java is below (where outputFile is a String). It

will create the specified file if it does not exist. Use the exact String outputFile passed in to

your solveMaze method (do not modify the path of the file).

try(PrintWriter output = new PrintWriter(new FileWriter(outputFile))) { output.println(height + " " + width); //write more data here }

Rules:

• The path cannot go through or on top of walls.

• The path must be connected (no skips or jumps).

• Diagonally-adjacent spaces are not connected.

o Only up, left, down, right

• If no path exists, the output file will have no dots.

• If multiple shortest paths exist, any of them are valid.

• Must produce output in exact format specified (for grading purposes). You will lose up

to 10% if the format of your output file is wrong eventhough your solution is correct.

• Your program must run in 10 seconds or less on all mazes we test. This includes file

input, graph construction, pathfinding, and file output. The biggest test maze is 100x100

(see randomMaze in the mazes provided).

• Other than the required PathFinder class with method solveMaze (see above) and above

rules, the design of your program is completely up to you.

Part 2 – Start your implementation

For this lab you are encouraged to take some time to think about how you are going to

accomplish this task (given the rules, etc). What methods and fields each class should have?

DO NOT open Eclipse and start coding aimlessly! IT WON’T WORK!

Try to break down this project into smaller and testable components. Implement each

component, test it, and then go to the next component. Before continue reading think about

how you can do this.

After you are done with that, discuss it with the lab instructor and then start implementing your

design. Remember that your design might not work the first time and you might need to

change it.

For instance, the first task is to be able to read in the maze file and store it into a 2D array. This

is absolutely required and is a smaller component of the project that can be tested

independently. Start working on this component in this lab. How would you test it? You can

simply print your maze to make sure it looks correct.

The next task you might want to accomplish is to write a function that accepts a maze and write

it into a file. This is a gain a required and a smaller component of this project that can be tested.

This can also be used to check the structure of your maze and make sure you are not going to

lose 10% for having an incorrect output file. After you are successfully reading in the maze file

try to write it out.

The rest if left for you to figure out. Good luck! J

Make sure to grab your code before your leave the lab, you will develop more functionality for the classes for your assignment. You are required to submit the code you wrote during the

lab as part of your assignment.

For all your assignments, please start early and seek help early (either from the instructor or the TAs).

__MACOSX/._Lab-Assignment11-Graph.pdf