scoutos / scout / libscout / src / test_behaviors / maze_solve.cpp @ 7db6cf9f
History | View | Annotate | Download (9.77 KB)
1 | 64ee446f | Yuyang | /**
|
---|---|---|---|
2 | * Copyright (c) 2011 Colony Project
|
||
3 | *
|
||
4 | * Permission is hereby granted, free of charge, to any person
|
||
5 | * obtaining a copy of this software and associated documentation
|
||
6 | * files (the "Software"), to deal in the Software without
|
||
7 | * restriction, including without limitation the rights to use,
|
||
8 | * copy, modify, merge, publish, distribute, sublicense, and/or sell
|
||
9 | * copies of the Software, and to permit persons to whom the
|
||
10 | * Software is furnished to do so, subject to the following
|
||
11 | * conditions:
|
||
12 | *
|
||
13 | * The above copyright notice and this permission notice shall be
|
||
14 | * included in all copies or substantial portions of the Software.
|
||
15 | *
|
||
16 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
||
17 | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
|
||
18 | * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
|
||
19 | * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
|
||
20 | * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
|
||
21 | * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
|
||
22 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
|
||
23 | * OTHER DEALINGS IN THE SOFTWARE.
|
||
24 | */
|
||
25 | |||
26 | #include "maze_solve.h" |
||
27 | |||
28 | 4c9fb6ba | viki | using namespace std; |
29 | 754da79f | Priya | |
30 | 5d1c5d81 | Hui Jun Tay | |
31 | // want to have a minimal working thing, use a big enough
|
||
32 | // static array and start in the middle
|
||
33 | // we assume we are facing right, that affects where we store
|
||
34 | // wall information
|
||
35 | // -1 for wall, 0 for unseen, 1 for traveled, 2 for critical
|
||
36 | #define WALL -1 |
||
37 | #define UNSEEN 0 |
||
38 | #define SEEN 1 |
||
39 | #define CRITICAL 2 |
||
40 | // facings
|
||
41 | #define UP 0 |
||
42 | #define RIGHT 1 |
||
43 | #define DOWN 2 |
||
44 | #define LEFT 3 |
||
45 | 1cb59616 | Hui Jun Tay | #define WALL_LIMIT 500 |
46 | 5d1c5d81 | Hui Jun Tay | |
47 | 7db6cf9f | Priya | // @todo This is bad! It's defined globally across all files. Please put it inside a good scope. -Alex
|
48 | 5d1c5d81 | Hui Jun Tay | Duration sonar_update_time(1.5); |
49 | c840fbe6 | Priya | |
50 | a69f6363 | viki | void maze_solve::run()
|
51 | { |
||
52 | 7db6cf9f | Priya | // @todo:first initialize map to all 0's
|
53 | 2b0c2534 | Priya | ROS_INFO("Starting to solve the maze");
|
54 | // Go up to the first line.
|
||
55 | follow_line(); |
||
56 | // Turn the sonar on.
|
||
57 | sonar->set_on(); |
||
58 | sonar->set_range(0, 23); |
||
59 | |||
60 | 5d1c5d81 | Hui Jun Tay | // Wait for the sonar to initialize.
|
61 | while(!look_around(25, 25, RIGHT) && ok()) |
||
62 | { |
||
63 | spinOnce(); |
||
64 | } |
||
65 | 1cb59616 | Hui Jun Tay | ROS_INFO("sonar initialized");
|
66 | 5d1c5d81 | Hui Jun Tay | |
67 | 1cb59616 | Hui Jun Tay | //spot_turn();
|
68 | 5d1c5d81 | Hui Jun Tay | // Solve the maze
|
69 | 1cb59616 | Hui Jun Tay | bool finished = solve(25,25, RIGHT, true); |
70 | 5d1c5d81 | Hui Jun Tay | |
71 | 1cb59616 | Hui Jun Tay | |
72 | 5d1c5d81 | Hui Jun Tay | // Check and report final condition.
|
73 | if (finished)
|
||
74 | ROS_INFO("YAY! I have solved the maze");
|
||
75 | else
|
||
76 | ROS_INFO("NO! The maze is unsolvable");
|
||
77 | } |
||
78 | |||
79 | 1cb59616 | Hui Jun Tay | |
80 | bool maze_solve::solve(int row, int col, int dir, bool root) |
||
81 | 5d1c5d81 | Hui Jun Tay | { |
82 | int initial_dir = dir;
|
||
83 | |||
84 | ROS_INFO("I am at direction %d", dir);
|
||
85 | |||
86 | // use backtracking to solve the maze
|
||
87 | if (at_destination())
|
||
88 | return true; |
||
89 | 64ee446f | Yuyang | |
90 | 5d1c5d81 | Hui Jun Tay | // Wait for sonar to update.
|
91 | sonar_update_time.sleep(); |
||
92 | |||
93 | // this function should fill the adjacent cells around me with
|
||
94 | // wall's or paths
|
||
95 | while(!look_around(row, col, dir) && ok())
|
||
96 | 2b0c2534 | Priya | { |
97 | 5d1c5d81 | Hui Jun Tay | spinOnce(); |
98 | } |
||
99 | |||
100 | 1cb59616 | Hui Jun Tay | print_board(map,row,col); |
101 | |||
102 | 5d1c5d81 | Hui Jun Tay | /* try go up */
|
103 | 1cb59616 | Hui Jun Tay | if (map[row-1][col] != WALL && (root || initial_dir != UP)) |
104 | 5d1c5d81 | Hui Jun Tay | { |
105 | ROS_INFO("GOING UP!");
|
||
106 | // Turn up.
|
||
107 | turn_from_to(dir, UP); |
||
108 | follow_line(); |
||
109 | // Solve recursively.
|
||
110 | 1cb59616 | Hui Jun Tay | bool solved = solve(row-2, col, DOWN, false); |
111 | 5d1c5d81 | Hui Jun Tay | if (solved)
|
112 | 64ee446f | Yuyang | { |
113 | 5d1c5d81 | Hui Jun Tay | return solved;
|
114 | 64ee446f | Yuyang | } |
115 | 5d1c5d81 | Hui Jun Tay | else
|
116 | f878b5f9 | Priya | { |
117 | 5d1c5d81 | Hui Jun Tay | //Update where we are.
|
118 | dir = UP; |
||
119 | 64ee446f | Yuyang | } |
120 | 5d1c5d81 | Hui Jun Tay | } |
121 | 1cb59616 | Hui Jun Tay | /* try down */
|
122 | if (map[row+1][col] != WALL && (root || initial_dir != DOWN)) |
||
123 | 5d1c5d81 | Hui Jun Tay | { |
124 | 1cb59616 | Hui Jun Tay | ROS_INFO("GOING DOWN!");
|
125 | // Turn down.
|
||
126 | turn_from_to(dir, DOWN); |
||
127 | 5d1c5d81 | Hui Jun Tay | follow_line(); |
128 | // Solve recursively.
|
||
129 | 1cb59616 | Hui Jun Tay | bool solved = solve(row+2, col, UP, false); |
130 | 5d1c5d81 | Hui Jun Tay | if (solved)
|
131 | f878b5f9 | Priya | { |
132 | 5d1c5d81 | Hui Jun Tay | return solved;
|
133 | f878b5f9 | Priya | } |
134 | 5d1c5d81 | Hui Jun Tay | else
|
135 | f878b5f9 | Priya | { |
136 | 5d1c5d81 | Hui Jun Tay | //Update where we are.
|
137 | 1cb59616 | Hui Jun Tay | dir = DOWN; |
138 | f878b5f9 | Priya | } |
139 | 5d1c5d81 | Hui Jun Tay | } |
140 | 1cb59616 | Hui Jun Tay | /* try right */
|
141 | if (map[row][col+1] != WALL && (root || initial_dir != RIGHT)) |
||
142 | 5d1c5d81 | Hui Jun Tay | { |
143 | 1cb59616 | Hui Jun Tay | ROS_INFO("GOING RIGHT!");
|
144 | // Turn right.
|
||
145 | turn_from_to(dir, RIGHT); |
||
146 | 5d1c5d81 | Hui Jun Tay | follow_line(); |
147 | // Solve recursively.
|
||
148 | 1cb59616 | Hui Jun Tay | bool solved = solve(row, col+2, LEFT, false); |
149 | 5d1c5d81 | Hui Jun Tay | if (solved)
|
150 | f878b5f9 | Priya | { |
151 | 5d1c5d81 | Hui Jun Tay | return solved;
|
152 | f878b5f9 | Priya | } |
153 | 5d1c5d81 | Hui Jun Tay | else
|
154 | f878b5f9 | Priya | { |
155 | 5d1c5d81 | Hui Jun Tay | //Update where we are.
|
156 | 1cb59616 | Hui Jun Tay | dir = RIGHT; |
157 | 4c9fb6ba | viki | } |
158 | 5d1c5d81 | Hui Jun Tay | } |
159 | /* try left */
|
||
160 | 1cb59616 | Hui Jun Tay | if (map[row][col-1] != WALL && (root || initial_dir != LEFT)) |
161 | 5d1c5d81 | Hui Jun Tay | { |
162 | ROS_INFO("GOING LEFT!");
|
||
163 | // Turn down.
|
||
164 | turn_from_to(dir, LEFT); |
||
165 | 4c9fb6ba | viki | follow_line(); |
166 | 5d1c5d81 | Hui Jun Tay | // Solve recursively.
|
167 | 1cb59616 | Hui Jun Tay | bool solved = solve(row, col-2, RIGHT, false); |
168 | 5d1c5d81 | Hui Jun Tay | if (solved)
|
169 | { |
||
170 | return solved;
|
||
171 | } |
||
172 | else
|
||
173 | { |
||
174 | //Update where we are.
|
||
175 | dir = LEFT; |
||
176 | } |
||
177 | } |
||
178 | |||
179 | ROS_INFO("DEAD END FOUND, TURNING BACK.");
|
||
180 | // we have exhausted all the options. This path is clearly a
|
||
181 | // dead end. go back to where we come from and return false.
|
||
182 | 1cb59616 | Hui Jun Tay | ROS_INFO("%d %d", dir, initial_dir);
|
183 | 5d1c5d81 | Hui Jun Tay | turn_from_to(dir, initial_dir); |
184 | follow_line(); |
||
185 | return false; |
||
186 | } |
||
187 | |||
188 | // this function takes in the current direction and turns the scout
|
||
189 | // into it intended direction
|
||
190 | void maze_solve::turn_from_to(int current_dir, int intended_dir) { |
||
191 | switch ((4 + intended_dir - current_dir) % 4) |
||
192 | { |
||
193 | case 0: |
||
194 | spot_turn(); |
||
195 | break;
|
||
196 | case 1: |
||
197 | turn_left(); |
||
198 | break;
|
||
199 | case 2: |
||
200 | turn_straight(); |
||
201 | break;
|
||
202 | case 3: |
||
203 | turn_right(); |
||
204 | break;
|
||
205 | f878b5f9 | Priya | } |
206 | 64ee446f | Yuyang | } |
207 | |||
208 | 5d1c5d81 | Hui Jun Tay | bool maze_solve::look_around(int row, int col, int dir) |
209 | { |
||
210 | // look around current place using sonar
|
||
211 | // store whether or not
|
||
212 | // there is a wall into the map
|
||
213 | // stores at row col 2 if point is critical, 1 otherwise
|
||
214 | |||
215 | 1cb59616 | Hui Jun Tay | wait(2);
|
216 | //ros::Duration(1).sleep(); //need to wait until sonar completely refreshes
|
||
217 | 5d1c5d81 | Hui Jun Tay | int* readings = sonar->get_sonar_readings();
|
218 | 1cb59616 | Hui Jun Tay | |
219 | //spinOnce();
|
||
220 | 5d1c5d81 | Hui Jun Tay | |
221 | /*
|
||
222 | // Look to the left.
|
||
223 | int left_distance = (readings[1] + readings[0] + readings[47])/3;
|
||
224 | // Look to the front.
|
||
225 | int front_distance = (readings[35] + readings[36] + readings[37])/3;
|
||
226 | // Look to the right.
|
||
227 | int right_distance = (readings[23] + readings[24] + readings[25])/3;
|
||
228 | */
|
||
229 | // Look to the left.
|
||
230 | int left_distance = readings[0]; |
||
231 | // Look to the front.
|
||
232 | int front_distance = readings[36]; |
||
233 | // Look to the right.
|
||
234 | int right_distance = readings[24]; |
||
235 | |||
236 | ROS_INFO("front: %d left: %d right: %d", front_distance, left_distance, right_distance);
|
||
237 | |||
238 | if (right_distance == 0 || front_distance == 0 || left_distance == 0) |
||
239 | return false; |
||
240 | |||
241 | switch (dir)
|
||
242 | { |
||
243 | case UP:
|
||
244 | // If the distance is less than 500, mark the area as a wall otherwise
|
||
245 | // mark it as seen.
|
||
246 | 1cb59616 | Hui Jun Tay | map[row][col+1] = (left_distance < WALL_LIMIT)?WALL:SEEN;
|
247 | map[row+1][col] = (front_distance < WALL_LIMIT)?WALL:SEEN;
|
||
248 | map[row][col-1] = (right_distance < WALL_LIMIT)?WALL:SEEN;
|
||
249 | 5d1c5d81 | Hui Jun Tay | break;
|
250 | case RIGHT:
|
||
251 | // If the distance is less than 500, mark the area as a wall otherwise
|
||
252 | // mark it as seen.
|
||
253 | 1cb59616 | Hui Jun Tay | map[row+1][col] = (left_distance < WALL_LIMIT)?WALL:SEEN;
|
254 | map[row][col-1] = (front_distance < WALL_LIMIT)?WALL:SEEN;
|
||
255 | map[row-1][col] = (right_distance < WALL_LIMIT)?WALL:SEEN;
|
||
256 | 5d1c5d81 | Hui Jun Tay | break;
|
257 | case DOWN:
|
||
258 | // If the distance is less than 500, mark the area as a wall otherwise
|
||
259 | // mark it as seen.
|
||
260 | 1cb59616 | Hui Jun Tay | map[row][col-1] = (left_distance < WALL_LIMIT)?WALL:SEEN;
|
261 | map[row-1][col] = (front_distance < WALL_LIMIT)?WALL:SEEN;
|
||
262 | map[row][col+1] = (right_distance < WALL_LIMIT)?WALL:SEEN;
|
||
263 | 5d1c5d81 | Hui Jun Tay | break;
|
264 | case LEFT:
|
||
265 | // If the distance is less than 500, mark the area as a wall otherwise
|
||
266 | // mark it as seen.
|
||
267 | 1cb59616 | Hui Jun Tay | map[row-1][col] = (left_distance < WALL_LIMIT)?WALL:SEEN;
|
268 | map[row][col+1] = (front_distance < WALL_LIMIT)?WALL:SEEN;
|
||
269 | map[row+1][col] = (right_distance < WALL_LIMIT)?WALL:SEEN;
|
||
270 | 5d1c5d81 | Hui Jun Tay | break;
|
271 | } |
||
272 | |||
273 | return true; |
||
274 | } |
||
275 | |||
276 | 1cb59616 | Hui Jun Tay | //prints the current map
|
277 | void maze_solve::print_board(int board[60][60], int c_row, int c_col) |
||
278 | { |
||
279 | int lower_limit_r = 60; |
||
280 | int upper_limit_r = 0; |
||
281 | int lower_limit_c = 60; |
||
282 | int upper_limit_c = 0; |
||
283 | |||
284 | for(int row = 0; row<60; row++) |
||
285 | { |
||
286 | for(int col = 0; col<60; col++) |
||
287 | { |
||
288 | if (board[row][col] != UNSEEN)
|
||
289 | { |
||
290 | if (row < lower_limit_r)
|
||
291 | { |
||
292 | lower_limit_r = row; |
||
293 | } |
||
294 | if (col < lower_limit_c)
|
||
295 | { |
||
296 | lower_limit_c = col; |
||
297 | } |
||
298 | if (row > upper_limit_r)
|
||
299 | { |
||
300 | upper_limit_r = row; |
||
301 | } |
||
302 | if (col > upper_limit_c)
|
||
303 | { |
||
304 | upper_limit_c = col; |
||
305 | } |
||
306 | } |
||
307 | } |
||
308 | } |
||
309 | |||
310 | for(int row = lower_limit_r; row<=upper_limit_r; row++) |
||
311 | { |
||
312 | for(int col = lower_limit_c; col<=upper_limit_c; col++) |
||
313 | { |
||
314 | if (row == c_row && col == c_col)
|
||
315 | { |
||
316 | cout << "S";
|
||
317 | } |
||
318 | else if (board[row][col] == UNSEEN) |
||
319 | { |
||
320 | cout << " ";
|
||
321 | } |
||
322 | else if (board[row][col] == WALL) |
||
323 | { |
||
324 | cout << "#";
|
||
325 | } |
||
326 | else
|
||
327 | { |
||
328 | cout << "O";
|
||
329 | } |
||
330 | } |
||
331 | cout << endl; |
||
332 | } |
||
333 | } |
||
334 | |||
335 | |||
336 | f878b5f9 | Priya | bool maze_solve::at_destination()
|
337 | 64ee446f | Yuyang | { |
338 | f878b5f9 | Priya | vector<uint32_t> readings = linesensor->query(); |
339 | 1cb59616 | Hui Jun Tay | |
340 | 7b5ea072 | Hui Jun Tay | //changed values so it detects solution
|
341 | 1cb59616 | Hui Jun Tay | if ( readings[0] > 75 && |
342 | readings[1] > 75 && |
||
343 | f878b5f9 | Priya | readings[2] < 55 && |
344 | readings[3] > 200 && |
||
345 | readings[4] > 200 && |
||
346 | readings[5] < 55 && |
||
347 | 1cb59616 | Hui Jun Tay | readings[6] > 75 && |
348 | readings[7] > 75 ) |
||
349 | f878b5f9 | Priya | { |
350 | return true; |
||
351 | } |
||
352 | return false; |
||
353 | 64ee446f | Yuyang | } |