Statistics
| Branch: | Revision:

root / scout / libscout / src / behaviors / maze_solve.cpp @ 754da79f

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