Maze.java.html

  1  import java.util.ArrayList;
  2  
  3  /**
  4     A maze has its walls marked by * characters and corridors 
  5     by spaces. It can classify corridor points as dead ends,
  6     intersections, or exits, and it can extend paths from 
  7     one intersection to another. The maze is assumed not to have
  8     any cycles (i.e., paths returning to their own start.)
  9  */
 10  public class Maze
 11  {
 12     private String[] cells;
 13  
 14     /**
 15        Constructs a maze from a string describing its contents.
 16        @param contents strings consisting of * and spaces
 17     */
 18     public Maze(String[] contents)
 19     {
 20        cells = contents;
 21     }
 22  
 23     /**
 24        Gets all paths emanating from a position in the maze.
 25        @param row the row of the position
 26        @param column the column of the position
 27        @return all paths emanating from the position
 28     */
 29     public ArrayList<Path> pathsFrom(int row, int column)
 30     {
 31        ArrayList<Path> paths = new ArrayList<Path>();
 32        if (isValid(row - 1, column)) 
 33        { 
 34           paths.add(new Path(row, column, Path.NORTH));
 35        }
 36        if (isValid(row, column + 1))
 37        { 
 38           paths.add(new Path(row, column, Path.EAST));
 39        }     
 40        if (isValid(row + 1, column)) 
 41        { 
 42           paths.add(new Path(row, column, Path.SOUTH));
 43        }
 44        if (isValid(row, column - 1)) 
 45        { 
 46           paths.add(new Path(row, column, Path.WEST));
 47        }
 48        for (Path p : paths) { extend(p); }
 49        return paths;
 50     }
 51  
 52     /**
 53        Extends this path to the next exit, intersection, or dead end.
 54        @param p the path to extend
 55     */
 56     private void extend(Path p)
 57     {
 58        boolean done = false;
 59        while (!done)
 60        {
 61           p.move();
 62           int row = p.getEndingRow();
 63           int column = p.getEndingColumn();
 64           if (isExit(row, column) || countNeighbors(row, column) != 2)
 65           {
 66              done = true; // Either a straight path or a turn
 67           }
 68           else
 69           {
 70              row = p.getNextRow();
 71              column = p.getNextColumn();
 72              if (!isValid(row, column))
 73              {
 74                 p.turn();
 75                 row = p.getNextRow();
 76                 column = p.getNextColumn();
 77                 if (!isValid(row, column))
 78                 {
 79                    p.turn();
 80                    p.turn();
 81                 }            
 82              }
 83           }
 84        }
 85     }
 86  
 87     /**
 88        Checks whether a position is an exit.
 89        @param row the row of the position
 90        @param column the column of the position
 91        @return true if the position is an exit
 92     */
 93     public boolean isExit(int row, int column)
 94     {
 95        return (row == 0 || row == cells.length - 1 
 96           || column == 0 || column == cells[row].length() - 1)
 97           && cells[row].charAt(column) == ' ';
 98     }
 99  
100     /**
101        Checks whether a position is a dead end.
102        @param row the row of the position
103        @param column the column of the position
104        @return true if the position is a dead end
105     */
106     public boolean isDeadEnd(int row, int column)
107     {
108        return countNeighbors(row, column) == 1;
109     }
110  
111     /**
112        Checks whether a position is within the maze and not a wall.
113        @param row the row of the position
114        @param column the column of the position
115        @return true if the position is valid
116     */
117     private boolean isValid(int row, int column)
118     {
119        return 0 <= row && row < cells.length 
120           && 0 <= column && column < cells[row].length()
121           && cells[row].charAt(column) == ' ';
122     }
123  
124     /**
125        Counts the neighbors of a position.
126        @param row the row of the position
127        @param column the column of the position
128        @return the number of neighbors in the four compass directions
129        that are within the maze and not walls.
130     */
131     private int countNeighbors(int row, int column)
132     {
133        int count = 0;
134        if (isValid(row - 1, column)) { count++; }
135        if (isValid(row + 1, column)) { count++; }
136        if (isValid(row, column - 1)) { count++; }
137        if (isValid(row, column + 1)) { count++; }
138        return count;
139     }
140  }