This assignment deals with graphs and path-finding within them You will write a

Question

This assignment deals with graphs and path-finding within them

You will write a program which allows the user to enter multiple levels of a text-based map, consisting of a 'start', an 'exit', 'walls', and 'floors'. The letter S represents the start. E is the exit. O (the letter 'oh') represents a 'floor' (meaning a path you can follow). X is a wall (meaning a block you cannot pass).

Your program will accept this ASCII-based map from Standard In (System.in), and convert it into a graph. It is up to you whether you wish to use an adjacency matrix or adjacency lists (linked or array-based). However, this step is not optional, and those are your only two options.

Ideally, your program will allow the user to find the 'fastest' path through the maze. In this context, 'fastest' means the fewest number of steps possible to get from the start to the exit, without crossing a wall. Note: You may only move North, South, East, West, Up, or Down (diagonal travel is not allowed).

If no valid path exists, your program should say so. You may assume 'sane' input, and that a start and exit are present (though there may not be a path connecting them). The maps do not 'wrap' (i.e. you can't exit the left edge to appear on the right edge), and you may not assume that a floor will have a boundary of walls.

Specifically, the input will be as follows: An integer for the width of the map (W) An integer for the height (length) of the map (H) An integer for the depth (number of layers) of the map (D) D×H lines of W characters (from {X,O,S,E}), terminated with newlines

For D layers, first the (H) lines of the top layer will be entered, then the lines of the second-highest, etc.

In place of any line of W characters, it is legal to include an entirely blank line (as such, any line will have W characters followed by a , or consist solely of a . Your code must be able to ignore such blank lines, but may never rely on their presence; an input might not have any blank lines at all).

You will then write a small report on the algorithms/methodologies you used. Include a quick description of how you translated the ASCII maze into a graph, and how you performed any path-finding/estimation algorithms. It will probably be approximately two pages (unless you're concise, in which case probably a page).

Explanation / Answer

Solution: See the code below

-----------------------------------------

/**
*
*/
package asciimaze;

import java.util.Scanner;

/**
* AsciiMaze class
*
*/
public class AsciiMaze {
   private static char map[][][];
   private static boolean status[][][];
   private static int W, // width of map
           H, // height of map
           D; // depth of map

   /**
   * function to find path in map
   *
   * @param position
   *            in map
   */
   public static boolean findPath(int d, int h, int w) {
       //System.out.println("d:" + d + ",h:" + h + ",w:" + w);
       // check if positions are ok
       if (d < 0 || h < 0 || w < 0)
           return false;
       if (d >= D || h >= H || w >= W)
           return false;
       // check if exit found
       if (map[d][h][w] == 'E') {
           //System.out.println("Exit found");
           return true;
       }
       // check if not is on the path
       if (map[d][h][w] == 'X') {
           //System.out.println("Wall");
           return false;
       }
       if (map[d][h][w] == 'S' || map[d][h][w] == 'O') {
           //System.out.println("On path");
           status[d][h][w] = true;
       }

       // next character
       if (w < (W - 1) && status[d][h][w + 1] == false) {
           if (findPath(d, h, w + 1)) {
               //System.out.println("Next character");
               return true;
           }
       }

       // previous character
       if (w > 0 && status[d][h][w - 1] == false) {
           if (findPath(d, h, w - 1)) {
               //System.out.println("Previous character");
               return true;
           }
       }
       // previous line
       if (h > 0 && status[d][h - 1][w] == false) {
           if (findPath(d, h - 1, w)) {
               //System.out.println("Previous line");
               return true;
           }
       }
       // next line
       if (h < (H - 1) && status[d][h + 1][w] == false) {
           if (findPath(d, h + 1, w)) {
               //System.out.println("Next line");
               return true;
           }
       }
       // previous layer
       if (d > 0 && status[d - 1][h][w] == false) {
           if (findPath(d - 1, h, w)) {
               //System.out.println("Previous layer");
               return true;
           }
       }
       // next layer
       if (d < (D - 1) && status[d + 1][h][w] == false) {
           if (findPath(d + 1, h, w + 1)) {
               //System.out.println("Next layer");
               return true;
           }
       }
       // status[d][h][w] = false;
       // System.out.println("Not on path");
       return false;
   }

   public static void main(String[] args) {
       // scanner for taking input from keyboard
       Scanner in = new Scanner(System.in);
       // read width
       System.out.print("Width:");
       W = in.nextInt();
       in.nextLine();
       // read height
       System.out.print("Height:");
       H = in.nextInt();
       in.nextLine();
       // read depth
       System.out.print("Depth:");
       D = in.nextInt();
       in.nextLine();
       // create a three-dimensional array to be used as
       // adjacency matrix to store ascii map
       map = new char[D][H][W];
       // matrix to store visit status
       status = new boolean[D][H][W];
       // loop to read ascii map from keyboard
       for (int i = 0; i < D; i++) // loop for D layers
       {
           System.out.println("Reading " + i + "th layer:");
           for (int j = 0; j < H; j++) // loop for H lines per layer
           {
               System.out.println("Reading " + j + "th line:");
               // read line of W characters
               String line = in.nextLine();
               line = line.substring(0, W);
               // now put characters in their respective cells in map
               for (int k = 0; k < line.length(); k++) {
                   map[i][j][k] = line.charAt(k);
               }
           }
       }

       // print map
       System.out.println("The entered ascii map is:");
       for (int i = 0; i < D; i++) {
           for (int j = 0; j < H; j++) {
               System.out.println("Layer " + i + ":");
               for (int k = 0; k < W; k++) {
                   System.out.print(map[i][j][k] + " ");
               }
               System.out.println();
           }
       }
       // close scanner
       in.close();
       // find path
       if (findPath(0, 0, 0))
           System.out.println("Path found");
       else
           System.out.println("Path not found");

   }

}

------------------------------------------

Output:

----------------------------------------

Width:3
Height:3
Depth:3
Reading 0th layer:
Reading 0th line:
SOO
Reading 1th line:
OXX
Reading 2th line:
XOO
Reading 1th layer:
Reading 0th line:
OOO
Reading 1th line:
OXO
Reading 2th line:
XOX
Reading 2th layer:
Reading 0th line:
XXO
Reading 1th line:
OXX
Reading 2th line:
OOE
The entered ascii map is:
Layer 0:
S O O
Layer 0:
O X X
Layer 0:
X O O
Layer 1:
O O O
Layer 1:
O X O
Layer 1:
X O X
Layer 2:
X X O
Layer 2:
O X X
Layer 2:
O O E
Path not found

------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.