Java代写 | P5 Maze Explorer

本次的Java代写题目是Java数据结构的assignment,要求不能使用JDK自带的Stack Class,需要自己实现并构造一个迷宫的数据结构,然后使用右边定则解决迷宫问题,要求72小时内完成,最后完成时间为24小时。

P5 Maze Explorer

  • This assignment is due by 11:59 PM on Monday August, 6th 2018.
  • Pair Programming is allowed but not required for this assignment. your partnership no later than Wednesday, August 1st to work with a partner.  If you have problems accessing this form, try following the advice.

In this assignment, you will implement an algorithm for finding a path through a maze. You will use a stack to store path information as the algorithm proceeds.

OBJECTIVES AND GRADING CRITERIA

The goals of this programming assignment are as follows:

  • Understand the Stack as an important Abstract Data Type (ADT).
  • Implement a specific maze explorer using a Stack from scratch.
25 points 5 zyBooks Tests: automated grading test results are visible upon submission, and allow multiple opportunities to correct the organization and functionality of your code.  Your highest scoring submission prior to the deadline will be recorded.
10 points 2 Final Tests: automated grading tests are run after the assignment’s deadline. They check for similar functionality and organizational correctness as the zyBooks tests.  However you will NOTbe able to resubmit corrections for extra points, and should therefore consider and test the correctness of your own code as thoroughly as possible.
15 points Final Submission Commenting: human graders will review (1) the correctness of the implementation of your work with respect to the write-up, and (2) the readability of your code and clarity of the comments in your final submission conforming to the guide.

SUBMISSION

For this assignment, you need to submit ONLY 4 files on zybooks: Maze.javaMazeRunnerStack.javaPosition.java, and StackADT.java.

GETTING STARTED: <Part 1>

Note that we will not use any pre-defined data structures provided by Java or any other source. You should NOT use the Stack class from the Java standard library for instance. You must implement a custom version of a stack from scratch. Note that this also means you may NOT use an ArrayList as part of your stack implementation! This means that you are NOT allowed to import any class from the java.util library package except Exception, and or, Scanner, if needed.

Step 1. Creating the Generic Interface StackADT

Create a stack Abstract Data Type (ADT) called StackADT which declares the following methods. Note that StackADT is a generic interface using the type variable “E”.

public void push(E item); // adds a new item to the top of the stack

public E pop() throws EmptyStackException; // removes the top item from the stack and returns it

public E peek() throws EmptyStackException; // returns the top item from the stack without removing it

public boolean isEmpty(); // returns true if the stack is empty, otherwise returns false
Step 2. Creating a STACK IMPLEMENTATION Class

Create a class named MazeRunnerStack which implements StackADT<Position>.

Note that, the MazeRunnerStack class

  • should throw an EmptyStackException if you attempt to pop or peek on an empty stack, and
  • should throw an IllegalArgumentException if you attempt to push a null item onto the stack.
  • should not otherwise throw any exceptions.
  • Your stack implementation may use arrays, and may also use package-visibility helper classes that you write for yourself and that may be written only in the files to be submitted. DO NOT USE JAVA’S ARRAYLIST.
  •  This is an unchecked exception. You will also need a package-visibility helper class called Position consisting of the following:
@SuppressWarnings("overrides") 
class Position {
  int col; // column of the position, 0 indexed
  int row; // column of the position, 0 indexed

  /**
   * Constructs a position object with given row and column
   * 
   * @param row
   *            Row for the position
   * @param col
   *            Column for the position
   */
  Position(int row, int col) {
    this.col = col;
    this.row = row;
  }

  /**
   * Checks if the two objects have same row and column values
   * This method overrides the equals method declared in the java.lang.Object class
   * @param other
   *            The other position object to be compared with
   */
  @SuppressWarnings("unchecked")
        @Override
  public boolean equals(Object other) {
    if (this == other) {
      return true;
    }

    if (!(other instanceof Position)) {
      return false;
    }

    Position pOther = (Position) other;

    return this.col == pOther.col && this.row == pOther.row;
  }

  /**
   * Checks if the two objects have same row and column values
   * This is an example of overloading methods
         * This method does not override the java.lang.Object's equals method. It has the same name, but different
         * input argument parameters.
   * @param row
   *            Row for comparison
   * @param col
   *            Column for comparison
   */
  public boolean equals(int row, int col) {
    return this.col == col && this.row == row;
  }
}

USING THE STACK: <Part 2>

Once you are satisfied that your stack implementation is working, it’s time to use it to solve a maze.

Step 3. Creating the Maze class

Now, let’s create a new class called Maze. You may want to provide a main method in this class for testing your maze solver. We will create Maze objects directly. In addition to the (optional) main method, the Maze class should have the following fields and public methods: (You may include additional private fields and methods.)

private Position start; // Start position
private Position finish; // Finish position
private char[][] mazeInfo; //  2-dimensional array of characters that represents the maze layout
private MazeRunnerStack path; // Final path from start to finish through the maze 
private Boolean solved; // indicates whether is maze path is solved or not

public Maze(char[][] mazeInfo){} // Constructor creates a new instance of Maze with a given layout
public void setStart(int row, int col){} // sets the start position field
public void setFinish(int row, int col){} // sets the finish position field
public void displayMaze(){} // Displays the maze. Note that the code for this method is provided in the assignment
public void solveMaze(){} // Solves the maze

Step 4. Building a maze

Note that a maze layout is represented by a 2-dimensional array of characters. Each character is either ‘L’, ‘|’, ‘_’, or ‘.’. (Capital L, a vertical bar, an underscore, or a period.) These characters provide partial information about the walls of a maze. Specifically, they indicate whether a cell has a wall to its left and bottom (L), just to its left (|), just below (_), or neither (.).

Note that each cell only provides information about its bottom and left walls. This is sufficient to describe the entire maze, but we will need to look at the position “above” a given cell to find out whether there is a wall above that cell. Below is one example encoding and the maze it represents:

Example of mazeInfo 2-dimentional array content:    
   first row content:   {'L','.','|'},
   second row content:  {'L','_','_'}

Displayed maze layout:

+---+---+---+
|       |   |
+---+   +   +
|           |
+---+---+---+

For most data about the maze that you wish to store, you may store it in whatever way is most convenient to you. But, as it is stated in step 3, you must include two specific fields: The MazeRunnerStack path will be used to store the final path from start to finish through the maze. Before the maze has been solved, path should be null. The Boolean solved is used to indicate whether the path is solved.

Note that before a solution has been attempted, solved is also null. It receives a value during the solveMaze() method, and indicates whether the maze was solvable.

Once a maze has been created, we can set the start (S) and finish (F) positions for the maze using the setStart() and setFinish() mutator methods. For instance, calling setStart(0,0) and setFinish(0,2) on the maze above results in the following maze:

+---+---+---+
| S     | F |
+---+   +   +
|           |
+---+---+---+

Step 5. Displaying a maze

The displayMaze() method produces an ASCII-graphics version of the maze (similar to the examples seen above). It may be called before or after the start and finish positions have been set, and before or after the maze has been solved. The implementation of this method is provided below for you.

Note that displayMaze() and main() must be the only methods within the Maze class that produce output on the screen.

Before the maze has been solved, a call to displayMaze() shows the unsolved maze. Note that:

  • A grid of + characters with three characters between them (horizontally) and 1 (vertically) defines the corners of the maze cells.
  • Three dashes () indicate a horizontal wall, and one vertical bar character (|) indicates a vertical wall.
  • The characters ‘S’ and ‘F’ should be placed in the appropriate cells to indicate the start and end cells (if they have been determined).

Once the maze has been solved, a call to displayMaze() prints “Solution is:” on one line, then displays the maze. Each cell along the path between S and F will now be filled with an asterisk (*). On the line below the maze, print “Path is: ” followed by the coordinates of each cell from S to F (inclusive).

Solution is:
+---+---+---+
| S   * | F |
+---+   +   +
|     *   * |
+---+---+---+
Path is: [0,0] --> [0,1] --> [1,1] --> [1,2] --> [0,2]

The implementation for displayMaze() method is provided for you in the following:

public void displayMaze() {
  boolean[][] pathGrid = new boolean[mazeInfo.length][mazeInfo[0].length];
  String pathLine = "";
  if (path != null) {
    if (solved) {
      System.out.println("Solution is:");
      Position p;
      while (!path.peek().equals(start)) {
        p = path.pop();
        pathLine = " --> ["+p.row+","+p.col+"]"+pathLine;
        pathGrid[p.row][p.col] = true;
      }
      p = path.pop();
      pathLine = "["+p.row+","+p.col+"]"+pathLine;
    }
    else
      System.out.println("No solution could be found.");
  }
  //Make the top wall
  for (int j=0;j<mazeInfo[0].length;j++) {
    System.out.print("+---");
  }
  System.out.println("+");

  //Make each row
  for (int i=0;i<mazeInfo.length;i++) {
    
    for (int j=0;j<mazeInfo[i].length;j++) {
      if (mazeInfo[i][j] == 'L' || mazeInfo[i][j] == '|')
        System.out.print("| ");
      else
        System.out.print("  ");
      if (start.equals(i,j))
        System.out.print("S ");
      else if (finish.equals(i,j))
        System.out.print("F ");
      else if (pathGrid[i][j])
        System.out.print("* ");
      else
        System.out.print("  ");
    }
    System.out.println("|"); //Right wall always present
    //Bottom walls
    for (int j=0;j<mazeInfo[i].length;j++) {
      if (mazeInfo[i][j] == 'L' || mazeInfo[i][j] == '_')
        System.out.print("+---");
      else
        System.out.print("+   ");
    }
    System.out.println("+");
  }
  //Display the path line if solved
  if(path != null && solved)
    System.out.println("Path is: "+pathLine);
  
}

6. Solving a maze (Right hand rule)

Most mazes can be solved using a technique called the “right hand rule”.

The “right hand rule” is simple: stretch out your right hand to touch the wall on your right. Start walking forward, but always keep your right hand on the wall. If the wall turns, you turn with it.

In the maze example above, you would explore the following sequence of cells [0,0]–>[0,1]–>[1,1]–>[1,0]–>[1,1]–>[1,2]–>[0,2]. Note the bolded cell in the middle, which you backtracked to as you followed your right hand into and then back out of the dead-end cell [1,0].

Note that you need a way to record the cells you actually use, while ignoring the cells that you backtrack away from. You can get this using a stack.

To solve the maze, you can follow the following steps:

  1. Setup: Create a new stack, and push the start position onto the stack. Set an orientation variable to record which way you are “facing”. Initially, you should be facing to the right.
  2. Run the right hand rule: At each room, consider which way you are facing. To follow the right hand rule, turn “right” (relative to where you are facing) if you can. If you can’t, try going “straight” next. If you can’t do that, try “left”. As a last resort, turn around and go back. You cannot walk through walls. Remember to update which way you are facing when you move. If the cell you enter is already part of your path, then you have either just backtracked or made a loop. Either way, pop positions from the stack until the top of the stack is your current position. The loop/backtracked portion is no longer part of your path. If the cell you enter is not yet part of your path, push it onto the stack as it is now part of your path. If the new position is the finish, then save the path you have found as the solution to the maze.