Statistics
| Branch: | Revision:

root / scout / libscout / src / behaviors / maze_solve.cpp @ 64ee446f

History | View | Annotate | Download (3.89 KB)

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
}