1 package cz.cuni.amis.utils.astar;
2
3 import java.awt.image.BufferedImage;
4 import java.io.File;
5 import java.io.IOException;
6 import java.net.URI;
7 import java.net.URISyntaxException;
8 import java.net.URL;
9 import java.util.ArrayList;
10 import java.util.Collection;
11 import java.util.List;
12 import java.util.Random;
13
14 import javax.imageio.ImageIO;
15
16 import org.junit.BeforeClass;
17 import org.junit.Test;
18
19 import cz.cuni.amis.utils.StopWatch;
20
21 public class Test04_AStar {
22
23 @BeforeClass
24 public static void before() {
25 String mazeImage = "/cz/cuni/amis/utils/astar/maze.bmp";
26 System.out.println("[INFO] Loading image " + mazeImage);
27 maze = new Maze(mazeImage);
28 System.out.println("Maze loaded...");
29 }
30
31 static Maze maze;
32
33 public static class MazeNode {
34
35 public int x;
36 public int y;
37
38 public List<MazeNode> neighs = new ArrayList<MazeNode>();
39
40 public MazeNode(int x, int y) {
41 this.x = x;
42 this.y = y;
43 }
44
45 public boolean isFree() {
46 return maze.maze[x][y];
47 }
48
49 public boolean isWall() {
50 return !maze.maze[x][y];
51 }
52
53 }
54
55 public static class Maze implements AStarMap<MazeNode> {
56
57 public boolean[][] maze = null;
58
59 public MazeNode[][] nodes = null;
60
61 private int width;
62
63 private int height;
64
65 private BufferedImage image;
66
67 private File imageFile;
68
69 public Maze(String pathToResource) {
70 Class cls = this.getClass();
71 URL url = this.getClass().getResource(pathToResource);
72 URI uri;
73 try {
74 uri = url.toURI();
75 } catch (URISyntaxException e) {
76 throw new RuntimeException("Could not obrain URI from URL: " + url.toString());
77 }
78 this.imageFile = new File(uri);
79 if (!imageFile.exists()) {
80 throw new RuntimeException("File as resource (" + pathToResource + ") does not exist at: " + imageFile.getAbsolutePath());
81 }
82
83 try {
84 this.image = ImageIO.read(imageFile);
85 } catch (IOException e) {
86 throw new RuntimeException("Could not read image from: " + imageFile.getAbsolutePath());
87 }
88
89 this.width = image.getWidth();
90 this.height = image.getHeight();
91
92 maze = new boolean[width][];
93 nodes = new MazeNode[width][];
94
95 for (int i = 0; i < width; ++i) {
96 maze[i] = new boolean[image.getHeight()];
97 nodes[i] = new MazeNode[image.getHeight()];
98 for (int j = 0; j < height; ++j) {
99 int pixel = image.getRGB(i,j);
100 int alpha = (pixel >> 24) & 0xff;
101 int red = (pixel >> 16) & 0xff;
102 int green = (pixel >> 8) & 0xff;
103 int blue = (pixel) & 0xff;
104 maze[i][j] = red != 0;
105 nodes[i][j] = new MazeNode(i, j);
106 }
107 }
108
109 for (int i = 0; i < width; ++i) {
110 for (int j = 0; j < height; ++j) {
111 if (i > 0) {
112 if (maze[i-1][j]) {
113 nodes[i][j].neighs.add(nodes[i-1][j]);
114 }
115 }
116 if (i < width-1) {
117 if (maze[i+1][j]) {
118 nodes[i][j].neighs.add(nodes[i+1][j]);
119 }
120 }
121 if (j > 0) {
122 if (maze[i][j-1]) {
123 nodes[i][j].neighs.add(nodes[i][j-1]);
124 }
125 }
126 if (j < height-1) {
127 if (maze[i][j+1]) {
128 nodes[i][j].neighs.add(nodes[i][j+1]);
129 }
130 }
131 }
132 }
133 }
134
135 @Override
136 public int getEdgeCost(MazeNode nodeFrom, MazeNode nodeTo) {
137 return Math.abs(nodeFrom.x - nodeTo.x) + Math.abs(nodeFrom.y - nodeTo.y) ;
138 }
139
140 @Override
141 public Collection<MazeNode> getNodeNeighbours(MazeNode node) {
142 return node.neighs;
143 }
144
145 public int getRGB(int r, int g, int b) {
146 int pixel = 0;
147 pixel = 255 & 0xff;
148 pixel = pixel << 8 | r;
149 pixel = pixel << 8 | g;
150 pixel = pixel << 8 | b;
151
152 return pixel;
153 }
154
155 int black = getRGB(0,0,0);
156 int red = getRGB(255,0,0);
157 int green = getRGB(0,255,0);
158 int blue = getRGB(100,100,255);
159 int white = getRGB(255,255,255);
160
161 private void setPixel(int x, int y, int rgb) {
162 if (x >= 0 && x < width && y >= 0 && y < height) {
163 image.setRGB(x,y,rgb);
164 }
165 }
166
167 private void restorePixel(int x, int y) {
168 if (x >= 0 && x < width && y >= 0 && y < height) {
169 if (maze[x][y]) image.setRGB(x,y,white);
170 else image.setRGB(x,y,black);
171 }
172 }
173
174 private void rectangle(int x, int y, int rgb) {
175 for (int i = x-4; i < x+4; ++i) {
176 for (int j = y-4; j < y+4; ++j) {
177 setPixel(i,j,rgb);
178 }
179 }
180 }
181
182 private void restoreRectangle(int x, int y) {
183 for (int i = x-4; i < x+4; ++i) {
184 for (int j = y-4; j < y+4; ++j) {
185 restorePixel(i,j);
186 }
187 }
188 }
189
190 public void output(AStarResult<MazeNode> result, int number) {
191 MazeNode start = result.getPath().get(0);
192 MazeNode end = result.getPath().get(result.getPath().size()-1);
193 int r = 100;
194 int g = 100;
195 int b = 100;
196 int i = 0;
197 for (MazeNode node : result.getPath()) {
198 ++i;
199 if (i % 10 == 0) {
200 ++r;
201 if (r == 256) {
202 g += 10;
203 r = 100;
204 }
205 if (g >= 256) {
206 b += 10;
207 g = 100;
208 }
209 if (b >= 256) {
210 b = 100;
211 }
212 }
213 image.setRGB(node.x, node.y, getRGB(r,g,b));
214 }
215 rectangle(start.x, start.y, red);
216 rectangle(end.x, end.y, green);
217 String separ = System.getProperty("file.separator");
218 String imagePath = imageFile.getAbsolutePath();
219 File out = new File(imagePath.substring(0, imagePath.lastIndexOf(separ)) + separ + "maze-result-" + (number > 9 ? number : "0" + number) + ".bmp");
220 try {
221 ImageIO.write(image, "bmp", out);
222 } catch (IOException e) {
223 throw new RuntimeException("Could not write PNG output with maze-result into " + out.getAbsolutePath(), e);
224 }
225 System.out.println("[INFO] result saved into " + out.getAbsolutePath());
226
227 restoreRectangle(start.x, start.y);
228 restoreRectangle(end.x, end.y);
229 for (MazeNode node : result.getPath()) {
230 image.setRGB(node.x, node.y, white);
231 }
232 }
233
234 @Override
235 public int getNodeCost(MazeNode node) {
236
237 return 0;
238 }
239
240 }
241
242 public class MazeHeuristic implements AStarHeuristic<MazeNode> {
243
244 private MazeNode goal;
245
246 public MazeHeuristic(MazeNode goal) {
247 this.goal = goal;
248 }
249
250 @Override
251 public int getEstimatedDistanceToGoal(MazeNode node) {
252 int dX = goal.x - node.x;
253 int dY = goal.y - node.y;
254 return (int)Math.sqrt(dX*dX+dY*dY);
255 }
256
257 }
258
259 private void test(int num, int startX, int startY, int endX, int endY, boolean expectedSuccess) {
260 System.out.println("TEST " + num + " / 44");
261 System.out.println("[INFO] " + (expectedSuccess ? "POSITIVE TEST" : "NEGATIVE TEST"));
262 System.out.println("[INFO] Start: " + startX + "," + startY);
263 System.out.println("[INFO] End: " + endX + ", " + endY);
264
265 MazeNode start = maze.nodes[startX][startY];
266 MazeNode end = maze.nodes[endX][endY];
267
268 if (expectedSuccess && !start.isFree()) {
269 System.out.println("[ERROR] Start[" + startX + "," + startY + "] is not a free point!");
270 throw new RuntimeException("[ERROR] Start[" + startX + "," + startY + "] is not a free point!");
271 }
272 if (expectedSuccess && !end.isFree()) {
273 System.out.println("[ERROR] Start[" + endX + ", " + endY + "] is not a free point!");
274 throw new RuntimeException("[ERROR] Start[" + endX + ", " + endY + "] is not a free point!");
275 }
276
277 System.out.println("[INFO] Invoking AStar!");
278 StopWatch watch = new StopWatch();
279 AStarResult<MazeNode> result = AStar.aStar(maze, new MazeHeuristic(end), start, end);
280 System.out.println("[INFO] AStar time: " + watch.stopStr() + " ms");
281
282 if (expectedSuccess != result.success) {
283 if (!result.success) {
284 System.out.println("[ERROR] Path not found! Can't be! Either someone passed wrong maze.png or AStar has failed!");
285 throw new RuntimeException("Path not found! Can't be! Either someone passed wrong maze.png or AStar has failed!");
286 } else {
287 System.out.println("[ERROR] Path found! Should not exist!");
288 throw new RuntimeException("Path found! Should not exist!");
289 }
290 }
291 if (result.success) {
292 System.out.println("[INFO] Path found!");
293 System.out.println("[INFO] Path length: " + result.getPath().size());
294 maze.output(result, num);
295 } else {
296 System.out.println("[INFO] Path does not exist! (Expected == correct)");
297 }
298
299 System.out.println("---/// TEST OK ///---");
300 }
301
302 Random random = new Random(System.currentTimeMillis());
303
304 private MazeNode getRandomNode(boolean free) {
305 int x = random.nextInt(maze.width);
306 int y = random.nextInt(maze.height);
307 while (free != maze.maze[x][y]) {
308 x = random.nextInt(maze.width);
309 y = random.nextInt(maze.height);
310 }
311 return maze.nodes[x][y];
312 }
313
314
315 private void testPositiveRandom(int num) {
316 MazeNode start = getRandomNode(true);
317 MazeNode goal = getRandomNode(true);
318 test(num, start.x, start.y, goal.x, goal.y, true);
319 }
320
321 private void testNegativeRandom(int num) {
322 MazeNode start = getRandomNode(true);
323 MazeNode goal = getRandomNode(false);
324 test(num, start.x, start.y, goal.x, goal.y, false);
325 }
326
327
328 @Test
329 public void test1() {
330 test(1, 1, 1, maze.width-1, maze.height-2, true);
331 }
332
333 @Test
334 public void test2() {
335 test(2, 1, maze.height-2, maze.width-1, maze.height-2, true);
336 }
337
338 @Test
339 public void test3() {
340 test(3, 1, maze.height-2, maze.width-2, 1, true);
341 }
342
343 @Test
344 public void test4Same() {
345 test(4, 1, 1, 1, 1, true);
346 }
347
348 @Test
349 public void test5PositiveRandom() {
350 for (int i = 0; i < 20; ++i) {
351 testPositiveRandom(5 + i);
352 }
353 }
354
355 @Test
356 public void test6NegativeRandom() {
357 for (int i = 0; i < 20; ++i) {
358 testNegativeRandom(25 + i);
359 }
360 }
361
362
363 }