Project

General

Profile

Revision c43cef09

IDc43cef099178b85870a376d778126a6f8120363b
Parent 5d1c5d81
Child 1cb59616

Added by Hui Jun Tay almost 11 years ago

Maze solve now works

View differences:

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