COM6516 Assignment: shortest path in a maze.
Consider a maze 10×10 defined in a .csv file. An example of such a maze is in map1.csv shown below, with a visualisation of it on the right:
,W,,,,W,W,W,W,W
,,,W,,,,,,
W,W,W,W,W,W,W,,W,
T,,,,,,W,W,W,
W,W,W,,W,,W,,,
,,,,W,,W,,W,
W,,,W,W,,,,,
W,,W,W,W,W,W,W,W,W
,L,W,,,,,W,W,
,,,,W,,,,,
In the .csv file commas separate cells. An empty cell is where a comma immediately follows another comma; two other cases are where a line starts with a comma or ends with a comma. Empty cells can be walked through, W means an impassable wall, T is a teleporter (displayed as a red square) and L is where the teleporter lands a player (depicted green). When a player steps on a teleporter, they are immediately transported to the ‘landing spot’ L. Teleporter is one-way only. You are expected to define a constant public final int SIZE=10anduseSIZEinyourworktomakeitcapableofhandlingmazesof different size.
The starting cell is (0,0) (top left) and the exit is (SIZE-1, SIZE-1) (bottom-right).
Movement is left/right/up/down, there are no diagonal moves. There is exactly one teleporter and one landing cell.
You are expected to load the layout of a maze from a .csv file and plot it using rectangles in a similar way to the presented screenshots. You are also expected to plot a shortest path from the start to the end. Such a path is not necessarily unique and you should consider using a teleporter to shorten the travel time. Whenever you change a maze by clicking on different cells, the shortest path should be recomputed and a new path displayed.
Let the direction of movement be provided by enumeration
enum DIR { DIR_UP, DIR_DOWN, DIR_LEFT, DIR_RIGHT }
A maze is expected to be represented by a map from Position to CELL, with CELL defined as an enumeration:
enum CELL { CELL_W, CELL_E, CELL_T, CELL_L } CELL_W is a solid wall,
CELL_E is an empty room,
CELL_T teleporter,
CELL_L where a teleporter places (lands) a player.
The maze is defined by
Map
For a position p, cell.get(p) returns an instance of CELL reflecting what can be found at that position.
COM6516 Assignment, Autumn 2016, The University of Sheffield.
Create a Position class that stores two integers reflecting the x and y coordinates of a player position in a maze. It should take a constructor accepting a pair of integers as coordinates as well as an instance of Position (this is used where you need to make a copy). You need to implement both equals and hashCode methods of Position.
[2]
T h e Position class should have method move(DIR dir) implemented which modifies the coordinates stored in it in relation to the request to move in a specific direction.
[2]
The maze has to be loaded from a .csv file. Two sample files are provided; keep in mind that there could be many other mazes used. When loading, it is suggested that you load the text file line-by-line and process cells using the split method of the String which takes a separator expression and splits a string into an array of strings between separators. Method valueOf of an enumeration can be helpful to turn strings into elements of CELL. Feel free to load in any other way you find useful but you should not use external libraries other than the Sheffield package.
[8]
You have to visualise the loaded maze in a similar way to the figure above. Empty cell is blank, wall is solid black, teleporter red and landing cell green. Drawing a filled rectangle can be done by setting a background colour and using clearRect. Solutions that draw cells of a fixed size rather than scale depending on the size of the main frame will receive half the marks for this and the next part.
Given any path, such as the one generated by the expression below, visualise it:
Arrays.asList(new Position[]{new Position(0,0),
new Position(0,1),new Position(1,1),new Position(2,1)})
A drawing for the path above is shown below:
[8]
Each step in the path should displayed in blue close to the middle of a respective cell. If you implement computation of the shortest path (the 20% part below) and visualise it, you will get the credit for this part.
[8]
Make it possible to modify the maze by clicking on different cells. This can be done by implementing a MouseListener interface. ThemouseClicked(MouseEvent e) method can use e.getPoint() in order to find coordinates of a mouse inside the component listening to mouse events. You can then find the relevant cell. A shift-click (e.isShiftDown()) should move the teleporter (CELL_T), control-click (e.isControlDown()) should move teleporter land cell (CELL_L) and otherwise each cell should be flipped between empty and wall. Your editor should not permit a teleporter or a land cell to completely disappear during edits (such by placing one over another one).
[8]
Draw a UML class diagram depicting relations between around 6 main classes of your solution. There should not be too many classes in the diagram and each of them should only include the most important methods, not all of them. Hence if you use a tool (such as Eclipse) to automatically build such a diagram, you’ll have to modify it to match what is expected. Only diagrams submitted as Adobe ® .pdf files will be accepted.
COM6516 Assignment, Autumn 2016, The University of Sheffield.
Compute the shortest path in a form of a list of Position from the start cell (0,0) to the end (SIZE- 1,SIZE-1) and visualise it. If no such path is possible, no path should be displayed. A possible path for the map map1.csv is shown above, with each step of the path numbered. Note that the shortest path uses a teleporter to shorten the walk to the exit. Example of a maze where no path exists is provided in map2_deadend.csv .
[20]
How to find a shortest path
This is called a breadth-first search. Consider a map Map
from positions to the length of a shortest path from an initial state (0,0). When you begin, this only contains a single entry for the initial state with a length of 0. You then look at all valid cells reachable from the initial cell, their distance from the initial cell is 1. From those cells, you consider subsequent valid cells, with a distance increased by 1. It is possible that at some point you will find that there is a shorter path to a particular cell than the one you have seen before – this is the case where there are multiple paths leading to the same cell. In this case, you replace the previous distance by the new (smaller) distance.
The algorithm hence maintains
Queue
that holds positions that need to be considered and then you have a loop that removes a position from the queue to consider it. Call this position pos. Consideration involves looking at all possible directions around that position. You can use a copy constructor to make a copy of pos and then use the move method to compute the new position newPos. Valid cells are those with newPos containing coordinates 0..SIZE-1 and then you explore what distance map returns for newPos,
1. if this is null, you have not explored that cell before, or
2. if it is a larger value than the distance from the initial state for the current path (1+what
distance map has for pos), you have found a shorter alternative path.
In both of these cases you have to consider all directions from newPos cells and therefore offer newPos to the posQueue. The algorithm terminates when posQueue becomes empty.
Every time you modify distance, you could record the path to the initial state that got you to that state. This can be done by maintaining a current path from the initial state that is kept on a separate queue pathQueue. When you add something to posQueue, you add the modified path to pathQueue and when you pop from posQueue, you also pop from pathQueue.
An alternative is to have a map Map
COM6516 Assignment, Autumn 2016, The University of Sheffield.
[4]
Submission
You should submit .java files and the .pdf of the UML class diagram as a single .zip file to Mole. Latin alphabet should be used for both the name of the .zip file and for any files inside. If you submit multiple times, only the last attempt will be marked.
When you submit your work, you are required to acknowledge in the comment field on MOLE that the material you submit (including your code) is your own work.
The deadline is 5pm Friday of week 12 (Fri Dec 16 2016). Standard DCS rules for late submission apply. Your solution should only make use of the core Java Class Libraries other than, optionally, the Sheffield package. It should not make use of any external Java libraries (e.g. packages to draw graphs).
A solution that uses buttons rather than implements paintComponent to draw cells of the maze and paths through the maze will be accepted and awarded full marks if it does what is expected and is well designed. If you use buttons, you’ll have to make them of the right colour (to reflect cells of different type) and display the right numbers (for paths through maze). An example of a badly-designed solution is 100 buttons and an equal number of actionPerformed methods.
Any parts of the assignment that use explicit maze size such as 9 or 10 rather than constant SIZE will have 30% deducted from the score for those parts. Your solution should work for any maze with SIZE at least 2.
Unfair means
This is an individual assignment, and so you are expected to work on your own . You may wish to discuss your design with other students, but you must not work together to develop your solution. All the reports and code that is submitted may be examined using specialised software that will identify if there is evidence of using code written by another student, or downloaded from online resources.
COM6516 Assignment, Autumn 2016, The University of Sheffield.