001 package proxy.mazegen;
002
003 import java.util.Vector;
004
005 /**
006 * This is a web service for generating random mazes. It has two entry points:
007 * one returns an XML version of the maze and the other returns a pretty-printed
008 * string version.
009 * @common:target-namespace namespace="http://workshop.bea.com/AccountEJBClient"
010 */
011
012 public class MazeGenerator implements java.io.Serializable, com.bea.jws.WebService
013 {
014
015 /**
016 * Returns a random maze in an XML format.
017 *
018 * @common:operation
019 * @jws:conversation phase=none
020 */
021 public int [] getRandomMaze(int rows, int columns)
022 {
023 int r, c;
024 int [] rooms = new int[rows * columns];
025
026 Maze maze = getRandomMazeImpl(rows, columns);
027 for(r = 0; r < rows; r++)
028 {
029 for(c = 0; c < columns; c++)
030 {
031 rooms[maze.toIndex(r, c)] = maze.getRoomWalls(r, c);
032 }
033 }
034 return rooms;
035 }
036
037 /**
038 * This operation generates a random maze and returns a pretty-printed string
039 * representation of it.
040 *
041 * @common:operation
042 * @jws:conversation phase="none"
043 */
044 public String printRandomMaze(int rows, int columns)
045 {
046 // Produce a random maze in our data structures.
047 Maze maze = getRandomMazeImpl(rows, columns);
048
049 // This will store the pretty-printed string. We start out with an extra
050 // newline so that it looks nice in the web UI.
051 StringBuffer buf = new StringBuffer("\n");
052
053 // Write the top row of the maze drawing. This is just a long line.
054
055 buf.append('+');
056
057 for (int i = 0; i < maze.cols; i++)
058 buf.append("--+");
059
060 buf.append('\n');
061
062 // Next, we draw 2 lines for each row of the maze.
063 for (int i = 0; i < maze.rows; i++)
064 {
065 // Write the second middle text row of this row of the maze. This will have a separator
066 // at the right end iff there is not a door between this room and the one to its right.
067
068 buf.append('|');
069
070 for (int j = 0; j < maze.cols; j++)
071 {
072 buf.append(" ");
073
074 if ((j + 1 < maze.cols) && maze.getConnected(i, j, i, j + 1))
075 buf.append(' ');
076 else
077 buf.append('|');
078 }
079
080 buf.append('\n');
081
082 // Write the bottom text row of this maze row. It has a separator iff there is a door
083 // between this room and the one below it.
084
085 buf.append("+");
086
087 for (int j = 0; j < maze.cols; j++)
088 {
089 if ((i + 1 < maze.rows) && maze.getConnected(i, j, i + 1, j))
090 buf.append(" ");
091 else
092 buf.append("--");
093
094 buf.append("+");
095
096 }
097
098 buf.append("\n");
099 }
100
101 // Return the pretty-printed string.
102 return buf.toString();
103 }
104
105 /** This is our internal datastructure for representing a maze. */
106 public static class Maze
107 {
108
109 public static int LEFT_WALL = 1;
110 public static int TOP_WALL = 2;
111 public static int RIGHT_WALL = 4;
112 public static int BOTTOM_WALL = 8;
113
114 public int rows;
115 public int cols;
116 public boolean[][] connected;
117
118 public Maze()
119 {
120 // This is necessary for using this type in an outputPart.
121 }
122
123 public Maze(int rows, int cols)
124 {
125 this.rows = rows;
126 this.cols = cols;
127 this.connected = new boolean[getIndexCount()][getIndexCount()];
128 }
129
130 public int getRows()
131 {
132 return rows;
133 }
134
135 public int getColumns()
136 {
137 return cols;
138 }
139
140 public int getIndexCount()
141 {
142 return rows * cols;
143 }
144
145 public int toIndex(int row, int col)
146 {
147 return row * cols + col;
148 }
149
150 public boolean getConnected(int row1, int col1, int row2, int col2)
151 {
152 return connected[toIndex(row1, col1)][toIndex(row2, col2)];
153 }
154
155 public void setConnected(int row1, int col1, int row2, int col2)
156 {
157 setConnected(toIndex(row1, col1), toIndex(row2, col2));
158 }
159
160 public void setConnected(int index1, int index2)
161 {
162 connected[index1][index2] = true;
163 connected[index2][index1] = true;
164 }
165
166 public int getRoomWalls(int row, int col)
167 {
168 int walls = 0;
169
170 // see if the left wall should exist: first column or column not connected on left
171 if ((col == 0) ||
172 ((col > 0) && !connected[toIndex(row,col)][toIndex(row,col-1)]))
173 {
174 walls += LEFT_WALL;
175 }
176
177 // see if the right wall should exist: last column or column not connected on right
178 if ((col == (cols-1)) ||
179 ((col < cols-1) && !connected[toIndex(row,col)][toIndex(row,col+1)]))
180 {
181 walls += RIGHT_WALL;
182 }
183
184 // see if the bottom wall should exist: first row or row not connected on bottom
185 if ((row == 0) ||
186 ((row > 0) && !connected[toIndex(row,col)][toIndex(row-1,col)]))
187 {
188 walls += BOTTOM_WALL;
189 }
190
191 // see if the top wall should exist: last row or row not connected on top
192 if ((row == (rows-1)) ||
193 ((row < rows-1) && !connected[toIndex(row,col)][toIndex(row+1,col)]))
194 {
195 walls += TOP_WALL;
196 }
197
198 return walls;
199 }
200 }
201
202 /** Returns the actual random maze. */
203 private Maze getRandomMazeImpl(int rows, int cols)
204 {
205 // Create an empty maze with no connecteness.
206 Maze maze = new Maze(rows, cols);
207
208 // Create a vector that contains all possible edges.
209
210 Vector edges = new Vector();
211
212 for (int i = 0; i < maze.rows; i++)
213 {
214 for (int j = 0; j < maze.cols; j++)
215 {
216 if (j + 1 < maze.cols)
217 edges.add(new Edge(maze.toIndex(i, j), maze.toIndex(i, j + 1)));
218
219 if (i + 1 < maze.rows)
220 edges.add(new Edge(maze.toIndex(i, j), maze.toIndex(i + 1, j)));
221 }
222 }
223
224 // Randomly permute the edges.
225 for (int i = 0; i < edges.size() - 1; i++)
226 {
227 // Pick which edge should go at this position in the array.
228 int choice = (int)((edges.size() - i) * Math.random());
229
230 // Swap the edge at this position with the one chosen.
231 Edge e = (Edge) edges.get(i);
232 edges.set(i, edges.get(choice));
233 edges.set(choice, e);
234 }
235
236 // Use a partition to determine which nodes are in the same tree.
237 Partition partition = new Partition(maze.getIndexCount());
238
239 // Try to add each edge in sequence, ensuring that no cycle is every produced.
240 for (int i = 0; i < edges.size(); i++)
241 {
242 // Retrieve the next edge from the list.
243 Edge edge = (Edge) edges.get(i);
244
245 // If the ends of this edge are not in the same tree, then connecting them
246 // will not cause a cycle.
247 if (!partition.inSameGroup(edge.index1, edge.index2))
248 {
249 // Add this edge into the maze.
250 maze.setConnected(edge.index1, edge.index2);
251
252 // Note that these two trees are now in the same tree.
253 partition.joinGroups(edge.index1, edge.index2);
254 }
255 }
256
257 // Return the maze produced.
258 return maze;
259 }
260
261 /** Stores an undirected edge between two nodes. */
262 private static class Edge
263 {
264 public int index1;
265 public int index2;
266
267 public Edge(int index1, int index2)
268 {
269 this.index1 = index1;
270 this.index2 = index2;
271 }
272 }
273
274 }
|