root / scout / libscout / src / test_behaviors / maze_solve.cpp @ 4dcab71d
History | View | Annotate | Download (9.77 KB)
1 |
/**
|
---|---|
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 |
using namespace std; |
29 |
|
30 |
|
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 |
#define WALL_LIMIT 500 |
46 |
|
47 |
// @todo This is bad! It's defined globally across all files. Please put it inside a good scope. -Alex
|
48 |
Duration sonar_update_time(1.5); |
49 |
|
50 |
void maze_solve::run()
|
51 |
{ |
52 |
// @todo:first initialize map to all 0's
|
53 |
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 |
// Wait for the sonar to initialize.
|
61 |
while(!look_around(25, 25, RIGHT) && ok()) |
62 |
{ |
63 |
spinOnce(); |
64 |
} |
65 |
ROS_INFO("sonar initialized");
|
66 |
|
67 |
//spot_turn();
|
68 |
// Solve the maze
|
69 |
bool finished = solve(25,25, RIGHT, true); |
70 |
|
71 |
|
72 |
// 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 |
|
80 |
bool maze_solve::solve(int row, int col, int dir, bool root) |
81 |
{ |
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 |
|
90 |
// 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 |
{ |
97 |
spinOnce(); |
98 |
} |
99 |
|
100 |
print_board(map,row,col); |
101 |
|
102 |
/* try go up */
|
103 |
if (map[row-1][col] != WALL && (root || initial_dir != UP)) |
104 |
{ |
105 |
ROS_INFO("GOING UP!");
|
106 |
// Turn up.
|
107 |
turn_from_to(dir, UP); |
108 |
follow_line(); |
109 |
// Solve recursively.
|
110 |
bool solved = solve(row-2, col, DOWN, false); |
111 |
if (solved)
|
112 |
{ |
113 |
return solved;
|
114 |
} |
115 |
else
|
116 |
{ |
117 |
//Update where we are.
|
118 |
dir = UP; |
119 |
} |
120 |
} |
121 |
/* try down */
|
122 |
if (map[row+1][col] != WALL && (root || initial_dir != DOWN)) |
123 |
{ |
124 |
ROS_INFO("GOING DOWN!");
|
125 |
// Turn down.
|
126 |
turn_from_to(dir, DOWN); |
127 |
follow_line(); |
128 |
// Solve recursively.
|
129 |
bool solved = solve(row+2, col, UP, false); |
130 |
if (solved)
|
131 |
{ |
132 |
return solved;
|
133 |
} |
134 |
else
|
135 |
{ |
136 |
//Update where we are.
|
137 |
dir = DOWN; |
138 |
} |
139 |
} |
140 |
/* try right */
|
141 |
if (map[row][col+1] != WALL && (root || initial_dir != RIGHT)) |
142 |
{ |
143 |
ROS_INFO("GOING RIGHT!");
|
144 |
// Turn right.
|
145 |
turn_from_to(dir, RIGHT); |
146 |
follow_line(); |
147 |
// Solve recursively.
|
148 |
bool solved = solve(row, col+2, LEFT, false); |
149 |
if (solved)
|
150 |
{ |
151 |
return solved;
|
152 |
} |
153 |
else
|
154 |
{ |
155 |
//Update where we are.
|
156 |
dir = RIGHT; |
157 |
} |
158 |
} |
159 |
/* try left */
|
160 |
if (map[row][col-1] != WALL && (root || initial_dir != LEFT)) |
161 |
{ |
162 |
ROS_INFO("GOING LEFT!");
|
163 |
// Turn down.
|
164 |
turn_from_to(dir, LEFT); |
165 |
follow_line(); |
166 |
// Solve recursively.
|
167 |
bool solved = solve(row, col-2, RIGHT, false); |
168 |
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 |
ROS_INFO("%d %d", dir, initial_dir);
|
183 |
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 |
} |
206 |
} |
207 |
|
208 |
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 |
wait(2);
|
216 |
//ros::Duration(1).sleep(); //need to wait until sonar completely refreshes
|
217 |
int* readings = sonar->get_sonar_readings();
|
218 |
|
219 |
//spinOnce();
|
220 |
|
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
break;
|
271 |
} |
272 |
|
273 |
return true; |
274 |
} |
275 |
|
276 |
//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 |
bool maze_solve::at_destination()
|
337 |
{ |
338 |
vector<uint32_t> readings = linesensor->query(); |
339 |
|
340 |
//changed values so it detects solution
|
341 |
if ( readings[0] > 75 && |
342 |
readings[1] > 75 && |
343 |
readings[2] < 55 && |
344 |
readings[3] > 200 && |
345 |
readings[4] > 200 && |
346 |
readings[5] < 55 && |
347 |
readings[6] > 75 && |
348 |
readings[7] > 75 ) |
349 |
{ |
350 |
return true; |
351 |
} |
352 |
return false; |
353 |
} |