File content as of revision 14:4739a7ef4251:

enum WALLS
{
    EMPTY   = 0x00,
    RIGHT   = 0x01,
    LEFT    = 0x02,
    BOTTOM  = 0x04,
    TOP     = 0x08,


    NTOP    = 0x07,
    NBOTTOM = 0x0B,
    NLEFT   = 0x0D,
    NRIGHT  = 0x0E,
    FULL    = 0x0F
};

enum DIRECTION
{ 
    NORTH = 0,
    EAST  = 1,
    SOUTH = 2,
    WEST  = 3,
};

enum OPERATION
{
    HALT                = 0x00,
    FORWARD             = 0x01,
    TURN_RIGHT          = 0x02,
    TURN_LEFT           = 0x03,
    TURN_AROUND         = 0x04,
    SENSE_RIGHT         = 0x05,
    SENSE_LEFT          = 0x06,
    SENSE_FRONT         = 0x07,
};

int orientation = 0;

void updateOrientation(signed int change)
{
        orientation += change;
        orientation %= 4;
};

const int size = 16;

unsigned char maze1s[16][16]    =   {
    // 1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16
    {0xA, 0xC, 0xC, 0xD, 0xE, 0xC, 0x9, 0xF, 0xA, 0xC, 0xC, 0xD, 0xE, 0x8, 0xC, 0xD},  // 1
    {0x3, 0xB, 0xA, 0xD, 0xA, 0xD, 0x2, 0x8, 0x4, 0xC, 0xC, 0xC, 0xC, 0x4, 0xC, 0xD},  // 2
    {0x3, 0x2, 0x5, 0xE, 0x4, 0xC, 0x5, 0x3, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 3
    {0x3, 0x3, 0xB, 0xA, 0xC, 0xC, 0x8, 0x1, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 4
    {0x3, 0x3, 0x3, 0x6, 0xC, 0x9, 0x3, 0x3, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 5
    {0x6, 0x4, 0x4, 0xC, 0xC, 0x1, 0x3, 0x3, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 6
    {0xA, 0xC, 0xC, 0xC, 0x9, 0x3, 0x2, 0x4, 0xC, 0x9, 0xA, 0xC, 0xC, 0xC, 0xC, 0x9},  // 7
    {0x6, 0xC, 0x8, 0x9, 0x3, 0x3, 0x3, 0xA, 0x9, 0x3, 0x2, 0xC, 0xC, 0xC, 0xD, 0x3},  // 8
    {0xB, 0xB, 0x3, 0x3, 0x3, 0x2, 0x1, 0x6, 0x4, 0x1, 0x2, 0xC, 0xC, 0xD, 0xB, 0x3},  // 9
    {0x2, 0x5, 0x3, 0x3, 0x3, 0x3, 0x6, 0xC, 0xC, 0x4, 0x4, 0x9, 0xA, 0x9, 0x3, 0x3},  // 10
    {0x3, 0xB, 0x7, 0x3, 0x3, 0x7, 0xA, 0xC, 0xC, 0xC, 0x8, 0x5, 0x2, 0x4, 0x4, 0x1},  // 11
    {0x3, 0x2, 0x8, 0x1, 0x6, 0xD, 0x2, 0xC, 0xC, 0x9, 0x6, 0xC, 0x4, 0xC, 0x9, 0x3},  // 12
    {0x3, 0x3, 0x3, 0x3, 0xA, 0xC, 0x4, 0xC, 0x9, 0x6, 0xC, 0xC, 0xC, 0x9, 0x3, 0x3},  // 13
    {0x3, 0x3, 0x3, 0x3, 0x2, 0xC, 0xC, 0xC, 0x4, 0x8, 0xC, 0xC, 0xD, 0x3, 0x3, 0x3},  // 14
    {0x6, 0x5, 0x3, 0x6, 0x0, 0xC, 0xC, 0xC, 0xD, 0x3, 0xE, 0xC, 0xC, 0x1, 0x7, 0x7},  // 15
    {0xE, 0xC, 0x4, 0xC, 0x4, 0xC, 0xC, 0xC, 0xD, 0x6, 0xC, 0xC, 0xC, 0x4, 0xC, 0xD}   // 16
};

unsigned char maze1[16][16] =   {
    // 0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15  
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 0
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 1
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 2
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 3
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 4
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF},  // 5
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xD, 0x8, 0xC, 0x8, 0x9, 0xA, 0x9},  // 6
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xD, 0x0, 0x9, 0x3, 0x3, 0x3, 0x3},  // 7
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0x3, 0x2, 0x1, 0x3, 0x3, 0x3},  // 8
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xE, 0x1, 0x7, 0x2, 0x1, 0x3, 0x3},  // 9
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xA, 0x5, 0xE, 0x5, 0x6, 0x1, 0x3},  // 10
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0x3, 0xA, 0x1, 0xA, 0x9, 0x3, 0x3},  // 11
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3},  // 12
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3, 0x3},  // 13
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0x6, 0x5, 0x2, 0x5, 0x3, 0x3, 0x3},  // 14
    {0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xD, 0xC, 0x4, 0xD, 0x6, 0x5, 0x7},  // 15
};

signed int maze1F[16][16] = {
   // 1   2  3    4   5   6   7   8   9  10  11  12  13  14  15  16
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, //1
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, //3
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, //5
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},  //7
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},  //10
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 12
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // 14
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1} // 16
};

// Visual Functions
void printmaze();
void printflood();

// important Functions
void floodStep();
void findPath();
void createDirections();

// CELL[i][j] <---> BYTE
unsigned char cellToByte(int i, int j)
{
    unsigned char byteVal = 0;

    int newi = i;
    int newj = j;

    if(newi >= 8)
    {
        byteVal += 0x80;
        newi-=8;
    }
    if(newi >= 4)
    {
        byteVal += 0x40;
        newi-=4;
    }
    if(newi >= 2)
    {
        byteVal += 0x20;
        newi-=2;
    }
    if(newi >= 1)
    {
        byteVal += 0x10;
        newi--;
    }

    if(newj >= 8)
    {
        byteVal += 0x8;
        newj-=8;
    }
    if(newj >= 4)
    {
        byteVal += 0x4;
        newj-=4;
    }
    if(newj >= 2)
    {
        byteVal += 0x2;
        newj-=2;
    }
    if(newj >= 1)
    {
        byteVal += 0x1;
        newj--;
    }

    return byteVal;
}
unsigned int  colFromByte(unsigned char byte)
{
    return (byte & 0x0F);
}
unsigned int  rowFromByte(unsigned char byte)
{
    return colFromByte((byte >> 4));
}

int highestSurrounding(int r, int c)
{
    int top = -1;
    if(r > 0 && !(maze1[r][c] & TOP))
        top = maze1F[r-1][c];

    int bottom = -1;
    if(r < size-1 && !(maze1[r][c] & BOTTOM))
        bottom = maze1F[r+1][c];

    int left = -1;
    if(c > 0 && !(maze1[r][c] & LEFT))
        left = maze1F[r][c-1];

    int right = -1;
    if(c < size-1 && !(maze1[r][c] & RIGHT) )
        right = maze1F[r][c+1];

    int max = top;

    if(bottom > max)
        max = bottom;

    if(left > max)
        max = left;

    if(right > max)
        max = right;

    return max;
}


// Global Vars
int startRow = 15;   // Start loc
int startCol = 15;

int destRow = 9;    // Destination loc
int destCol = 9;

int currRow = startRow;    // Current Loc
int currCol = startCol;

unsigned int Movements[5000];
int moveCounter = 0;


int currentDistance = 0; // Flooding 

unsigned char* directions;

void floodStep()
{
    currentDistance++;

    int changed = 0;
    unsigned char changes[256];

    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            if(maze1F[i][j] != -1)
            {
                continue;
            }
            else
            {
                if(highestSurrounding(i,j) != -1)
                {
                    changes[changed] = cellToByte(i, j);
                    changed++;
                }
            }
        }
    }

    for(int k = 0; k < changed; k++)
    {
        maze1F[rowFromByte(changes[k])][colFromByte(changes[k])] = currentDistance;
    }
}

void findPath()
{
    int i = destRow;
    int j = destCol;

    int di = 0;
    int dj = 0;

    int counter = 0;

    directions = new unsigned char[currentDistance];

    while((i != startRow) || (j != startCol))
    {
        int min = maze1F[i][j];

        if(i > 0 && !(maze1[i][j] & TOP))
        {
            if(maze1F[i-1][j] < min && maze1F[i-1][j] != -1)
            {
                min = maze1F[i-1][j];
                di = -1;
                dj = 0;
            }

        }

        if(i < size-1 && !(maze1[i][j] & BOTTOM))
        {
            if(maze1F[i+1][j] < min && maze1F[i+1][j] != -1)
            {
                min = maze1F[i+1][j];
                di = 1;
                dj = 0;
            }
        }

        if(j > 0 && !(maze1[i][j] & LEFT))
        {
            if(maze1F[i][j-1] < min && maze1F[i][j-1] != -1)
            {
                min = maze1F[i][j-1];
                di = 0;
                dj = -1;
            }

        }

        if(j < size-1 && !(maze1[i][j] & RIGHT))
        {
            if(maze1F[i][j+1] < min && maze1F[i][j+1] != -1)
            {
                min = maze1F[i][j+1];
                di = 0;
                dj = 1;
            }
        }

        i += di;
        j += dj;

        counter++;
    
        unsigned char byteVal = cellToByte(i, j);

        directions[currentDistance - counter] = byteVal;

    }
}

void turnRight()
{
    updateOrientation(1);

}

void turnLeft()
{
    updateOrientation(3);
}

void createDirections()
{
    int prevRow = rowFromByte(directions[0]);
    int prevCol = colFromByte(directions[0]);
    unsigned char prevByte = directions[0];

    directions[currentDistance] = cellToByte(destRow, destCol);

    for(int d = 1; d <= currentDistance; d++)
    {
        int row = rowFromByte(directions[d]);
        int col = colFromByte(directions[d]);
        unsigned char byte = directions[d];
        
        switch(orientation)
        {
            case NORTH:
                switch((prevByte-byte))
                {
                    case -1: // GO RIGHT ONE CELL
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case 1:  // GO LEFT
                        Movements[moveCounter++] = TURN_LEFT;
                        turnLeft();
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case 16: // GO UP
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case -16:// GO DOWN
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD;
                        break;
                }
                break;

            case EAST:
                switch((prevByte-byte))
                {
                    case -1:
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case 1:
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case 16:
                        Movements[moveCounter++] = TURN_LEFT;
                        turnLeft();
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case -16:
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD;
                        break;
                }
                break;

            case SOUTH:
                switch((prevByte-byte))
                {
                    case -1:
                        Movements[moveCounter++] = TURN_LEFT;
                        turnLeft();
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case 1:
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD; 
                        break;

                    case 16:
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD; 
                        break;

                    case -16: //DOWN
                        Movements[moveCounter++] = FORWARD;
                        break;
                }
                break;

            case WEST:
                switch((prevByte-byte))
                {
                    case -1:
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case 1:
                        Movements[moveCounter++] = FORWARD;
                        break;

                    case 16:
                        Movements[moveCounter++] = TURN_RIGHT;
                        turnRight();
                        Movements[moveCounter++] = FORWARD;                     
                        break;

                    case -16:
                        Movements[moveCounter++] = TURN_LEFT;
                        turnLeft();
                        Movements[moveCounter++] = FORWARD; 
                        break;
                }
                break;
        }

        prevRow = row;
        prevCol = col;
        prevByte = byte;
    }

    Movements[moveCounter++] = HALT;
}



void calcFlood()
{
    //THIS IS WHERE WE SET THE DESTINATION AND START VALUES; //OR IN THE HEADER... WHO CARES?
    // IF this cond is true, then the mouse begins with the REST of the maze on its right and is facing north
    if(false)  // if pin != 1
    {
        orientation = 0;
        startRow = 15;
        startCol = 0;
    }
    else
    {
        orientation = 0;
        startRow = 15;
        startCol = 15;

    }

    maze1F[startRow][startCol] = 0;

    
    while(maze1F[destRow][destCol] == -1)
    {
        floodStep();
    }

    findPath();

    createDirections();
}