Colony » Colony Scout » Colony Scout OS

/**

 * Copyright (c) 2011 Colony Project

 * 

 * Permission is hereby granted, free of charge, to any person

 * obtaining a copy of this software and associated documentation

 * files (the "Software"), to deal in the Software without

 * restriction, including without limitation the rights to use,

 * copy, modify, merge, publish, distribute, sublicense, and/or sell

 * copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following

 * conditions:

 * 

 * The above copyright notice and this permission notice shall be

 * included in all copies or substantial portions of the Software.

 * 

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT

 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,

 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 * OTHER DEALINGS IN THE SOFTWARE.

 */

#include "maze_solve.h"

using namespace std;

// want to have a minimal working thing, use a big enough 

// static array and start in the middle

// we assume we are facing right, that affects where we store

// wall information

// -1 for wall, 0 for unseen, 1 for traveled, 2 for critical

static int map[60][60];

#define WALL -1

#define UNSEEN 0

#define SEEN 1

#define CRITICAL 2

// facings

#define UP 0

#define RIGHT 1

#define DOWN 2

#define LEFT 3

void maze_solve::run(){

    // TODO:first initialize map to all 0's

    solve(25,25, RIGHT);

}

bool maze_solve::solve(int row, int col, int dir)

{

    int intial_dir = dir;

    // use backtracking to solve the maze

    if (at_destination())

        return true;

    // this function should fill the adjacent cells around me with

    // wall's or paths

    look_around(row, col, dir);

    /* try go up */

    if (map[row-1][col] != WALL && initial_dir != UP)

    {

        // Turn up.

        turn_from_to(dir, UP);

        line_follow();

        // Solve recursively.

        bool solved = solve(row-1, col, DOWN);

        if (solved)

        {

            return solved;

        }

        else

        {

            //Update where we are.

            dir = UP;

        }

    }

    /* try right */

    if (map[row][col+1] != WALL && initial_dir != RIGHT)

    {

        // Turn right.

        turn_from_to(dir, RIGHT);

        line_follow();

        // Solve recursively.

        bool solved = solve(row, col+1, LEFT);

        if (solved)

        {

            return solved;

        }

        else

        {

            //Update where we are.

            dir = RIGHT;

        }

    }

    /* try down */

    if (map[row+1][col] != WALL && initial_dir != DOWN)

    {

        // Turn down.

        turn_from_to(dir, DOWN);

        line_follow();

        // Solve recursively.

        bool solved = solve(row+1, col, UP);

        if (solved)

        {

            return solved;

        }

        else

        {

            //Update where we are.

            dir = DOWN;

        }

    }

    /* try left */

    if (map[row][col-1] != WALL && initial_dir != LEFT)

    {

        // Turn down.

        turn_from_to(dir, LEFT);

        line_follow();

        // Solve recursively.

        bool solved = solve(row, col-1, RIGHT);

        if (solved)

        {

            return solved;

        }

        else

        {

            //Update where we are.

            dir = LEFT;

        }

    }

    // we have exhausted all the options. This path is clearly a

    // dead end. go back to where we come from and return false.

    turn_from_to(dir, initial_dir);

    line_follow();

    return false;

}

// this function takes in the current direction and turns the scout

// into it intended direction

void maze_solve::turn_from_to(int current_dir, int intended_dir) {

    switch ((4 + intended_dir - current_dir) % 4) 

        case 0:

            spot_turn();

            break;

        case 1:

            turn_right();

            break;

        case 2:

            turn_straight();

            break;

        case 3:

            turn_left();

            break;

}

void maze_solve::look_around(int row, int col, int dir)

{

    // look around current place using sonar

    // store whether or not

    // there is a wall into the map

    // stores at row col 2 if point is critical, 1 otherwise

    int* readings = get_sonar_readings();

    // Look to the right.

    int right_distance = (readings[1] + readings[0] + readings[47])/3;

    // Look to the front.

    int front_distance = (readings[11] + readings[12] + readings[13])/3;

    // Look to the left.

    int left_distance = (readings[23] + readings[24] + readings[25])/3;

    switch (dir)

    {

        case UP:

            // If the distance is less than 500, mark the area as a wall otherwise

            // mark it as seen.

            map[row][col+1] = (left_distance < 500)?WALL:SEEN;

            map[row+1][col] = (front_distance < 500)?WALL:SEEN;

            map[row][col-1] = (right_distance < 500)?WALL:SEEN;

            break;

        case RIGHT:

            // If the distance is less than 500, mark the area as a wall otherwise

            // mark it as seen.

            map[row+1][col] = (left_distance < 500)?WALL:SEEN;

            map[row][col-1] = (front_distance < 500)?WALL:SEEN;

            map[row-1][col] = (right_distance < 500)?WALL:SEEN;

            break;

        case DOWN:

            // If the distance is less than 500, mark the area as a wall otherwise

            // mark it as seen.

            map[row][col-1] = (left_distance < 500)?WALL:SEEN;

            map[row-1][col] = (front_distance < 500)?WALL:SEEN;

            map[row][col+1] = (right_distance < 500)?WALL:SEEN;

            break;

        case LEFT:

            // If the distance is less than 500, mark the area as a wall otherwise

            // mark it as seen.

            map[row-1][col] = (left_distance < 500)?WALL:SEEN;

            map[row][col+1] = (front_distance < 500)?WALL:SEEN;

            map[row+1][col] = (right_distance < 500)?WALL:SEEN;

            break;

    }

}

bool maze_solve::at_destination() 

{

    vector<uint32_t> readings = linesensor->query();

    if ( readings[0] > 200 &&

         readings[1] < 55 &&

         readings[2] < 55 &&

         readings[3] > 200 &&

         readings[4] > 200 &&

         readings[5] < 55 &&

         readings[6] < 55 &&

         readings[7] > 200 )

    {

        return true;

    }

    return false;

}