scoutos / scout / libscout / src / behaviors / maze_solve.cpp @ 64ee446f
History | View | Annotate | Download (3.89 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 | 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 | } |