Statistics
| Branch: | Revision:

root / scout / libscout / src / behaviors / maze_solve.cpp @ 2b0c2534

History | View | Annotate | Download (7.51 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
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 754da79f Priya
46 64ee446f Yuyang
void maze_solve::run(){
47
    
48
    // TODO:first initialize map to all 0's
49 2b0c2534 Priya
    ROS_INFO("Starting to solve the maze");
50
    // Go up to the first line.
51
    follow_line();
52
    // Turn the sonar on.
53
    sonar->set_on();
54
    sonar->set_range(0, 23);
55
56
    // Wait for the sonar to initialize.
57
    while(!look_around(25, 25, RIGHT) && ok())
58
    {
59
      spinOnce();      
60
    }
61
62
    // Solve the maze
63
    bool finished = solve(25,25, RIGHT);
64
65
    // Check and report final condition.
66
    if (finished)
67
        ROS_INFO("YAY! I have solved the maze");
68
    else
69
        ROS_INFO("NO! The maze is unsolvable");
70 64ee446f Yuyang
}
71 f878b5f9 Priya
72
bool maze_solve::solve(int row, int col, int dir)
73
{
74 754da79f Priya
    int initial_dir = dir;
75 f878b5f9 Priya
76 64ee446f Yuyang
    // use backtracking to solve the maze
77 f878b5f9 Priya
    if (at_destination())
78 64ee446f Yuyang
        return true;
79
80 f878b5f9 Priya
    // this function should fill the adjacent cells around me with
81
    // wall's or paths
82 2b0c2534 Priya
    while(!look_around(row, col, dir) && ok())
83
    {
84
        spinOnce();
85
    }
86 f878b5f9 Priya
87
    /* try go up */
88 2b0c2534 Priya
    ROS_INFO("GOING UP!");
89 f878b5f9 Priya
    if (map[row-1][col] != WALL && initial_dir != UP)
90 64ee446f Yuyang
    {
91 f878b5f9 Priya
        // Turn up.
92
        turn_from_to(dir, UP);
93 754da79f Priya
        follow_line();
94 f878b5f9 Priya
        // Solve recursively.
95
        bool solved = solve(row-1, col, DOWN);
96
        if (solved)
97 64ee446f Yuyang
        {
98 f878b5f9 Priya
            return solved;
99 64ee446f Yuyang
        }
100 f878b5f9 Priya
        else
101 64ee446f Yuyang
        {
102 f878b5f9 Priya
            //Update where we are.
103
            dir = UP;
104 64ee446f Yuyang
        }
105 f878b5f9 Priya
    }
106
    /* try right */
107 2b0c2534 Priya
    ROS_INFO("GOING RIGHT!");
108 f878b5f9 Priya
    if (map[row][col+1] != WALL && initial_dir != RIGHT)
109
    {
110
        // Turn right.
111
        turn_from_to(dir, RIGHT);
112 754da79f Priya
        follow_line();
113 f878b5f9 Priya
        // Solve recursively.
114
        bool solved = solve(row, col+1, LEFT);
115
        if (solved)
116 64ee446f Yuyang
        {
117 f878b5f9 Priya
            return solved;
118
        }
119
        else
120
        {
121
            //Update where we are.
122
            dir = RIGHT;
123 64ee446f Yuyang
        }
124
    }
125 f878b5f9 Priya
    /* try down */
126 2b0c2534 Priya
    ROS_INFO("GOING DOWN!");
127 f878b5f9 Priya
    if (map[row+1][col] != WALL && initial_dir != DOWN)
128
    {
129
        // Turn down.
130
        turn_from_to(dir, DOWN);
131 754da79f Priya
        follow_line();
132 f878b5f9 Priya
        // Solve recursively.
133
        bool solved = solve(row+1, col, UP);
134
        if (solved)
135
        {
136
            return solved;
137
        }
138
        else
139
        {
140
            //Update where we are.
141
            dir = DOWN;
142
        }
143
    }
144
    /* try left */
145 2b0c2534 Priya
    ROS_INFO("GOING LEFT!");
146 f878b5f9 Priya
    if (map[row][col-1] != WALL && initial_dir != LEFT)
147
    {
148
        // Turn down.
149
        turn_from_to(dir, LEFT);
150 754da79f Priya
        follow_line();
151 f878b5f9 Priya
        // Solve recursively.
152
        bool solved = solve(row, col-1, RIGHT);
153
        if (solved)
154
        {
155
            return solved;
156
        }
157
        else
158
        {
159
            //Update where we are.
160
            dir = LEFT;
161
        }
162
    }
163
    // we have exhausted all the options. This path is clearly a
164
    // dead end. go back to where we come from and return false.
165
    turn_from_to(dir, initial_dir);
166 754da79f Priya
    follow_line();
167 f878b5f9 Priya
    return false;
168 64ee446f Yuyang
}
169
170
// this function takes in the current direction and turns the scout
171
// into it intended direction
172
void maze_solve::turn_from_to(int current_dir, int intended_dir) {
173
    switch ((4 + intended_dir - current_dir) % 4) 
174 754da79f Priya
    {
175 64ee446f Yuyang
        case 0:
176 f878b5f9 Priya
            spot_turn();
177 64ee446f Yuyang
            break;
178
        case 1:
179
            turn_right();
180
            break;
181
        case 2:
182 f878b5f9 Priya
            turn_straight();
183 64ee446f Yuyang
            break;
184
        case 3:
185
            turn_left();
186
            break;
187 754da79f Priya
    }
188 64ee446f Yuyang
}
189
190 2b0c2534 Priya
bool maze_solve::look_around(int row, int col, int dir)
191 64ee446f Yuyang
{
192
    // look around current place using sonar
193
    // store whether or not
194
    // there is a wall into the map
195
    // stores at row col 2 if point is critical, 1 otherwise
196
    
197 754da79f Priya
    int* readings = sonar->get_sonar_readings();
198 2b0c2534 Priya
    spinOnce();
199 f878b5f9 Priya
200 2b0c2534 Priya
/*
201
    // Look to the left.
202
    int left_distance = (readings[1] + readings[0] + readings[47])/3;
203 f878b5f9 Priya
    // Look to the front.
204 2b0c2534 Priya
    int front_distance = (readings[35] + readings[36] + readings[37])/3;
205
    // Look to the right.
206
    int right_distance = (readings[23] + readings[24] + readings[25])/3;
207
*/
208 f878b5f9 Priya
    // Look to the left.
209 2b0c2534 Priya
    int left_distance = readings[0];
210
    // Look to the front.
211
    int front_distance = readings[36];
212
    // Look to the right.
213
    int right_distance = readings[24];
214
215
    ROS_INFO("front: %d  left: %d  right: %d", front_distance, left_distance, right_distance);
216
217
    if (right_distance == 0 || front_distance == 0 || left_distance == 0)
218
      return false;
219
220 f878b5f9 Priya
    switch (dir)
221
    {
222
        case UP:
223
            // If the distance is less than 500, mark the area as a wall otherwise
224
            // mark it as seen.
225
            map[row][col+1] = (left_distance < 500)?WALL:SEEN;
226
            map[row+1][col] = (front_distance < 500)?WALL:SEEN;
227
            map[row][col-1] = (right_distance < 500)?WALL:SEEN;
228
            break;
229
        case RIGHT:
230
            // If the distance is less than 500, mark the area as a wall otherwise
231
            // mark it as seen.
232
            map[row+1][col] = (left_distance < 500)?WALL:SEEN;
233
            map[row][col-1] = (front_distance < 500)?WALL:SEEN;
234
            map[row-1][col] = (right_distance < 500)?WALL:SEEN;
235
            break;
236
        case DOWN:
237
            // If the distance is less than 500, mark the area as a wall otherwise
238
            // mark it as seen.
239
            map[row][col-1] = (left_distance < 500)?WALL:SEEN;
240
            map[row-1][col] = (front_distance < 500)?WALL:SEEN;
241
            map[row][col+1] = (right_distance < 500)?WALL:SEEN;
242
            break;
243
        case LEFT:
244
            // If the distance is less than 500, mark the area as a wall otherwise
245
            // mark it as seen.
246
            map[row-1][col] = (left_distance < 500)?WALL:SEEN;
247
            map[row][col+1] = (front_distance < 500)?WALL:SEEN;
248
            map[row+1][col] = (right_distance < 500)?WALL:SEEN;
249
            break;
250
    }
251 2b0c2534 Priya
252
    return true;
253 64ee446f Yuyang
}
254
255 f878b5f9 Priya
bool maze_solve::at_destination() 
256 64ee446f Yuyang
{
257 f878b5f9 Priya
    vector<uint32_t> readings = linesensor->query();
258
    if ( readings[0] > 200 &&
259
         readings[1] < 55 &&
260
         readings[2] < 55 &&
261
         readings[3] > 200 &&
262
         readings[4] > 200 &&
263
         readings[5] < 55 &&
264
         readings[6] < 55 &&
265
         readings[7] > 200 )
266
    {
267
        return true;
268
    }
269
    return false;
270 64ee446f Yuyang
}