Revision 64ee446f
ID | 64ee446faaa45db3a768bed2c9e8a98d2b2f5075 |
a poor barebone of maze_solve that I wasn't able to finish
scout/libscout/src/behaviors/maze_solve.cpp | ||
---|---|---|
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 |
static int map[60][60]; |
|
37 |
#define WALL -1 |
|
38 |
#define UNSEEN 0 |
|
39 |
#define SEEN 1 |
|
40 |
#define CRITICAL 2 |
|
41 |
// facings |
|
42 |
#define UP 0 |
|
43 |
#define RIGHT 1 |
|
44 |
#define DOWN 2 |
|
45 |
#define LEFT 3 |
|
46 |
void maze_solve::run(){ |
|
47 |
|
|
48 |
// TODO:first initialize map to all 0's |
|
49 |
solve(25,25, RIGHT); |
|
50 |
} |
|
51 |
bool maze_solve::solve(row, col, dir) |
|
52 |
{ |
|
53 |
// use backtracking to solve the maze |
|
54 |
if (at_destination()) { |
|
55 |
// not really sure what to do next... just chill here |
|
56 |
return true; |
|
57 |
} |
|
58 |
|
|
59 |
else |
|
60 |
{ |
|
61 |
// this function should fill the adjacent cells around me with |
|
62 |
// wall's or paths |
|
63 |
look_around(row, col, dir); |
|
64 |
|
|
65 |
if (at_dead_end(row, col, dir)) |
|
66 |
{ |
|
67 |
// set the scout to a back tracking direction |
|
68 |
spot_turn(); |
|
69 |
return false; |
|
70 |
} |
|
71 |
|
|
72 |
/* try go up */ |
|
73 |
// no need to check range because we assume our map is big enough |
|
74 |
if (map[row-1][col] != WALL) |
|
75 |
{ |
|
76 |
turn_from_to(dir, UP); |
|
77 |
line_follow(); |
|
78 |
// halts at intersection |
|
79 |
bool solved = solve(row-1, col) |
|
80 |
if (solved) { |
|
81 |
//yeah!!! don't really know what to do now... |
|
82 |
// hopefully send some message to some other scout |
|
83 |
// waiting for my valuable information |
|
84 |
} |
|
85 |
else { |
|
86 |
// whoops, that path did not work out |
|
87 |
// redo the move, since the recursive call has |
|
88 |
// already put me into the right direction, I will just |
|
89 |
// drive back and halt at intersection |
|
90 |
line_follow(); |
|
91 |
// undo the turning |
|
92 |
turn_from_to() |
|
93 |
} |
|
94 |
} |
|
95 |
|
|
96 |
/* try right */ |
|
97 |
if (map[row][col+1] != WALL) |
|
98 |
{ |
|
99 |
turn_from |
|
100 |
} |
|
101 |
|
|
102 |
} |
|
103 |
|
|
104 |
} |
|
105 |
|
|
106 |
// this function takes in the current direction and turns the scout |
|
107 |
// into it intended direction |
|
108 |
void maze_solve::turn_from_to(int current_dir, int intended_dir) { |
|
109 |
switch ((4 + intended_dir - current_dir) % 4) |
|
110 |
case 0: |
|
111 |
turn_straight(); |
|
112 |
break; |
|
113 |
case 1: |
|
114 |
turn_right(); |
|
115 |
break; |
|
116 |
case 2: |
|
117 |
break; |
|
118 |
case 3: |
|
119 |
turn_left(); |
|
120 |
break; |
|
121 |
} |
|
122 |
|
|
123 |
int maze_solve::look_around(row, col) |
|
124 |
{ |
|
125 |
// look around current place using sonar |
|
126 |
// store whether or not |
|
127 |
// there is a wall into the map |
|
128 |
// stores at row col 2 if point is critical, 1 otherwise |
|
129 |
} |
|
130 |
|
|
131 |
bool maze_solve::at_destination() |
|
132 |
{ |
|
133 |
|
|
134 |
} |
|
135 |
|
|
136 |
bool wall_in_direction() |
|
137 |
{ |
|
138 |
|
|
139 |
} |
scout/libscout/src/behaviors/maze_solve.h | ||
---|---|---|
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 |
#ifndef _MAZE_SOLVE_H_ |
|
27 |
#define _MAZE_SOLVE_H_ |
|
28 |
|
|
29 |
#include "../Behavior.h" |
|
30 |
|
|
31 |
class maze_solve: public line_follow |
|
32 |
{ |
|
33 |
public: |
|
34 |
maze_solve(std::string scoutname, Sensors* sensors): |
|
35 |
line_follow(scoutname, "maze_solve", sensors) {}; |
|
36 |
void run(); |
|
37 |
} |
|
38 |
#endif |
|
39 |
|
Also available in: Unified diff