Revision c43cef09
Maze solve now works
scout/libscout/src/test_behaviors/smart_runaround.cpp | ||
---|---|---|
59 | 59 |
return pixels/200.0; |
60 | 60 |
} |
61 | 61 |
|
62 |
// millimeters to pixels
|
|
63 |
int mm_to_idx(float meters)
|
|
62 |
// meters to pixels |
|
63 |
int m_to_idx(float meters) |
|
64 | 64 |
{ |
65 |
// 200 pixels per meter, and 1000 millimeters per meter |
|
66 |
float pixels = meters*0.2; |
|
65 |
float pixels = meters*200.0; |
|
67 | 66 |
float idx = pixels/BLOCK_LENGTH; |
68 | 67 |
return floor(idx+0.5); |
69 | 68 |
} |
70 | 69 |
|
71 |
float *matrix_mult(float inputs[2], float matrix[2][2]) |
|
70 |
/* return a direction (if any) where adjacent block |
|
71 |
* is labeled "info" on map. Searches clockwise |
|
72 |
* starting at up. Returns -1 if no direction valid. |
|
73 |
*/ |
|
74 |
int smart_runaround::choose_direc(int row, int col, int info) |
|
72 | 75 |
{ |
73 |
float newX = matrix[0][0]*inputs[0]+matrix[0][1]*inputs[1]; |
|
74 |
float newY = matrix[1][0]*inputs[0]+matrix[1][1]*inputs[1]; |
|
75 |
float output[2] = {newX, newY}; |
|
76 |
return output; |
|
76 |
if (map[row-1][col] == info) |
|
77 |
return UP; |
|
78 |
else if (map[row][col+1] == info) |
|
79 |
return RIGHT; |
|
80 |
else if (map[row+1][col] == info) |
|
81 |
return DOWN; |
|
82 |
else if (map[row][col-1] == info) |
|
83 |
return LEFT; |
|
84 |
return -1; |
|
77 | 85 |
} |
78 | 86 |
|
79 | 87 |
// TODO This is bad! It's defined globally across all behaviors. Please fix this. -Alex |
... | ... | |
109 | 117 |
|
110 | 118 |
|
111 | 119 |
int dir = RIGHT; // current direction |
112 |
//int new_dir = RIGHT; // direction in which to turn after a scan
|
|
120 |
int new_dir = RIGHT; // direction in which to turn after a scan |
|
113 | 121 |
bool success = false; // true when maze solved |
114 | 122 |
while(ok()) |
115 | 123 |
{ |
124 |
// Look left, right, and forward |
|
116 | 125 |
look_around(row, col, dir); |
117 | 126 |
// Try moving in each direction |
118 |
/*new_dir = choose_direc(row, col, UNSEEN);
|
|
127 |
new_dir = choose_direc(row, col, UNSEEN); |
|
119 | 128 |
if(new_dir < 0) |
120 | 129 |
new_dir = choose_direc(row, col, SEEN); |
121 | 130 |
if(new_dir >= 0) { |
122 | 131 |
turn_from_to(dir, new_dir); |
123 | 132 |
dir = new_dir; |
124 |
}*/
|
|
133 |
} |
|
125 | 134 |
} |
126 | 135 |
|
127 | 136 |
// Check and report final condition. |
... | ... | |
131 | 140 |
ROS_INFO("NO! The maze is unsolvable"); |
132 | 141 |
} |
133 | 142 |
|
134 |
/* return a direction (if any) where adjacent block |
|
135 |
* is labeled "info" on map. Searches clockwise |
|
136 |
* starting at up. Returns -1 if no direction valid. |
|
137 |
*/ |
|
138 |
int smart_runaround::choose_direc(int row, int col, int info) |
|
143 |
// NOT CURRENTLY USED!!! |
|
144 |
bool smart_runaround::solve(int row, int col, int dir) |
|
139 | 145 |
{ |
140 |
if (map[row-1][col] == info) |
|
141 |
return UP; |
|
142 |
else if (map[row][col+1] == info) |
|
143 |
return RIGHT; |
|
144 |
else if (map[row+1][col] == info) |
|
145 |
return DOWN; |
|
146 |
else if (map[row][col-1] == info) |
|
147 |
return LEFT; |
|
148 |
return -1; |
|
146 |
int initial_dir = dir; |
|
147 |
|
|
148 |
ROS_INFO("I am at direction %d", dir); |
|
149 |
|
|
150 |
// use backtracking to solve the maze |
|
151 |
if (at_destination()) |
|
152 |
return true; |
|
153 |
|
|
154 |
// Wait for sonar to update. |
|
155 |
sonar_update_time2.sleep(); |
|
156 |
|
|
157 |
// this function should fill the adjacent cells around me with |
|
158 |
// wall's or paths |
|
159 |
while(!look_around(row, col, dir) && ok()) |
|
160 |
{ |
|
161 |
spinOnce(); |
|
162 |
} |
|
163 |
|
|
164 |
/* try go up */ |
|
165 |
if (map[row-1][col] != WALL && initial_dir != UP) |
|
166 |
{ |
|
167 |
ROS_INFO("GOING UP!"); |
|
168 |
// Turn up. |
|
169 |
turn_from_to(dir, UP); |
|
170 |
follow_line(); |
|
171 |
// Solve recursively. |
|
172 |
bool solved = solve(row-1, col, DOWN); |
|
173 |
if (solved) |
|
174 |
{ |
|
175 |
return solved; |
|
176 |
} |
|
177 |
else |
|
178 |
{ |
|
179 |
//Update where we are. |
|
180 |
dir = UP; |
|
181 |
} |
|
182 |
} |
|
183 |
/* try right */ |
|
184 |
if (map[row][col+1] != WALL && initial_dir != RIGHT) |
|
185 |
{ |
|
186 |
ROS_INFO("GOING RIGHT!"); |
|
187 |
// Turn right. |
|
188 |
turn_from_to(dir, RIGHT); |
|
189 |
follow_line(); |
|
190 |
// Solve recursively. |
|
191 |
bool solved = solve(row, col+1, LEFT); |
|
192 |
if (solved) |
|
193 |
{ |
|
194 |
return solved; |
|
195 |
} |
|
196 |
else |
|
197 |
{ |
|
198 |
//Update where we are. |
|
199 |
dir = RIGHT; |
|
200 |
} |
|
201 |
} |
|
202 |
/* try down */ |
|
203 |
if (map[row+1][col] != WALL && initial_dir != DOWN) |
|
204 |
{ |
|
205 |
ROS_INFO("GOING DOWN!"); |
|
206 |
// Turn down. |
|
207 |
turn_from_to(dir, DOWN); |
|
208 |
follow_line(); |
|
209 |
// Solve recursively. |
|
210 |
bool solved = solve(row+1, col, UP); |
|
211 |
if (solved) |
|
212 |
{ |
|
213 |
return solved; |
|
214 |
} |
|
215 |
else |
|
216 |
{ |
|
217 |
//Update where we are. |
|
218 |
dir = DOWN; |
|
219 |
} |
|
220 |
} |
|
221 |
/* try left */ |
|
222 |
if (map[row][col-1] != WALL && initial_dir != LEFT) |
|
223 |
{ |
|
224 |
ROS_INFO("GOING LEFT!"); |
|
225 |
// Turn down. |
|
226 |
turn_from_to(dir, LEFT); |
|
227 |
follow_line(); |
|
228 |
// Solve recursively. |
|
229 |
bool solved = solve(row, col-1, RIGHT); |
|
230 |
if (solved) |
|
231 |
{ |
|
232 |
return solved; |
|
233 |
} |
|
234 |
else |
|
235 |
{ |
|
236 |
//Update where we are. |
|
237 |
dir = LEFT; |
|
238 |
} |
|
239 |
} |
|
240 |
|
|
241 |
ROS_INFO("DEAD END FOUND, TURNING BACK."); |
|
242 |
// we have exhausted all the options. This path is clearly a |
|
243 |
// dead end. go back to where we come from and return false. |
|
244 |
turn_from_to(dir, initial_dir); |
|
245 |
follow_line(); |
|
246 |
return false; |
|
149 | 247 |
} |
150 | 248 |
|
151 | 249 |
/* this function takes in the current direction, |
... | ... | |
169 | 267 |
} |
170 | 268 |
} |
171 | 269 |
|
172 |
/* Purpose: look front, left, and right using sonar, and update |
|
173 |
* map accordingly. Returns true if and only if sonar is initialized. |
|
174 |
*/ |
|
175 | 270 |
bool smart_runaround::look_around(int row, int col, int dir) |
176 | 271 |
{ |
272 |
// look around current place using sonar |
|
273 |
// store whether or not |
|
274 |
// there is a wall into the map |
|
275 |
// stores at row col 2 if point is critical, 1 otherwise |
|
276 |
|
|
177 | 277 |
int* readings = sonar->get_sonar_readings(); |
178 | 278 |
spinOnce(); |
179 | 279 |
|
180 | 280 |
// Assumption: readings are given in millimeters - Zane |
181 | 281 |
|
182 |
<<<<<<< HEAD |
|
183 |
// matrices for going from robot's frame to base frame |
|
184 |
float rightMat[2][2] = {{0, 1}, {-1, 0}}; |
|
185 |
float downMat[2][2] = {{-1, 0}, {0, -1}}; |
|
186 |
float leftMat[2][2] = {{0, 1}, {1, 0}}; |
|
187 |
|
|
188 |
// Look to the left (and update map). |
|
189 |
float left_distance = readings[0]; // w.r.t. robot |
|
190 |
if(left_distance == 0) |
|
191 |
return false; |
|
192 |
int left_idx = -mm_to_idx(left_distance); // w.r.t. map |
|
193 |
// plot to map if indices are valid |
|
194 |
if (0 <= left_idx && left_idx < MAP_LENGTH) |
|
195 |
map[row][col+left_idx] = SEEN; |
|
196 |
|
|
197 |
// Look in the other directions (and update map). |
|
198 |
for (int i = 24; i < 48; i++) { |
|
199 |
float distance = readings[i]; // w.r.t. robot |
|
200 |
if(distance == 0) |
|
201 |
return false; |
|
202 |
if(distance >= 500) |
|
203 |
break; // too far to be accurate |
|
204 |
float theta = (M_PI/24)*i - M_PI; |
|
205 |
float xDist = distance*cos(theta); // w.r.t. robot |
|
206 |
float yDist = distance*sin(theta); // w.r.t. robot |
|
207 |
float inputs[2] = {xDist, yDist}; |
|
208 |
float *ans; |
|
209 |
|
|
210 |
// re-orient x and y distances based on direction |
|
211 |
switch(dir) { |
|
212 |
case UP: |
|
213 |
ans[0] = xDist; |
|
214 |
ans[1] = yDist; |
|
215 |
break; |
|
216 |
case RIGHT: |
|
217 |
ans = matrix_mult(inputs, rightMat); |
|
218 |
break; |
|
219 |
case DOWN: |
|
220 |
ans = matrix_mult(inputs, downMat); |
|
221 |
break; |
|
222 |
case LEFT: |
|
223 |
ans = matrix_mult(inputs, leftMat); |
|
224 |
break; |
|
225 |
} |
|
226 |
// indices into the map |
|
227 |
int pixDistX = row + mm_to_idx(ans[0]); |
|
228 |
int pixDistY = col + mm_to_idx(ans[1]); |
|
229 |
// plot to map if indices are valid |
|
230 |
if (0 <= pixDistX && pixDistX < MAP_LENGTH |
|
231 |
&& 0 <= pixDistY && pixDistY < MAP_LENGTH) |
|
232 |
map[pixDistX][pixDistY] = SEEN; |
|
233 |
======= |
|
234 | 282 |
// distances with respect to robot, NOT map |
235 | 283 |
// Look to the left. |
236 | 284 |
float left_distance = readings[0]/1000.0; |
... | ... | |
323 | 371 |
break; |
324 | 372 |
} |
325 | 373 |
map[row][col-l] = SEEN; |
326 |
>>>>>>> dbbad8ed5cba08f5500e7d333beab2d089f9956c |
|
327 | 374 |
} |
375 |
|
|
328 | 376 |
return true; |
329 | 377 |
} |
330 | 378 |
|
scout/libscout/src/test_behaviors/smart_runaround.h | ||
---|---|---|
26 | 26 |
#ifndef _SMART_RUNAROUND_H_ |
27 | 27 |
#define _SMART_RUNAROUND_H_ |
28 | 28 |
|
29 |
#include <math.h> |
|
30 | 29 |
#include "../behaviors/line_follow.h" |
31 | 30 |
/* Details about map: |
32 | 31 |
* 1 meter = 200 pixels |
... | ... | |
46 | 45 |
void run(); |
47 | 46 |
private: |
48 | 47 |
int choose_direc(int row, int col, int info); |
48 |
bool solve(int row, int col, int dir); |
|
49 | 49 |
void turn_from_to(int current_dir, int intended_dir); |
50 | 50 |
bool look_around(int row, int col, int dir); |
51 | 51 |
bool at_destination(); |
... | ... | |
60 | 60 |
* map even if it starts at a boundary and goes to |
61 | 61 |
* the other side. |
62 | 62 |
* Rows top to bottom, and columns left to right |
63 |
*/
|
|
63 |
*/ |
|
64 | 64 |
int map[MAP_LENGTH][MAP_LENGTH]; |
65 | 65 |
}; |
66 | 66 |
#endif |
Also available in: Unified diff