Revision 4c9fb6ba
Update smart_runaround and add old files.
scout/libscout/src/test_behaviors/maze_solve.cpp | ||
---|---|---|
25 | 25 |
|
26 | 26 |
#include "maze_solve.h" |
27 | 27 |
|
28 |
using namespace std;
|
|
29 |
|
|
28 |
#define D_THRESH 600
|
|
29 |
#define max(x,y) ((x > y) ? x : y) |
|
30 | 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 |
|
31 |
using namespace std; |
|
45 | 32 |
|
46 |
// TODO This is bad! It's defined globally across all files. Please put it inside a good scope. -Alex |
|
47 |
Duration sonar_update_time(1.5); |
|
33 |
void maze_solve::spin_for(double duration) |
|
34 |
{ |
|
35 |
ros::Rate r(100); // 100 hz |
|
36 |
int ticks = int(duration * 100); |
|
37 |
for (int i = 0; i < ticks; i++) |
|
38 |
{ |
|
39 |
spinOnce(); |
|
40 |
r.sleep(); |
|
41 |
} |
|
42 |
} |
|
48 | 43 |
|
49 | 44 |
void maze_solve::run() |
50 | 45 |
{ |
51 |
// TODO:first initialize map to all 0's |
|
52 | 46 |
ROS_INFO("Starting to solve the maze"); |
47 |
|
|
53 | 48 |
// Go up to the first line. |
54 | 49 |
follow_line(); |
50 |
|
|
55 | 51 |
// Turn the sonar on. |
56 | 52 |
sonar->set_on(); |
57 | 53 |
sonar->set_range(0, 23); |
58 | 54 |
|
59 |
// Wait for the sonar to initialize. |
|
60 |
while(!look_around(25, 25, RIGHT) && ok()) |
|
61 |
{ |
|
62 |
spinOnce(); |
|
63 |
} |
|
64 |
|
|
65 |
// Solve the maze |
|
66 |
bool finished = solve(25,25, RIGHT); |
|
67 |
|
|
68 |
// Check and report final condition. |
|
69 |
if (finished) |
|
70 |
ROS_INFO("YAY! I have solved the maze"); |
|
71 |
else |
|
72 |
ROS_INFO("NO! The maze is unsolvable"); |
|
73 |
} |
|
74 |
|
|
75 |
bool maze_solve::solve(int row, int col, int dir) |
|
76 |
{ |
|
77 |
int initial_dir = dir; |
|
78 |
|
|
79 |
ROS_INFO("I am at direction %d", dir); |
|
80 |
|
|
81 |
// use backtracking to solve the maze |
|
82 |
if (at_destination()) |
|
83 |
return true; |
|
55 |
ROS_INFO("Off we go!"); |
|
84 | 56 |
|
85 |
// Wait for sonar to update. |
|
86 |
sonar_update_time.sleep(); |
|
87 |
|
|
88 |
// this function should fill the adjacent cells around me with |
|
89 |
// wall's or paths |
|
90 |
while(!look_around(row, col, dir) && ok()) |
|
57 |
while (!at_destination()) |
|
91 | 58 |
{ |
92 |
spinOnce(); |
|
93 |
} |
|
94 |
|
|
95 |
/* try go up */ |
|
96 |
if (map[row-1][col] != WALL && initial_dir != UP) |
|
97 |
{ |
|
98 |
ROS_INFO("GOING UP!"); |
|
99 |
// Turn up. |
|
100 |
turn_from_to(dir, UP); |
|
101 |
follow_line(); |
|
102 |
// Solve recursively. |
|
103 |
bool solved = solve(row-1, col, DOWN); |
|
104 |
if (solved) |
|
59 |
// Wait for sonar to update. |
|
60 |
spin_for(1.5); |
|
61 |
int* readings = sonar->get_sonar_readings(); |
|
62 |
|
|
63 |
// Wait until the sonar gives us real values. |
|
64 |
bool readings_ok = true; |
|
65 |
cout << "["; |
|
66 |
for (int i = 0; i < 48; i++) |
|
105 | 67 |
{ |
106 |
return solved; |
|
68 |
if (i == 24 || i == 36 || i == 0) |
|
69 |
{ |
|
70 |
cout << "(" << readings[i] << ") "; |
|
71 |
} |
|
72 |
else |
|
73 |
{ |
|
74 |
cout << readings[i] << " "; |
|
75 |
} |
|
76 |
if (readings[i] == 0) |
|
77 |
{ |
|
78 |
ROS_INFO("Waiting. readings[%d] == 0.", i); |
|
79 |
readings_ok = false; |
|
80 |
break; |
|
81 |
} |
|
107 | 82 |
} |
108 |
else |
|
109 |
{ |
|
110 |
//Update where we are. |
|
111 |
dir = UP; |
|
112 |
} |
|
113 |
} |
|
114 |
/* try right */ |
|
115 |
if (map[row][col+1] != WALL && initial_dir != RIGHT) |
|
116 |
{ |
|
117 |
ROS_INFO("GOING RIGHT!"); |
|
118 |
// Turn right. |
|
119 |
turn_from_to(dir, RIGHT); |
|
120 |
follow_line(); |
|
121 |
// Solve recursively. |
|
122 |
bool solved = solve(row, col+1, LEFT); |
|
123 |
if (solved) |
|
124 |
{ |
|
125 |
return solved; |
|
126 |
} |
|
127 |
else |
|
83 |
cout << endl; |
|
84 |
|
|
85 |
if (!readings_ok) |
|
128 | 86 |
{ |
129 |
//Update where we are. |
|
130 |
dir = RIGHT; |
|
87 |
continue; |
|
131 | 88 |
} |
132 |
} |
|
133 |
/* try down */ |
|
134 |
if (map[row+1][col] != WALL && initial_dir != DOWN) |
|
135 |
{ |
|
136 |
ROS_INFO("GOING DOWN!"); |
|
137 |
// Turn down. |
|
138 |
turn_from_to(dir, DOWN); |
|
139 |
follow_line(); |
|
140 |
// Solve recursively. |
|
141 |
bool solved = solve(row+1, col, UP); |
|
142 |
if (solved) |
|
89 |
|
|
90 |
int r_read = max(readings[23], max(readings[24], readings[25])); |
|
91 |
int s_read = max(readings[35], max(readings[36], readings[37])); |
|
92 |
int l_read = max(readings[47], max(readings[0], readings[1])); |
|
93 |
|
|
94 |
ROS_INFO("Left: %d. Straight: %d. Right: %d.", l_read, s_read, r_read); |
|
95 |
|
|
96 |
if (r_read > D_THRESH) // Right |
|
143 | 97 |
{ |
144 |
return solved; |
|
98 |
ROS_INFO("Right."); |
|
99 |
turn_right(); |
|
145 | 100 |
} |
146 |
else |
|
101 |
else if (s_read > D_THRESH) // Straight
|
|
147 | 102 |
{ |
148 |
//Update where we are.
|
|
149 |
dir = DOWN;
|
|
103 |
ROS_INFO("Straight.");
|
|
104 |
turn_straight();
|
|
150 | 105 |
} |
151 |
} |
|
152 |
/* try left */ |
|
153 |
if (map[row][col-1] != WALL && initial_dir != LEFT) |
|
154 |
{ |
|
155 |
ROS_INFO("GOING LEFT!"); |
|
156 |
// Turn down. |
|
157 |
turn_from_to(dir, LEFT); |
|
158 |
follow_line(); |
|
159 |
// Solve recursively. |
|
160 |
bool solved = solve(row, col-1, RIGHT); |
|
161 |
if (solved) |
|
106 |
else if (l_read > D_THRESH) // Left |
|
162 | 107 |
{ |
163 |
return solved; |
|
108 |
ROS_INFO("Left."); |
|
109 |
turn_left(); |
|
164 | 110 |
} |
165 |
else |
|
111 |
else // Deadend
|
|
166 | 112 |
{ |
167 |
//Update where we are. |
|
168 |
dir = LEFT; |
|
169 |
} |
|
170 |
} |
|
171 |
|
|
172 |
ROS_INFO("DEAD END FOUND, TURNING BACK."); |
|
173 |
// we have exhausted all the options. This path is clearly a |
|
174 |
// dead end. go back to where we come from and return false. |
|
175 |
turn_from_to(dir, initial_dir); |
|
176 |
follow_line(); |
|
177 |
return false; |
|
178 |
} |
|
179 |
|
|
180 |
// this function takes in the current direction and turns the scout |
|
181 |
// into it intended direction |
|
182 |
void maze_solve::turn_from_to(int current_dir, int intended_dir) { |
|
183 |
switch ((4 + intended_dir - current_dir) % 4) |
|
184 |
{ |
|
185 |
case 0: |
|
113 |
ROS_INFO("Dead end."); |
|
186 | 114 |
spot_turn(); |
187 |
break; |
|
188 |
case 1: |
|
189 |
turn_left(); |
|
190 |
break; |
|
191 |
case 2: |
|
192 |
turn_straight(); |
|
193 |
break; |
|
194 |
case 3: |
|
195 |
turn_right(); |
|
196 |
break; |
|
197 |
} |
|
198 |
} |
|
199 |
|
|
200 |
bool maze_solve::look_around(int row, int col, int dir) |
|
201 |
{ |
|
202 |
// look around current place using sonar |
|
203 |
// store whether or not |
|
204 |
// there is a wall into the map |
|
205 |
// stores at row col 2 if point is critical, 1 otherwise |
|
206 |
|
|
207 |
int* readings = sonar->get_sonar_readings(); |
|
208 |
spinOnce(); |
|
209 |
|
|
210 |
/* |
|
211 |
// Look to the left. |
|
212 |
int left_distance = (readings[1] + readings[0] + readings[47])/3; |
|
213 |
// Look to the front. |
|
214 |
int front_distance = (readings[35] + readings[36] + readings[37])/3; |
|
215 |
// Look to the right. |
|
216 |
int right_distance = (readings[23] + readings[24] + readings[25])/3; |
|
217 |
*/ |
|
218 |
// Look to the left. |
|
219 |
int left_distance = readings[0]; |
|
220 |
// Look to the front. |
|
221 |
int front_distance = readings[36]; |
|
222 |
// Look to the right. |
|
223 |
int right_distance = readings[24]; |
|
224 |
|
|
225 |
ROS_INFO("front: %d left: %d right: %d", front_distance, left_distance, right_distance); |
|
226 |
|
|
227 |
if (right_distance == 0 || front_distance == 0 || left_distance == 0) |
|
228 |
return false; |
|
115 |
} |
|
229 | 116 |
|
230 |
switch (dir) |
|
231 |
{ |
|
232 |
case UP: |
|
233 |
// If the distance is less than 500, mark the area as a wall otherwise |
|
234 |
// mark it as seen. |
|
235 |
map[row][col+1] = (left_distance < 500)?WALL:SEEN; |
|
236 |
map[row+1][col] = (front_distance < 500)?WALL:SEEN; |
|
237 |
map[row][col-1] = (right_distance < 500)?WALL:SEEN; |
|
238 |
break; |
|
239 |
case RIGHT: |
|
240 |
// If the distance is less than 500, mark the area as a wall otherwise |
|
241 |
// mark it as seen. |
|
242 |
map[row+1][col] = (left_distance < 500)?WALL:SEEN; |
|
243 |
map[row][col-1] = (front_distance < 500)?WALL:SEEN; |
|
244 |
map[row-1][col] = (right_distance < 500)?WALL:SEEN; |
|
245 |
break; |
|
246 |
case DOWN: |
|
247 |
// If the distance is less than 500, mark the area as a wall otherwise |
|
248 |
// mark it as seen. |
|
249 |
map[row][col-1] = (left_distance < 500)?WALL:SEEN; |
|
250 |
map[row-1][col] = (front_distance < 500)?WALL:SEEN; |
|
251 |
map[row][col+1] = (right_distance < 500)?WALL:SEEN; |
|
252 |
break; |
|
253 |
case LEFT: |
|
254 |
// If the distance is less than 500, mark the area as a wall otherwise |
|
255 |
// mark it as seen. |
|
256 |
map[row-1][col] = (left_distance < 500)?WALL:SEEN; |
|
257 |
map[row][col+1] = (front_distance < 500)?WALL:SEEN; |
|
258 |
map[row+1][col] = (right_distance < 500)?WALL:SEEN; |
|
259 |
break; |
|
117 |
follow_line(); |
|
260 | 118 |
} |
261 |
|
|
262 |
return true; |
|
263 | 119 |
} |
264 | 120 |
|
265 | 121 |
bool maze_solve::at_destination() |
266 | 122 |
{ |
267 | 123 |
vector<uint32_t> readings = linesensor->query(); |
124 |
//ROS_INFO("Readings: %d %d %d %d %d %d %d %d.", readings[0], readings[1], readings[2], readings[3], readings[4], readings[5], readings[6], readings[7]); |
|
268 | 125 |
if ( readings[0] > 200 && |
269 | 126 |
readings[1] < 55 && |
270 | 127 |
readings[2] < 55 && |
... | ... | |
274 | 131 |
readings[6] < 55 && |
275 | 132 |
readings[7] > 200 ) |
276 | 133 |
{ |
134 |
ROS_INFO("\n\nDESTINATION\n\n"); |
|
277 | 135 |
return true; |
278 | 136 |
} |
279 | 137 |
return false; |
Also available in: Unified diff