Demo entry 6730947

maze

   

Submitted by anonymous on Apr 09, 2018 at 17:28
Language: Java. Code size: 6.1 kB.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Maze {
  // CONSTANTS
  public static final int EMPTY = 0;
  public static final int WALL = 1;
  public static final int START = 2;
  public static final int EXIT = 3;
  public static final int BREADCRUMB = 4;
  public static final int EXIT_PATH = 5;
  public static final int DOWN = 6;
  public static final int RIGHT = 7;
  public static final int UP = 8;
  public static final int LEFT = 9;
  
  
  // FIELDS
  private int[][] rooms;
  private int[][] directions;
  
  // CONSTRUCTORS
  /** Creates new maze based on given array. */
  public Maze(int[][] rooms, int[][] directions) {
    this.rooms = rooms;
    this.directions = directions;
  }
  
  /**
   * Creates new maze based on text input: First line is number of rows and columns,
   * the remaining file is the contents of the maze (' ' = EMPTY, '*' = WALL, 'S' =
   * START, and 'E' = EXIT).
   */
  public Maze(Scanner input) {
    int numRows = input.nextInt();
    int numCols = input.nextInt();
    rooms = new int[numRows][numCols];
    input.nextLine();
    for (int r = 0; r < numRows; r++) {
      String line = input.nextLine();
      for (int c = 0; c < numCols; c++) {
        char ch = line.charAt(c);
        switch (ch) {
          case ' ': rooms[r][c] = EMPTY; break;
          case '*': rooms[r][c] = WALL; break;
          case 'S': rooms[r][c] = START; break;
          case 'E': rooms[r][c] = EXIT; break;
          default: throw new IllegalArgumentException("Unknown room type: " + ch);
        }
      }
    }
  }
  
  // INSTANCE METHODS
  public int numRows() { return rooms.length; }
  public int numCols() { return rooms[0].length; }
  
  /** Clears StdDraw window and draws maze. */
  public void draw() {
    StdDraw.clear();
    StdDraw.enableDoubleBuffering();
    int size = Math.max(numRows(), numCols()); // Forces square rooms
    StdDraw.setScale(-1, size+1);
    for (int r = 0; r < numRows(); r++) {
      for (int c = 0; c < numCols(); c++) {
        switch (rooms[r][c]) {
          case EMPTY:      StdDraw.setPenColor(StdDraw.WHITE); break;
          case WALL:       StdDraw.setPenColor(StdDraw.BLACK); break;
          case START:      StdDraw.setPenColor(StdDraw.BLUE); break;
          case EXIT:       StdDraw.setPenColor(StdDraw.GREEN); break;
          case BREADCRUMB: StdDraw.setPenColor(StdDraw.ORANGE); break;
          case DOWN:       StdDraw.setPenColor(StdDraw.YELLOW); break;
          case EXIT_PATH:  StdDraw.setPenColor(StdDraw.MAGENTA); break;
          default: throw new IllegalStateException("Unknown room type: " + rooms[r][c]);
        }
        StdDraw.filledSquare(c+0.5, numRows()-r-0.5, 0.45);
        if(directions[r][c]==DOWN){
          StdDraw.setPenColor(StdDraw.BLACK);
          StdDraw.text(c+0.5, numRows()-r-0.5,"v");
          System.out.println("down");
        }
         else if(directions[r][c]==UP){
          StdDraw.setPenColor(StdDraw.BLACK);
          StdDraw.text(c+0.5, numRows()-r-0.5,"^");
          System.out.println("up");
        }
         else if(directions[r][c]==RIGHT){
          StdDraw.setPenColor(StdDraw.BLACK);
          StdDraw.text(c+0.5, numRows()-r-0.5,">");
          System.out.println("right");
        }
         else if(directions[r][c]==LEFT){
          StdDraw.setPenColor(StdDraw.BLACK);
          StdDraw.text(c+0.5, numRows()-r-0.5,"<");
          System.out.println("left");
        }
        
      }
    }
    StdDraw.show();
  }
  
  /** Returns if maze in current state is solvable from START location. */
  public boolean isSolvable() {
    for (int r = 0; r < numRows(); r++) {
      for (int c = 0; c < numCols(); c++) {
        if (rooms[r][c] == START) {
          return isSolvable(r, c);
        }
      }
    }
    throw new IllegalStateException("This maze has no START!");
  }
  
  /** Returns if maze in current state is solvable from given location. */
  private boolean isSolvable(int r, int c) {
    if (r < 0 || c < 0 || r >= numRows() || c >= numCols()) {
      return false;
    }
    int room = rooms[r][c];
    int direction = directions[r][c];
    if (room == EXIT) { return true; } 
    if (room == BREADCRUMB) { return false; }
    if (room == WALL) { return false; } 
    rooms[r][c] = BREADCRUMB;
    boolean solvable = isSolvable(r-1, c) || isSolvable(r, c+1) || isSolvable(r+1, c) || isSolvable(r, c-1);
    if (solvable) { 
      rooms[r][c] = EXIT_PATH;
      if(rooms[r][c+1]==EXIT || rooms[r][c+1]==EXIT_PATH){
        directions[r][c] = RIGHT;
      }
      else if(rooms[r+1][c]==EXIT_PATH){
        directions[r][c] = DOWN;
      }
      else if(rooms[r-1][c]==EXIT_PATH){
        directions[r][c] = UP;
      }
      else if(rooms[r][c-1]==EXIT_PATH){
        directions[r][c] = LEFT;
      }
    }
    return solvable;
  }

  public static void main(String[] args) throws FileNotFoundException {
    int[][] rooms = {
      {WALL, START, WALL,  WALL,  WALL},
      {WALL, EMPTY, WALL,  WALL,  WALL},
      {WALL, EMPTY, WALL,  WALL,  WALL},
      {WALL, EMPTY, WALL,  WALL,  WALL},
      {WALL, EMPTY, WALL,  WALL,  WALL},
      {WALL, EMPTY, WALL,  WALL,  WALL},
      {WALL, EMPTY, EMPTY, EMPTY, EXIT},
    };
    int[][] directions = {
      {EMPTY, EMPTY, EMPTY,  EMPTY,  EMPTY},
      {EMPTY, EMPTY, EMPTY,  EMPTY,  EMPTY},
      {EMPTY, EMPTY, EMPTY,  EMPTY,  EMPTY},
      {EMPTY, EMPTY, EMPTY,  EMPTY,  EMPTY},
      {EMPTY, EMPTY, EMPTY,  EMPTY,  EMPTY},
      {EMPTY, EMPTY, EMPTY,  EMPTY,  EMPTY},
      {EMPTY, EMPTY, EMPTY,  EMPTY,  EMPTY},
    };
    Maze maze = new Maze(rooms,directions);
    //Maze maze = new Maze(new Scanner(new File("maze0.txt")));
    //Maze maze = Maze.random(100, 100, 0.3);
    //maze.draw();
    System.out.println("Solvable? " + maze.isSolvable()); // Should be true for sample maze above
    maze.draw();
    //maxWallPctForSolvable(20, 20, 0.5);
  }
  
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).