Revision 5d1c5d81

View differences:

scout/libscout/src/test_behaviors/maze_solve.cpp
25 25

  
26 26
#include "maze_solve.h"
27 27

  
28
#define D_THRESH 600
29
#define max(x,y) ((x > y) ? x : y)
30

  
31 28
using namespace std;
32 29

  
33
void maze_solve::spin_for(double duration)
34
{
35
    ros::Rate r(100);     // 100 hz
36
    int ticks = int(duration * 100);
37
    for (int i = 0; i < ticks; i++)
38
    {
39
        spinOnce();
40
        r.sleep();
41
    }
42
}
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);
43 48

  
44 49
void maze_solve::run()
45 50
{    
51
    // TODO:first initialize map to all 0's
46 52
    ROS_INFO("Starting to solve the maze");
47

  
48 53
    // Go up to the first line.
49 54
    follow_line();
50

  
51 55
    // Turn the sonar on.
52 56
    sonar->set_on();
53 57
    sonar->set_range(0, 23);
54 58

  
55
    ROS_INFO("Off we go!");
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;
56 84

  
57
    while (!at_destination())
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())
58 91
    {
59
        // Wait for sonar to update.
60
        spin_for(1.5);
61
        int* readings = sonar->get_sonar_readings();
62
        
63
        // Wait until the sonar gives us real values.
64
        bool readings_ok = true;
65
        cout << "[";
66
        for (int i = 0; i < 48; i++)
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)
67 105
        {
68
            if (i == 24 || i == 36 || i == 0)
69
            {
70
                cout << "(" << readings[i] << ") ";
71
            }
72
            else
73
            {
74
                cout << readings[i] << " ";
75
            }
76
            if (readings[i] == 0)
77
            {
78
                ROS_INFO("Waiting. readings[%d] == 0.", i);
79
                readings_ok = false;
80
                break;
81
            }
106
            return solved;
82 107
        }
83
        cout << endl;
84

  
85
        if (!readings_ok)
108
        else
86 109
        {
87
            continue;
110
            //Update where we are.
111
            dir = UP;
88 112
        }
89

  
90
        int r_read = max(readings[23], max(readings[24], readings[25]));
91
        int s_read = max(readings[35], max(readings[36], readings[37]));
92
        int l_read = max(readings[47], max(readings[0],  readings[1]));
93

  
94
        ROS_INFO("Left: %d. Straight: %d. Right: %d.", l_read, s_read, r_read);
95

  
96
        if (r_read > D_THRESH)      // Right
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)
97 124
        {
98
            ROS_INFO("Right.");
99
            turn_right();
125
            return solved;
100 126
        }
101
        else if (s_read > D_THRESH) // Straight
127
        else
102 128
        {
103
            ROS_INFO("Straight.");
104
            turn_straight();
129
            //Update where we are.
130
            dir = RIGHT;
105 131
        }
106
        else if (l_read > D_THRESH)   // Left
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)
107 143
        {
108
            ROS_INFO("Left.");
109
            turn_left();
144
            return solved;
110 145
        }
111
        else                                                        // Deadend
146
        else
112 147
        {
113
            ROS_INFO("Dead end.");
114
            spot_turn();
148
            //Update where we are.
149
            dir = DOWN;
115 150
        }
116

  
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);
117 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;
118 197
    }
119 198
}
120 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

  
121 265
bool maze_solve::at_destination() 
122 266
{
123 267
    vector<uint32_t> readings = linesensor->query();
124
    //ROS_INFO("Readings: %d %d %d %d %d %d %d %d.", readings[0], readings[1], readings[2], readings[3], readings[4], readings[5], readings[6], readings[7]);
125 268
    if ( readings[0] > 200 &&
126 269
         readings[1] < 55 &&
127 270
         readings[2] < 55 &&
......
131 274
         readings[6] < 55 &&
132 275
         readings[7] > 200 )
133 276
    {
134
        ROS_INFO("\n\nDESTINATION\n\n");
135 277
        return true;
136 278
    }
137 279
    return false;
scout/libscout/src/test_behaviors/maze_solve.h
26 26
#ifndef _MAZE_SOLVE_H_
27 27
#define _MAZE_SOLVE_H_
28 28

  
29
#include <stdio.h>
30 29
#include "../behaviors/line_follow.h"
31 30

  
32 31
class maze_solve: public line_follow
......
36 35
            line_follow(scoutname, "maze_solve", sensors) {};
37 36
        void run();
38 37
    private:
39
        void spin_for(double duration);
38
        bool solve(int row, int col, int dir);
39
        void turn_from_to(int current_dir, int intended_dir);
40
        bool look_around(int row, int col, int dir);
40 41
        bool at_destination();
41 42

  
42
        Duration sonar_update_time;
43

  
44 43
        int map[60][60];
45 44
};
46 45
#endif

Also available in: Unified diff