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 }