1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.vectomatic.svg.edu.client.maze;
19
20 import java.util.ArrayList;
21 import java.util.List;
22 import java.util.Stack;
23
24 import org.vectomatic.dom.svg.OMSVGCircleElement;
25 import org.vectomatic.dom.svg.OMSVGDocument;
26 import org.vectomatic.dom.svg.OMSVGGElement;
27 import org.vectomatic.dom.svg.OMSVGPathElement;
28 import org.vectomatic.dom.svg.OMSVGPathSegList;
29 import org.vectomatic.dom.svg.OMSVGRect;
30 import org.vectomatic.dom.svg.OMSVGRectElement;
31 import org.vectomatic.dom.svg.OMSVGStyle;
32 import org.vectomatic.svg.edu.client.maze.Rasterizer.RasterizationResult;
33
34 import com.google.gwt.core.client.GWT;
35
36 public class RectangularMaze extends Maze {
37
38 static final String VECTOMATIC_NS = "http://www.vectomatic.org";
39
40 static final String RES_TAG = "res";
41
42 static final String START_TAG = "start";
43
44 static final String END_TAG = "end";
45
46 static final String WALL_TAG = "wall";
47
48 static final String BORDER_TAG = "border";
49 private int colCount;
50 private int rowCount;
51 private OMSVGRect bbox;
52 private OMSVGPathElement wallPath;
53 private RectangularCell[][] grid;
54 private int currentX, currentY;
55 private int srcX, srcY;
56 private int destX, destY;
57 private static MazeCss style = MazeBundle.INSTANCE.getCss();
58 private Stack<Cell> solution;
59 private OMSVGCircleElement srcCircle;
60 OMSVGPathElement destPath;
61
62 static class RectangularCell extends Cell {
63 private int x;
64 private int y;
65 private boolean onPath;
66 private OMSVGRectElement rect;
67 public RectangularCell(int x, int y) {
68 this.x = x;
69 this.y = y;
70 }
71 public void setRect(OMSVGRectElement rect) {
72 this.rect = rect;
73 }
74 @Override
75 public String getId() {
76 return "R" + x + "C" + y;
77 }
78 public String getClassName() {
79 return rect.getClassName().getBaseVal();
80 }
81 public void setClassName(String className) {
82 rect.setClassNameBaseVal(className);
83 }
84 public void setOnPath(boolean onPath) {
85 this.onPath = onPath;
86 }
87 public boolean isOnPath() {
88 return onPath;
89 }
90 public OMSVGStyle getStyle() {
91 return rect.getStyle();
92 }
93 }
94
95 private RectangularMaze(
96 Cell[] cells,
97 RasterizationResult result,
98 int colCount,
99 int rowCount,
100 OMSVGRect bbox,
101 OMSVGPathElement wallPath) {
102 super(cells);
103 this.grid = result.grid;
104 this.colCount = colCount;
105 this.rowCount = rowCount;
106 this.bbox = bbox;
107 this.wallPath = wallPath;
108 this.currentX = this.srcX = result.srcX;
109 this.currentY = this.srcY = result.srcY;
110 this.destX = result.destX;
111 this.destY = result.destY;
112 }
113 public int getColCount() {
114 return colCount;
115 }
116 public int getRowCount() {
117 return rowCount;
118 }
119 public void left() {
120 move(currentX - 1, currentY);
121 }
122 public boolean canGoLeft() {
123 int x = currentX - 1;
124 return x >= 0 && grid[x][currentY] != null && !grid[x][currentY].getBoundary(grid[currentX][currentY]).hasWall();
125 }
126 public void right() {
127 move(currentX + 1, currentY);
128 }
129 public boolean canGoRight() {
130 int x = currentX + 1;
131 return x < colCount && grid[x][currentY] != null && !grid[x][currentY].getBoundary(grid[currentX][currentY]).hasWall();
132 }
133 public void up() {
134 move(currentX, currentY - 1);
135 }
136 public boolean canGoUp() {
137 int y = currentY - 1;
138 return y >= 0 && grid[currentX][y] != null && !grid[currentX][y].getBoundary(grid[currentX][currentY]).hasWall();
139 }
140 public void down() {
141 move(currentX, currentY + 1);
142 }
143 public boolean canGoDown() {
144 int y = currentY + 1;
145 return y < rowCount && grid[currentX][y] != null && !grid[currentX][y].getBoundary(grid[currentX][currentY]).hasWall();
146 }
147 public void back() {
148 for (Cell cell : grid[currentX][currentY].getNeighbors()) {
149 if (!cell.hasWall(grid[currentX][currentY])) {
150 String cellStyle = ((RectangularCell)cell).getClassName();
151 if (style.path().equals(cellStyle) || style.src().equals(cellStyle)) {
152 if (currentX > 0 && grid[currentX - 1][currentY] == cell) {
153 left();
154 } else if (currentX < colCount - 1 && grid[currentX + 1][currentY] == cell) {
155 right();
156 } else if (currentY > 0 && grid[currentX][currentY - 1] == cell) {
157 up();
158 } else if (currentY < rowCount - 1 && grid[currentX][currentY + 1] == cell) {
159 down();
160 }
161 break;
162 }
163 }
164 }
165 }
166 public boolean canGoBack() {
167 for (Cell cell : grid[currentX][currentY].getNeighbors()) {
168 if (!cell.hasWall(grid[currentX][currentY])) {
169 String cellStyle = ((RectangularCell)cell).getClassName();
170 if (style.path().equals(cellStyle) || style.src().equals(cellStyle)) {
171 if ((currentX > 0 && grid[currentX - 1][currentY] == cell)
172 || (currentX < colCount - 1 && grid[currentX + 1][currentY] == cell)
173 || (currentY > 0 && grid[currentX][currentY - 1] == cell)
174 || (currentY < rowCount - 1 && grid[currentX][currentY + 1] == cell)) {
175 return true;
176 }
177 }
178 }
179 }
180 return false;
181 }
182 public void move(int x, int y) {
183
184 if (x < 0 || x >= colCount
185 || y < 0 || y >= rowCount
186 || grid[x][y] == null
187 || grid[x][y].getBoundary(grid[currentX][currentY]).hasWall()) {
188 return;
189 }
190
191 int prevX = currentX;
192 int prevY = currentY;
193 currentX = x;
194 currentY = y;
195 grid[prevX][prevY].setOnPath(!grid[x][y].isOnPath());
196 update(prevX, prevY);
197 }
198
199 public void update(int x, int y) {
200 if (srcX == x && srcY == y) {
201 grid[x][y].setClassName(style.src());
202 } else if (destX == x && destY == y) {
203 grid[x][y].setClassName(style.dest());
204 } else if (grid[x][y].isOnPath()) {
205 grid[x][y].setClassName(style.path());
206 } else {
207 grid[x][y].setClassName(style.blank());
208 }
209 }
210
211 public void updateCurrent() {
212 if (grid != null && grid[currentX] != null && grid[currentX][currentY] != null) {
213 if (style.current().equals(grid[currentX][currentY].getClassName())) {
214 update(currentX, currentY);
215 } else {
216 grid[currentX][currentY].setClassName(style.current());
217 }
218 }
219 }
220
221 public boolean gameWon() {
222 return currentX == destX && currentY == destY;
223 }
224 public Stack<Cell> getSolution() {
225 return solution;
226 }
227
228 public void displaySolution(boolean show) {
229 if (show) {
230 for (Cell cell : solution) {
231 if (style.blank().equals(((RectangularCell)cell).getClassName())) {
232 ((RectangularCell)cell).setClassName(style.solution());
233 }
234 }
235 } else {
236 for (Cell cell : solution) {
237 if (style.solution().equals(((RectangularCell)cell).getClassName())) {
238 ((RectangularCell)cell).setClassName(style.blank());
239 }
240 }
241 }
242 }
243
244 public static RectangularMaze createMaze(int colCount, int rowCount, OMSVGDocument document, OMSVGPathElement mazeDef, OMSVGGElement cellGroup, OMSVGPathElement borderPath, OMSVGPathElement wallPath) {
245
246
247 RasterizationResult result = Rasterizer.rasterize(mazeDef, cellGroup, colCount, rowCount);
248 long t1 = System.currentTimeMillis();
249 RectangularCell[][] grid = result.grid;
250 List<RectangularCell> list = new ArrayList<RectangularCell>();
251 for (int i = 0; i < colCount; i++) {
252 for (int j = 0; j < rowCount; j++) {
253 if (grid[i][j] != null) {
254 list.add(grid[i][j]);
255 }
256 }
257 }
258 RectangularCell[] cells = list.toArray(new RectangularCell[list.size()]);
259
260
261 long t2 = System.currentTimeMillis();
262 OMSVGRect bbox = mazeDef.getBBox();
263 float x = bbox.getX();
264 float y = bbox.getY();
265 float width = bbox.getWidth();
266 float height = bbox.getHeight();
267 float cellWidth = width / colCount;
268 float cellHeight = height / rowCount;
269 OMSVGPathSegList borderSegs = borderPath.getPathSegList();
270 for (int i = 0; i < colCount; i++) {
271 for (int j = 0; j < rowCount; j++) {
272 if ((i == 0 && grid[i][j] != null) || (i > 0 && grid[i - 1][j] == null && grid[i][j] != null)) {
273 borderSegs.appendItem(borderPath.createSVGPathSegMovetoAbs(x + i * cellWidth, y + j * cellHeight));
274 borderSegs.appendItem(borderPath.createSVGPathSegLinetoVerticalRel(cellHeight));
275 }
276 if ((i == colCount - 1 && grid[i][j] != null) || (i < colCount -1 && grid[i][j] != null && grid[i + 1][j] == null)) {
277 borderSegs.appendItem(borderPath.createSVGPathSegMovetoAbs(x + (i + 1) * cellWidth, y + j * cellHeight));
278 borderSegs.appendItem(borderPath.createSVGPathSegLinetoVerticalRel(cellHeight));
279 }
280 if ((j == 0 && grid[i][j] != null) || (j > 0 && grid[i][j - 1] == null && grid[i][j] != null)) {
281 borderSegs.appendItem(borderPath.createSVGPathSegMovetoAbs(x + i * cellWidth, y + j * cellHeight));
282 borderSegs.appendItem(borderPath.createSVGPathSegLinetoHorizontalRel(cellWidth));
283 }
284 if ((j == rowCount - 1 && grid[i][j] != null) || (j < rowCount -1 && grid[i][j] != null && grid[i][j + 1] == null)) {
285 borderSegs.appendItem(borderPath.createSVGPathSegMovetoAbs(x + i * cellWidth, y + (j + 1) * cellHeight));
286 borderSegs.appendItem(borderPath.createSVGPathSegLinetoHorizontalRel(cellWidth));
287 }
288 }
289 }
290
291
292 long t3 = System.currentTimeMillis();
293 for (int i = 0; i < colCount - 1; i++) {
294 for (int j = 0; j < rowCount; j++) {
295 if ((grid[i][j] != null) && (grid[i + 1][j] != null)) {
296 new Boundary(grid[i][j], grid[i + 1][j]);
297 }
298 }
299 }
300 for (int i = 0; i < colCount; i++) {
301 for (int j = 0; j < rowCount - 1; j++) {
302 if ((grid[i][j] != null) && (grid[i][j + 1] != null)) {
303 new Boundary(grid[i][j], grid[i][j + 1]);
304 }
305 }
306 }
307 long t4 = System.currentTimeMillis();
308
309
310 GWT.log("allocate cells = " + (t2 - t1));
311 GWT.log("ui borders = " + (t3 - t2));
312 GWT.log("allocate boundaries = " + (t4 - t3));
313 return new RectangularMaze(cells, result, colCount, rowCount, bbox, wallPath);
314 }
315
316 @Override
317 public void perfectRandomize() {
318 super.perfectRandomize();
319 long t1 = System.currentTimeMillis();
320 OMSVGPathSegList wallsSegs = wallPath.getPathSegList();
321 wallsSegs.clear();
322 int wc = 0;
323
324
325 for (int i = 0; i < colCount; i++) {
326 for (int j = 0; j < rowCount; j++) {
327 if (grid[i][j] != null) {
328 grid[i][j].setClassName(style.blank());
329 }
330 }
331 }
332
333
334 grid[srcX][srcY].setClassName(style.src());
335 grid[destX][destY].setClassName(style.dest());
336 OMSVGRectElement srcRect = grid[srcX][srcY].rect;
337 OMSVGGElement cellGroup = (OMSVGGElement)srcRect.getParentNode();
338 if (srcCircle == null) {
339 float srcX = srcRect.getX().getBaseVal().getValue();
340 float srcY = srcRect.getY().getBaseVal().getValue();
341 float srcW = srcRect.getWidth().getBaseVal().getValue();
342 float srcH = srcRect.getHeight().getBaseVal().getValue();
343 srcX += 0.1f * srcW;
344 srcY += 0.1f * srcH;
345 srcW *= 0.8f;
346 srcH *= 0.8f;
347 srcCircle = new OMSVGCircleElement(srcX + 0.5f * srcW, srcY + 0.5f * srcH, (float)Math.sqrt(0.5f * 0.5f * Math.min(srcW, srcH) * Math.min(srcW, srcH)));
348 srcCircle.setClassNameBaseVal(style.symbol());
349 cellGroup.appendChild(srcCircle);
350 }
351 if (destPath == null) {
352 OMSVGRectElement destRect = grid[destX][destY].rect;
353 float destX = destRect.getX().getBaseVal().getValue();
354 float destY = destRect.getY().getBaseVal().getValue();
355 float destW = destRect.getWidth().getBaseVal().getValue();
356 float destH = destRect.getHeight().getBaseVal().getValue();
357 destX += 0.1f * destW;
358 destY += 0.1f * destH;
359 destW *= 0.8f;
360 destH *= 0.8f;
361 destPath = new OMSVGPathElement();
362 OMSVGPathSegList destSegs = destPath.getPathSegList();
363 destSegs.appendItem(destPath.createSVGPathSegMovetoAbs(destX, destY));
364 destSegs.appendItem(destPath.createSVGPathSegLinetoAbs(destX + destW, destY));
365 destSegs.appendItem(destPath.createSVGPathSegLinetoAbs(destX + 0.5f * destW, destY + destH));
366 destSegs.appendItem(destPath.createSVGPathSegClosePath());
367 destPath.setClassNameBaseVal(style.symbol());
368 cellGroup.appendChild(destPath);
369 }
370
371 currentX = this.srcX;
372 currentY = this.srcY;
373
374
375 float x = bbox.getX();
376 float y = bbox.getY();
377 float width = bbox.getWidth();
378 float height = bbox.getHeight();
379 float cellWidth = width / colCount;
380 float cellHeight = height / rowCount;
381 for (int i = 0; i < colCount - 1; i++) {
382 boolean hasSegment = false;
383 for (int j = 0; j < rowCount; j++) {
384 if (grid[i][j] != null && grid[i + 1][j] != null && grid[i][j].getBoundary(grid[i + 1][j]).hasWall()) {
385 if (!hasSegment) {
386 wallsSegs.appendItem(wallPath.createSVGPathSegMovetoAbs(x + (i + 1) * cellWidth, y + j * cellHeight));
387 hasSegment = true;
388 }
389 if (j == rowCount -1) {
390 wallsSegs.appendItem(wallPath.createSVGPathSegLinetoVerticalAbs(y + (j + 1) * cellHeight));
391 }
392 } else {
393 if (hasSegment) {
394 wallsSegs.appendItem(wallPath.createSVGPathSegLinetoVerticalAbs(y + j * cellHeight));
395 hasSegment = false;
396 wc++;
397 }
398 }
399 }
400 }
401 for (int j = 0; j < rowCount - 1; j++) {
402 boolean hasSegment = false;
403 for (int i = 0; i < colCount; i++) {
404 if (grid[i][j] != null && grid[i][j + 1] != null && grid[i][j].getBoundary(grid[i][j + 1]).hasWall()) {
405 if (!hasSegment) {
406 wallsSegs.appendItem(wallPath.createSVGPathSegMovetoAbs(x + i * cellWidth, y + (j + 1) * cellHeight));
407 hasSegment = true;
408 }
409 if (i == colCount -1) {
410 wallsSegs.appendItem(wallPath.createSVGPathSegLinetoHorizontalAbs(x + (i + 1) * cellWidth));
411 }
412 } else {
413 if (hasSegment) {
414 wallsSegs.appendItem(wallPath.createSVGPathSegLinetoHorizontalAbs(x + i * cellWidth));
415 hasSegment = false;
416 wc++;
417 }
418 }
419 }
420 }
421 long t2 = System.currentTimeMillis();
422 solution = resolve(grid[this.srcX][this.srcY], grid[this.destX][this.destY]);
423 long t3 = System.currentTimeMillis();
424 GWT.log("ui walls = " + (t2 - t1));
425 GWT.log("wc = " + wc);
426 GWT.log("solution = " + (t3 - t2));
427 }
428 }