MazeSolver.java

The Tombs of Mars

(Java...and the pictures are from Netbeans)

The rulers of Mars wish to construct tombs for their eternal rest. The objective, for you, is to ensure that a path exists from the tomb's entrance, through the maze of walls, to the placement of the sarcophagus. This lab is based on Dijkstra's Shortest Path Algorithm. (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

In this lab you will extends the abstract class named "Shortest" instead of implementing an interface. You should configure Netbeans the same way you did before, except you treat your extension of Shortest as the implementation of the interface Shortest is testing, i.e. you set the project properties > Run > Arguments to the class name you create. As usual, you need to also set "-ea" in VM Options.

[And for the argument, it is supposed to actullay be "MazeSolver.ShortestImpl" (If MazeSolver is the package name)]

Steps

1. Create the constructor. The constructor for your class must take two integers and call the corresponding constructor on the superclass.

2. Implement the nearest method(). Read the comments on the method in Shortest for instructions.

3. Implement the markPaths() method. Read the comments on the method in Shortest for instructions.

4. Implement the findPath() method. Read the comments on the method in Shortest for instructions.

The algoithm of finding the shortest path is implemented by the combination of markPaths() and findPath().

Thought Question: If you use java.util.LinkedList for your queue, What happens if you use it like a stack instead (i.e. you replace add() and remove() with push() and pop())?

Shortest.java

import java.util.*; import java.io.*; /** * Find the shortest path through the Martian tomb. */ public abstract class Shortest { public final static int WALL = Integer.MAX_VALUE; public final static int EMPTY = Integer.MAX_VALUE - 1; LinkedList q = new LinkedList(); public final static Random RAND = new Random(); static { RAND.setSeed(0); } int[][] grid; final int NX, NY; final Coord START, END; public Shortest(int n,int m) { NX = n; NY = m; grid = new int[n][m]; clear(); START = new Coord(0,0); END = new Coord(NX-1,NY-1); } void clear() { for(int i=0;i wallsBefore = getWalls(); boolean b = markPaths(); List wallsAfter = getWalls(); assert wallsBefore.equals(wallsAfter) : "Calling markPaths() should not add or remove walls."; // Does a shortest path still exist? // If so, we're done. if(b) { clarify(); print(); return true; } // if the shortest path doesn't exist, // a wall shouldn't go here. Take it // away and try again. grid[x][y] = EMPTY; } return false; } /** * Convert a numerical value to * a letter for display purposes. */ public char toChar(int val) { if(val == Integer.MAX_VALUE) return '#'; if(val == Integer.MAX_VALUE-1) return '.'; if(val  * 0 1 2 3 4 * +----------+ * 0 | . # . . .| * 1 | . # # . .| * 2 | . . . . .| * +----------+ * 

*/ public abstract List nearest(int x,int y); /** * Check the nearest method to make sure * it is functioning properly. */ void checkNearest() { Shortest s = makeShortest(3,5); s.grid[0][1] = WALL; s.grid[1][1] = WALL; s.grid[1][2] = WALL; s.print(); checkNearest(s.nearest(1,3),"[(0,3), (1,4), (2,3)]"); checkNearest(s.nearest(2,2),"[(2,1), (2,3)]"); checkNearest(s.nearest(0,0),"[(1,0)]"); checkNearest(s.nearest(2,4),"[(1,4), (2,3)]"); } void checkNearest(List c,String val) { Collections.sort(c); System.out.println(c); assert c.toString().equals(val); } /** * Implement the following procedure: * * 0: Create a queue of Coord objects. * * 1: Put a 1 in the START square (i.e. grid[START.x][START.y]=1). * * 2: Add the START square in the queue. * * 3. If the queue is empty, return false. * * 4: Remove a value c from the queue. * * 5: For each empty square p near c.... * Note: use the nearest() method you defined to help * you with this step. * * 5(a): Update the value of the grid at p (i.e. grid[p.x][p.y]) * to be 1 more than the value at c. * * 5(b): Add p to the queue. * * 5(c): If p is equal to END, then exit and return true. * * 6: return to (3) */ public abstract boolean markPaths(); Coord prev(int x,int y) { int val = grid[x][y]-1; for(Coord p : nearest(x,y)) if(grid[p.x][p.y] == val) return p; return null; } /** * Return a List of coords describing * the shortest path through the grid. * * 0: Create a list of Coord objects. * * 1. Add END to the list. * * 2. Create a variable of type Coord named c and * set it to END. * * 3. If there exists a Coord p that * is near c, and the value of the grid * at p is one less than at c, then * add p to the list and set c = p. * Note: use the nearest() method you defined to help * you with this step. * * 4. If c is not the same as START, * return to 3. * * 5. Return the list. */ public abstract List findPath(); public void checkPath(List path) { for(int i=1;i path = findPath(); checkPath(path); clear(); for(int n=0;n getWalls() { List walls = new ArrayList(); for(int i=0;i m = new HashMap();"); pw.println(" public Check() {"); } final int nx = 15, ny = 30; Shortest s = makeShortest(nx,ny); s.checkNearest(); Check c = new Check(); for(int i=0;i

Coord.java

/** * A class describing a coordinate x,y * on a grid. */ class Coord implements Comparable { final int x,y; public Coord(int x,int y) { this.x = x; this.y = y; } public String toString() { return String.format("(%d,%d)",x,y); } /** * Allow it to be compared. */ public boolean equals(Object o) { Coord c = (Coord)o; return x == c.x && y == c.y; } /** * Allow it to be sorted. */ public int compareTo(Object other) { Coord that = (Coord)other; int diff = this.x - that.x; if(diff == 0) diff = this.y - that.y; return diff; } } 

Check.java

import java.util.*; public class Check { Map m = new HashMap(); public Check() { m.put(0,44); m.put(1,44); m.put(2,44); m.put(3,44); m.put(4,44); m.put(5,44); m.put(6,44); m.put(7,44); m.put(8,44); m.put(9,44); m.put(10,44); m.put(11,44); m.put(12,44); m.put(13,44); m.put(14,44); m.put(15,44); m.put(16,44); m.put(17,44); m.put(18,44); m.put(19,44); m.put(20,44); m.put(21,44); m.put(22,44); m.put(23,44); m.put(24,44); m.put(25,44); m.put(26,44); m.put(27,44); m.put(28,44); m.put(29,44); m.put(30,44); m.put(31,44); m.put(32,44); m.put(33,44); m.put(34,44); m.put(35,44); m.put(36,44); m.put(37,44); m.put(38,44); m.put(39,44); m.put(40,44); m.put(41,44); m.put(42,44); m.put(43,44); m.put(44,44); m.put(45,44); m.put(46,44); m.put(47,44); m.put(48,44); m.put(49,44); m.put(50,44); m.put(51,44); m.put(52,44); m.put(53,44); m.put(54,44); m.put(55,44); m.put(56,44); m.put(57,44); m.put(58,44); m.put(59,44); m.put(60,44); m.put(61,44); m.put(62,44); m.put(63,44); m.put(64,44); m.put(65,44); m.put(66,44); m.put(67,44); m.put(68,44); m.put(69,44); m.put(70,44); m.put(71,44); m.put(72,44); m.put(73,44); m.put(74,46); m.put(75,46); m.put(76,46); m.put(77,46); m.put(78,46); m.put(79,46); m.put(80,46); m.put(81,46); m.put(82,46); m.put(83,46); m.put(84,46); m.put(85,46); m.put(86,46); m.put(87,46); m.put(88,46); m.put(89,46); m.put(90,46); m.put(91,46); m.put(92,46); m.put(93,46); m.put(94,46); m.put(95,46); m.put(96,46); m.put(97,46); m.put(98,46); m.put(99,46); m.put(100,46); m.put(101,46); m.put(102,46); m.put(103,46); m.put(104,46); m.put(105,46); m.put(106,46); m.put(107,46); m.put(108,46); m.put(109,46); m.put(110,46); m.put(111,46); m.put(112,46); m.put(113,46); m.put(114,46); m.put(115,46); m.put(116,46); m.put(117,46); m.put(118,46); m.put(119,46); m.put(120,46); m.put(121,46); m.put(122,52); m.put(123,52); m.put(124,52); m.put(125,52); m.put(126,52); m.put(127,52); m.put(128,52); m.put(129,52); m.put(130,52); m.put(131,52); m.put(132,52); m.put(133,52); m.put(134,52); m.put(135,52); m.put(136,52); m.put(137,52); m.put(138,52); m.put(139,56); m.put(140,56); m.put(141,56); m.put(142,56); m.put(143,56); m.put(144,56); m.put(145,56); m.put(146,56); m.put(147,56); m.put(148,56); m.put(149,56); } }

Categories o Sources oLibraries Configuration:-.default config New. Delete Build Compiling o Packaging o Deployment o Documenting Runtime Platform: Project Platform Main Class: Arguments Working Directory: VM Options Manage Platforms Shortest Browse Shortestimpl Run Application o Web Start Browse oLicense Headers o Formatting o Hints Customize (e.g. -Xms10m) Run with Java Web Start To run and debug the application with Java Web Start, first enable Java Web Start) OK Cance Categories o Sources oLibraries Configuration:-.default config New. Delete Build Compiling o Packaging o Deployment o Documenting Runtime Platform: Project Platform Main Class: Arguments Working Directory: VM Options Manage Platforms Shortest Browse Shortestimpl Run Application o Web Start Browse oLicense Headers o Formatting o Hints Customize (e.g. -Xms10m) Run with Java Web Start To run and debug the application with Java Web Start, first enable Java Web Start) OK Cance