Statistics
| Branch: | Revision:

scoutos / scout / libscout / src / test_behaviors / maze_solve.cpp @ 7b5ea072

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
}