root / scout / libscout / src / test_behaviors / maze_solve.cpp @ 071926c2
History | View | Annotate | Download (7.79 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 |
|
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); |
48 |
|
49 |
void maze_solve::run()
|
50 |
{ |
51 |
// TODO:first initialize map to all 0's
|
52 |
ROS_INFO("Starting to solve the maze");
|
53 |
// Go up to the first line.
|
54 |
follow_line(); |
55 |
// Turn the sonar on.
|
56 |
sonar->set_on(); |
57 |
sonar->set_range(0, 23); |
58 |
|
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; |
84 |
|
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())
|
91 |
{ |
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)
|
105 |
{ |
106 |
return solved;
|
107 |
} |
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
|
128 |
{ |
129 |
//Update where we are.
|
130 |
dir = RIGHT; |
131 |
} |
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)
|
143 |
{ |
144 |
return solved;
|
145 |
} |
146 |
else
|
147 |
{ |
148 |
//Update where we are.
|
149 |
dir = DOWN; |
150 |
} |
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)
|
162 |
{ |
163 |
return solved;
|
164 |
} |
165 |
else
|
166 |
{ |
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: |
186 |
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; |
229 |
|
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;
|
260 |
} |
261 |
|
262 |
return true; |
263 |
} |
264 |
|
265 |
bool maze_solve::at_destination()
|
266 |
{ |
267 |
vector<uint32_t> readings = linesensor->query(); |
268 |
if ( readings[0] > 200 && |
269 |
readings[1] < 55 && |
270 |
readings[2] < 55 && |
271 |
readings[3] > 200 && |
272 |
readings[4] > 200 && |
273 |
readings[5] < 55 && |
274 |
readings[6] < 55 && |
275 |
readings[7] > 200 ) |
276 |
{ |
277 |
return true; |
278 |
} |
279 |
return false; |
280 |
} |