#include <cstdio>
#include <iostream>
#include <windows.h>
#include <ctime>

using namespace std;

#define ROW 10
#define COL 10

// The size of each type of ship
#define S_CARRIER 5
#define S_BATTLESHIP 4
#define S_DESTROYER 3
#define S_SUBMARINE 3
#define S_PATROLBOAT 2

#define BOATCOUNT 5

#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4

// Defines for the deck in ai_attack_random();
#define D_ROW 0
#define D_COL 1
#define D_SCORE 2
#define D_SIZE 3 // col size in the 2d array

#define AI_ACCURACY_ADJACENT 50 // Modifier defining how likely the AI is to attack spaces adjacent to hits.  0 = never, 34 + 4 * AI_ACCURACY_DIAGONAL = always
#define AI_ACCURACY_DIAGONAL 8 // Modifier that tweaks accuracy of AI attacking spaces adjacent to hits. 0 = inaccurate, AI_ACCURACY_ADJACENT / 4 makes AI dumb as a brick

enum hit {
  BLANK = ' ',
  MISS = '*',
  HIT = 'x',
  CARRIER = 'C',
  BATTLESHIP = 'B',
  DESTROYER = 'D',
  SUBMARINE = 'S',
  PATROLBOAT = 'P'
};

// Various prototypes for the functions
void welcome_display();
bool play();

void player_populate(hit players_board_def[ROW][COL]);
void boat_check(hit players_board_def[ROW][COL], int boat_type);

void board_display(hit board[ROW][COL]);
void board_display(hit board[ROW][COL], const hit ref[ROW][COL]);

bool is_sunk(hit boat, hit board[ROW][COL], const hit ref[ROW][COL]);
bool is_game_over(hit board[ROW][COL], const hit ref[ROW][COL]);

int hit2space(int space);
int hit2string(int space);

void ai_attack(hit board[ROW][COL], int &x, int &y);
void ai_attack_random(hit board[ROW][COL], int &col, int &row, int boats[BOATCOUNT], int boatsize);
int ai_calculate_score(hit board[ROW][COL], int r, int c, const int boats[BOATCOUNT], const int boatsize);
void ai_sort_deck(int scores[][D_SIZE], int rows);

void player_attack(const hit computer_const_board_ref[ROW][COL], hit player_board_off[ROW][COL], int &r, int &c);
void process_attack_off(hit offense[ROW][COL], const hit reference[ROW][COL], int r, int c);
void process_attack_def(hit defense[ROW][COL], const hit reference[ROW][COL], int r, int c);

void placeBoat(hit board[][COL]);
void direction(hit board[][COL],int randDirection,int x, int y,int limit, hit boatType);
bool checkBlank(hit board[][COL], const int x, const int y, const int limit, int direction);

/*********************************************************************************************************
Purpose: This is the main function that continues while the user wants to start a new game and exits when
the user no longer wants to play anymore games with our awesome AI

Input: Nothing

Returns: Nothing
*********************************************************************************************************/
int main()
{
    srand(time(NULL));
    bool valid=true;

    // Clears the screen then displays a graphic for the startup of the program
    welcome_display();

    do{
        valid = play();
    }while (valid);

    printf("\n ");
    system("pause");
}

/*********************************************************************************************************
Purpose: This is where all of the gameplay happens, from getting the user to fill their board to the computer
filling its board. To then playing the game until a winner is declared.

Input: Nothing

Returns: new_game - This determines whether or not the user wants to start a new game
*********************************************************************************************************/
bool play(){

    bool valid;
    bool new_game;
    char choice;
    int x=0;
    int r, c;
    bool computer = false, player=false;

    // For the players own board
    hit player_board_def[ROW][COL];
    hit computer_board_def[ROW][COL];

    // Invisible reference board keeping track of boat locations... ((Should be const))
    hit player_const_board_ref[ROW][COL];
    hit computer_const_board_ref[ROW][COL];

    // For the board the players will be attacking
    hit player_board_off[ROW][COL];
    hit computer_board_off[ROW][COL];

    for(int i = 0; i < ROW; i++)
           for(int j = 0; j < COL; j++)
               player_board_def[i][j] = computer_board_def[i][j] = player_const_board_ref[i][j] = computer_const_board_ref[i][j] = player_board_off[i][j] = computer_board_off[i][j] = BLANK;

    player_populate(player_board_def);
    printf("\nYour board is...\n");
    board_display(player_board_def, player_const_board_ref);

    printf("\n\n The computer players 'random' board is... \n ");
    placeBoat(computer_board_def);
    board_display(computer_board_def);

    system("pause");
    system("cls");

    // Assume all boards are set at this point so copy said boards
    for(int i = 0; i < ROW; i++)
        for(int j = 0; j < COL; j++){
        player_const_board_ref[i][j] = player_board_def[i][j];
        computer_const_board_ref[i][j] = computer_board_def[i][j];
        }

    do{
        ai_attack(computer_board_off, c, r); // Get coordinates to attack
        process_attack_off(computer_board_off, player_const_board_ref, r, c); // Attack on offensive board
        process_attack_def(player_board_def, player_const_board_ref, r, c); // Attack on defensive board
        printf("\n AI has attacked %c%d\n", c+'A', r);
        if(is_sunk(player_board_ref[r][c], player_board_def, player_const_board_ref))
            printf("\n AI has sunk %s!", hit2string((int) player_const_board_ref[r][c]));

        printf("\n Human player's board...\n");
        board_display(player_board_def, player_const_board_ref);
        computer = is_game_over(player_board_def, player_const_board_ref); // Make sure computer hasn't already won

        printf("\n Computer player's board...\n");
        board_display(player_board_off);

        if(!computer){
            player_attack(computer_const_board_ref, player_board_off, r, c); // Get coordinates to attack
            process_attack_off(player_board_off, computer_const_board_ref, r, c); // Attack on offensive board
            process_attack_def(computer_board_def, computer_const_board_ref, r, c); // Attack on defensive board

            // printf(" Human has attacked %c%d\n", c+'A', r);
            player = is_game_over(computer_board_def, computer_const_board_ref); // Make sure player hasn't already won
        }

        system("cls");
    }while (!player && !computer); // Exit when someone wins

    printf("\n GAME OVER. %s player won!\n", computer ? "Computer" : "Human");

    board_display(player_board_off);
    board_display(computer_board_def);

    // This is just to ask if you want to make a new game or not. Based on that it will start a new game or quit
    // This can be put in a separate function if needed later...
    do{
        printf("\n\n Do you want to start a new game? (y/n): ");
        scanf("%c", &choice);
        fflush(stdin);
        switch (toupper(choice)){
            case 'Y':
                x=1;
                new_game=true;
                break;
            case 'N':
                x=2;
                new_game=false;
                break;
            default:
                printf("\n\n Incorrect option entered, please choose again\n\n");
                x=3;
        }
    }while (x==3);
    return (new_game);
}

/*********************************************************************************************************
Purpose: Process an attack on the offensive board.  Translate sinks into boat types so the player/computer
        can figure out what type of boat he just sunk.

Input:  hit offense[ROW][COL]                   offense board to modify
                const hit reference[ROW][COL]   reference board to check for ships
                int r                                                   Row to aim at
                int c                                                   Column to aim at

Returns: Nothing
*********************************************************************************************************/
void process_attack_off(hit offense[ROW][COL], const hit reference[ROW][COL], int r, int c)
{
        if(reference[r][c] != BLANK)
        {
                offense[r][c] = HIT;
                if(is_sunk(reference[r][c], offense, reference))
                        for(int i = 0; i < ROW; i++)
                                for(int j = 0; j < COL; j++)
                                        if(reference[i][j] == reference[r][c])
                                                offense[i][j] = reference[r][c];
        }
        else
        {
                offense[r][c] = MISS;
        }
}

/*********************************************************************************************************
Purpose: Process an attack on the defensive board, add hits when needed and misses where necessary.  DO
        NOT translate sinks.

Input:  hit defense[ROW][COL]                   defensive board to modify
                const hit reference[ROW][COL]   reference board to check for ships
                int r                                                   Row to aim at
                int c                                                   Column to aim at

Returns: Nothing
*********************************************************************************************************/
void process_attack_def(hit defense[ROW][COL], const hit reference[ROW][COL], int r, int c)
{
        // This tests if the coordinate entered by the user is a ship piece on the computers board, if it is then
        // we mark it as a hit. If it equals a blank spot on the computers board then it equals a miss.
        if (reference[r][c] != BLANK)
        defense[r][c] = HIT;
    else
        defense[r][c] = MISS;
}

/*********************************************************************************************************
Purpose: This function simply grabs input from the user for the coordinates they wish to attack

Input:  const hit computer_const_board_ref[ROW][COL], hit player_board_off[ROW][COL], int &r, int &c

Returns: Nothing
*********************************************************************************************************/
void player_attack(const hit computer_const_board_ref[ROW][COL], hit player_board_off[ROW][COL], int &r, int &c){

    char coord[3]={0};
    char tchar;
    bool valid;


    do{
        do{
            valid = true;
            printf("\n Enter the coordinate you want to attack: ");
                fgets(coord, 3, stdin);
                fflush(stdin);
                strupr(coord);
                if(!isalpha(coord[0])){
                        tchar = coord[0];
                        coord[0] = coord[1];
                        coord[1] = tchar;
                }
                if ((coord[0] < 'A' || coord[0] > 'J') || (coord[1] <'0' || coord[1] >'9')){
                printf("\n Incorrect coordinate entered. Please choose again.\n");
                valid = false;
            }else
                valid = true;
        }while (!valid);

        coord[0] -= 'A';
        coord[1] -= '0';

        // This checks to make sure the spot the user choose is actually a blank spot so that way they
        // cannot attack the same spot twice.
        if (player_board_off[coord[1]][coord[0]] != BLANK){
            printf("\n That coordinate has already been attacked. Please choose again.\n");
            valid = false;
        }

        }while (!valid);

    printf(" You are attacking: %c%d\n", coord[0] + 'A', coord[1]);
    r = coord[1];
    c = coord[0];
}

/*********************************************************************************************************
Purpose: This is to have the player choose which boat they want to place and then proceed to
another function that based on the boat choosen will ask for coordinates and valid them. This continues
until all boats have been placed.

Input: hit board[ROW][COL]

Returns: Nothing
*********************************************************************************************************/
void player_populate(hit player_board_def[ROW][COL]){

    int boattypes[5] = { CARRIER, BATTLESHIP, DESTROYER, SUBMARINE, PATROLBOAT };
    bool boatplaced[5] = { false } ;
    int boats = 0;
    int choice;
    bool valid;

    printf("\n");

    do{
        do{
            valid = true;
            board_display(player_board_def);
            printf("\n 1) Aircraft Carrier\n 2) Battleship\n 3) Destroyer\n 4) Submarine\n 5) Patrol Boat\n\n");
            printf(" Choose which ship you want to place: ");
            scanf("%d", &choice);
            fflush(stdin);
            if (choice > 0 && choice < 6){
                valid = true;
            }else{
                printf("\n Incorrect option entered. Please choose again.\n\n");
                valid = false;
            }
        }while (!valid);

        choice--;
        if(!boatplaced[choice]){ // Keeping track of which boats we have placed
            boat_check(player_board_def, boattypes[choice]);
            boats++; // Number of boats we have placed so far, when 5 stop placing boats.
            boatplaced[choice] = true;
        }else{
            printf("\n You have already placed that ship. Please choose a different ship.\n\n ");
            system("pause");
        }
        system("cls");
    }while (boats < 5);
}

/*********************************************************************************************************
Purpose: This is to have the player choose which boat they want to place and then proceed to
another function that based on the boat choosen will ask for coordinates and valid them. This continues
until all boats have been placed.

Input: hit player_board_def[ROW][COL]

Returns: Nothing
*********************************************************************************************************/
void boat_check(hit player_board_def[ROW][COL], int boat_type)
{
        char coord1[3]={0};
    char coord2[3]={0};
    char tchar;
    bool valid;

    do{
                valid = true;

                // Input & validation for the start coordinates from the user
                do{
                        printf("\n Enter first coordinate: ");
                        fgets(coord1, 3, stdin);
                        fflush(stdin);
                        strupr(coord1);
                        if(!isalpha(coord1[0])){
                                tchar = coord1[0];
                                coord1[0] = coord1[1];
                                coord1[1] = tchar;
                        }
        }while ((coord1[0] < 'A' || coord1[0] > 'J') && (coord1[0] <'0' || coord1[0] >'9'));

        // Input & validation for the end coordinates from the user
        do{
                        printf(" Enter second coordinate: ");
            fgets(coord2, 3, stdin);
            fflush(stdin);
            strupr(coord2);
            if(!isalpha(coord2[0])){
                                tchar = coord2[0];
                coord2[0] = coord2[1];
                coord2[1] = tchar;
                        }
                }while ((coord2[1] < 'A' || coord2[1] > 'J') && (coord2[1] <'0' || coord2[1] >'9'));

        // This changes the chars in the arrays to an actual number so that we can use them to interface
        // with the location in the array it corrisponds to.
        coord1[0] -= 'A';
        coord1[1] -= '0';
        coord2[0] -= 'A';
        coord2[1] -= '0';

        // This checks the inputted numbers to see if they are valid by one of the element pairs being equal
        // to each other. Such as if you have A2 & D2 as the coordinates the second element in both arrays
        // are the same or if you have A2 & A5, the 'A's are the same (This verifies that the start & end points
        // are truly in a horizontal or vertical line)

        if ((coord1[0]==coord2[0] && coord1[1]!=coord2[1]) || (coord1[0]!=coord2[0] && coord1[1]==coord2[1]))
                {
                        for(int i = 0; i < 2; i++)
            {
                                if(coord1[i] > coord2[i]) // Exchange coordinates to make 2nd larger than 1st
                {
                                        for(int j = 0; j < 2; j++)
                    {
                                                tchar = coord1[j];
                        coord1[j] = coord2[j];
                        coord2[j] = tchar;
                                        }
                                }
            }

            // We have already guaranteed that at least 1 is the same, so we can MATHS to divine the boat size and determine its valid
            if((coord2[0] - coord1[0]) + (coord2[1] - coord1[1]) + 1 != hit2space(boat_type))
                                valid = false;

                        for(int i = coord1[0]; i <= coord2[0]; i++) // Checking horizontal
                                if(player_board_def[coord1[1]][i] != BLANK)
                                        valid = false;

                        for(int i = coord1[1]; i <= coord2[1]; i++) // Checking vertical
                                if(player_board_def[i][coord1[0]] != BLANK)
                                        valid = false;

                }
                // If none of the previous checks have not been met then the coordinates cannot be
        // correct therefore we must ask again
        else
        {
                        valid = false;
                }
        if (!valid)
                printf("\n Incorrect coordinates entered, please choose again\n");
        } while (!valid);

    for(int i = coord1[0]; i <= coord2[0]; i++)
                player_board_def[coord1[1]][i] = (hit) boat_type; // Or respective boat type

        for(int i = coord1[1]; i <= coord2[1]; i++)
                player_board_def[i][coord1[0]] = (hit) boat_type; // Or respective boat type
}


/*********************************************************************************************************
Purpose: This function simply prints out any array it is given in the board format that the battleship
game is supposed to be displayed in

Input: hit board[ROW][COL]

Returns: Nothing
*********************************************************************************************************/
void board_display(hit board[ROW][COL]){

    char letters_array[11]={' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};

    // This is for displaying the first line of dashes
    for (int z=0; z < 4*COL+4; z++){
        printf("-");
    }
    printf("\n");

    // This is for displaying A-J
    for (int x=0; x < 11; x++){
        printf(" %c |", letters_array[x]);
    }
    printf("\n");

    // These for loops are for making the board dynamically based on the #define values and displays
    // what is in the array in the board format accordingly
    for (int x=0, y=0; x < ROW; x++, y++){
        for (int z=0; z < 4*COL+4; z++){
           printf("-");
        }
        printf("\n");

        // This is for displaying 0-9
        printf(" %d |", y);

        // This is for displaying the contents of the element of the array we are currently at
        for (int y=0; y < COL; y++){
            printf(" %c |", board[x][y]);
        }
        printf("\n");
    }

    // This is for displaying the last line of dashes
    for (int z=0; z < 4*COL+4; z++){
        printf("-");
    }
    printf("\n");
}

/*********************************************************************************************************
Purpose: This is the overloaded version of the function that prints out any array it is given in the board
format that the battleship game is supposed to be displayed in. This functions takes two boards

Input: hit board[ROW][COL] & hit ref[ROW][COL]

Returns: Nothing
*********************************************************************************************************/
void board_display(hit board[ROW][COL], const hit ref[ROW][COL]){

    char letters_array[11]={' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};

    // This is for displaying the first line of dashes
    for (int z=0; z < 4*COL+4; z++){
        printf("-");
    }
    printf("\n");

    // This is for displaying A-J
    for (int x=0; x < 11; x++){
        printf(" %c |", letters_array[x]);
    }
    printf("\n");

    // These for loops are for making the board dynamically based on the #define values and displays
    // what is in the array in the board format accordingly
    for (int x=0, y=0; x < ROW; x++, y++){
        for (int z=0; z < 4*COL+4; z++){
           printf("-");
        }
        printf("\n");

        // This is for displaying 0-9
        printf(" %d |", y);

        // This is for displaying the contents of the element of the array we are currently at
        for (int y=0; y < COL; y++){
            printf(" %c |", is_sunk(ref[x][y], board, ref) ? tolower(ref[x][y]) : board[x][y]);
        }
        printf("\n");
    }

    // This is for displaying the last line of dashes
    for (int z=0; z < 4*COL+4; z++){
        printf("-");
    }
    printf("\n");
}

/*********************************************************************************************************
Purpose: Determine whether or not all the boats on a board have been sunk

Input:  hit board[ROW][COL]             Board to look for sunken boats
                const hit ref[ROW][COL] Reference board for ship placement

Returns: bool                                   True if all boats are sunk, false otherwise.
*********************************************************************************************************/
bool is_game_over(hit board[ROW][COL], const hit ref[ROW][COL])
{
        hit boats[BOATCOUNT] = { CARRIER, BATTLESHIP, DESTROYER, SUBMARINE, PATROLBOAT };
        int sinks = BOATCOUNT;

        for(int i = 0; i < BOATCOUNT; i++)
                if(is_sunk(boats[i], board, ref))
                        sinks--;
        return !sinks;
}

/*********************************************************************************************************
Purpose: Function to determine if a single boat has sunk already

Input:  hit boat                                Boat to check if has sunk
                hit board[ROW][COL]             Gameboard to check
                const hit ref[ROW][COL] Reference board to refer to for boat placement

Returns: bool                                   True if boat has sunk, false otherwise
*********************************************************************************************************/
bool is_sunk(hit boat, hit board[ROW][COL], const hit ref[ROW][COL])
{
        int size = hit2space(boat);
        if(!size)
                return false;

        for(int i = 0; i < ROW; i++)
                for(int j = 0; j < COL; j++)
                        if(ref[i][j] == boat && board[i][j] == HIT)
                                size--;
        return (!size);
}

/*********************************************************************************************************
Purpose: Returns the number of spaces that the passed boat will take up.  A glorified switch statement, but
        used everywhere.

Input:  int space               type of boat to check

Returns: int            Number of spaces that the ship will take up, counting from 1.  EG. Carrier would return 5
*********************************************************************************************************/
int hit2string(int space)
{
        switch(space)
        {
                case CARRIER:           return S_CARRIER;
                case BATTLESHIP:        return S_BATTLESHIP;
                case DESTROYER:         return S_DESTROYER;
                case SUBMARINE:         return S_SUBMARINE;
                case PATROLBOAT:        return S_PATROLBOAT;
                default:                        return 0;
    }
}

/*********************************************************************************************************
Purpose: Returns the number of spaces that the passed boat will take up.  A glorified switch statement, but
        used everywhere.

Input:  int space               type of boat to check

Returns: int            Number of spaces that the ship will take up, counting from 1.  EG. Carrier would return 5
*********************************************************************************************************/
char *hit2string(int space)
{
        switch(space)
        {
                case CARRIER:                   return "Carrier";
                case BATTLESHIP:                return "Battleship";
                case DESTROYER:                 return "Destroyer";
                case SUBMARINE:                 return "Submarine";
                case PATROLBOAT:                return "Patrol Boat";
                case MISS:                              return "Miss";
                case HIT:                               return "Hit";
                case BLANK:                             return "BLANK";
        }
}

/*********************************************************************************************************
Purpose: This just prints out the first screen to display with a cool ascii graphic for the player to see

Input: Nothing

Returns: Nothing
*********************************************************************************************************/
void welcome_display(){

    // This just gives time for the user so they can fullscreen the command prompt to be able to see
    // the game without scrolling up & down
    printf("\n Loading; Please wait");
    for (int x=0; x<3; x++){
        printf(". ");
        Sleep(1150);
    }
    system("cls");

    // This is fairly obvious that this is the title and graphic that is displayed when you start the program
    printf("\n");
    printf("\t\t\t\tWelcome to\n");
    printf("\t\t\t     ================\n");
    printf("   ____              __    __    ___                   __                    \n");
    printf("  /\\  _`\\           /\\ \\__/\\ \\__/\\_ \\                 /\\ \\      __           \n");
    printf("  \\ \\ \\_\\ \\     __  \\ \\ ,_\\ \\ ,_\\//\\ \\      __    ____\\ \\ \\___ /\\_\\  _____   \n");
    printf("   \\ \\  _ <'  /'__`\\ \\ \\ \\/\\ \\ \\/ \\ \\ \\   /'__`\\ /',__\\\\ \\  _ `\\/\\ \\/\\ '__`\\ \n");
    printf("    \\ \\ \\_\\ \\/\\ \\_\\.\\_\\ \\ \\_\\ \\ \\_ \\_\\ \\_/\\  __//\\__, `\\\\ \\ \\ \\ \\ \\ \\ \\ \\_\\ \\\n");
    printf("     \\ \\____/\\ \\__/.\\_\\\\ \\__\\\\ \\__\\/\\____\\ \\____\\/\\____/ \\ \\_\\ \\_\\ \\_\\ \\ ,__/\n");
    printf("      \\/___/  \\/__/\\/_/ \\/__/ \\/__/\\/____/\\/____/\\/___/   \\/_/\\/_/\\/_/\\ \\ \\/ \n");
    printf("                                                                       \\ \\_\\ \n");
    printf("   Developers:                                                          \\/_/ \n");
    printf("                                      #    _                                    ");
    printf("   Larry Ing                       _ # #  (.)\n");
    printf("   Luke Kontes               =====|_|#_#___|__                                  ");
    printf("   Erich Healy                _  |____________|  _                              ");
    printf("   Mark de Guzman       =====|.| | .  .  .  . | |.|====                         ");
    printf("                       _ .---------------------------. _                        ");
    printf("                 =====|.||  .  .  .  .  .  .  .  .   ||.|====\n");
    printf("   \\---------------------'                           `--------------/\n");
    printf("    \\ .  .  .  .           .  .  .  .        .  .  .  .     USS-42 /\n");
    printf("     \\          .  .  .  .           .  .  .           .  .  .  . /\n");
    printf("      \\__________________________________________________________/\n");
    printf("  wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww\n");
    printf(" wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww\n");
    printf("   wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww \n");
    printf("\n");
    printf("\n ");

    // Possibly use a sleep instead here...
    system("pause");
    system("cls");
}

/*********************************************************************************************************
Purpose: This is the main attacking function for the AI.  It gathers information about the board and passes it
        off to the other AI functions.  Coordinates to attack are passed by reference.

Input:  hit board[ROW][COL]             Gameboard that AI will be attacking
                int col                                 Column passed by reference that the AI will decide to attack
                int row                                 Row passed by reference that the AI will decide to attack

Returns: Nothing
*********************************************************************************************************/
void ai_attack(hit board[ROW][COL], int &col, int &row)
{
        int boatlist[BOATCOUNT] = { CARRIER, BATTLESHIP, DESTROYER, SUBMARINE, PATROLBOAT };
        int boatsize = BOATCOUNT;
        int i;

        // REMEMBER: col and row are passed by reference
        for(int r = 0; r < ROW; r++)
        {
                for(int c = 0; c < COL; c++)
                {
                        if(board[r][c] != MISS && board[r][c] != BLANK) // Boat is an actual boat and needs to be removed from the boatlist
                        {
                                for(i = 0; i < BOATCOUNT && board[r][c] != boatlist[i]; i++);
                                if(i != BOATCOUNT) // Otherwise this boat has already been removed
                                {
                                        for(; i < BOATCOUNT - 1; i++)
                                                boatlist[i] = boatlist[i+1]; // Remove the boat from the list
                                        boatsize--;
                                }
                        }
                }
        }
        for(i = 0; i < boatsize; i++) // Convert boatlist to sizes
                boatlist[i] = hit2space(boatlist[i]);
        ai_attack_random(board, col, row, boatlist, boatsize);
}

/*********************************************************************************************************
Purpose: This tries to pick the best space to attack on the board using a weighted system

Input:  hit board[ROW][COL]             Gameboard that AI will be attacking
                int col                                 Column passed by reference that the AI will decide to attack
                int row                                 Row passed by reference that the AI will decide to attack
                int boats[BOATCOUNT]    Array of boat sizes that still have not been sunk yet
                int boatsize                    Size of the boats array.

Returns: Nothing
*********************************************************************************************************/
void ai_attack_random(hit board[ROW][COL], int &col, int &row, int boats[BOATCOUNT], int boatsize)
{
        // The theory behind the AI here is thus:
        // create a 2D deck for each space in the array holding coordinates and the score for that space
        // The score represents how many variations of each type of remaining battleship can intercept that space
        // Such that spaces without many hits nearby will have a higher weight than those adjacent to the edge of the board
        // or next to miss markers.
        // The deck is then sorted according to score and a random space from the list of top scorers is chosen and the AI targets that

        // TODO:
        // As it stands, the AI here is too smart and thus too predictable.  need to figure out a way to make it slightly more random.
        // Unless thats unneccesary...
        int deck[ROW*COL][D_SIZE];
        int decksize = 0;
        int target, x;

        for(int i = 0; i < ROW; i++) // populate the deck and generate scores
        {
                for(int j = 0; j < COL; j++)
                {
                        if(board[i][j] == BLANK)
                        {
                                deck[decksize][D_ROW] = i;
                                deck[decksize][D_COL] = j;
                                deck[decksize][D_SCORE] = ai_calculate_score(board, i, j, boats, boatsize);
                                decksize++;
                        }
                }
        }

        ai_sort_deck(deck, decksize - 1); // Sort the deck based on scores
        for(target = 0, x = deck[0][D_SCORE]; x == deck[target][D_SCORE] && target < decksize; target++); // find the range of possible targets
        target = rand() % target; // Pick the target to use
        col = deck[target][D_COL];
        row = deck[target][D_ROW];
}

/*********************************************************************************************************
Purpose: This calculates the weight score of a particular board space and returns that score.  Score is
        based on how many possible ship combinations can legally overlap that space.  It then adds or subtracts
        a modifier to the score based on adjacent and diagonal hits.

Input:  hit board[ROW][COL]             Main gameboard that it must calculate
                int r                                   Row number to check
                int c                                   Column number to check
                int boats[BOATCOUNT]    List of boats to check against space
                int boatsize                    Size of boats array

Returns: int    Weight score for that particular space
*********************************************************************************************************/
int ai_calculate_score(hit board[ROW][COL], int r, int c, const int boats[BOATCOUNT], const int boatsize)
{
        // Scoring algorithm works like such:  add 1 to the weight of the space for each section of a ship it can contain
        // both horizontaly and verticaly
        // Thus, x_?__x (x = miss, _ = blank, ? = coordinates) would have a score of:
        //              +2 for patrol boat
        //              +2 for sub and destroyer apiece
        //              +1 for battleship since there is only one legal configuration in this section that would store the ? within the battleship
        //              +0 for carrier since it cannot fit between those misses
        // Additionally, score is only added for ships that have not yet been sunk, as defined by int boats.
        // By this method, each space has a theoretical score limit of 34

        // Modifiers:
        // Spaces will be modified based on their proximity to a hit.  such that spaces directly adjacent to hits will recieve extra points and
        // spaces diagonally adjacent to hits will be demoted points
        int score = 0;
        int startpos, endpos;

        // Calculate the horizontal.
        for(int boat = 0; boat < BOATCOUNT; boat++)
        {
                for(startpos = c; startpos < COL - 1 && (board[r][startpos] == BLANK || board[r][startpos] == HIT) && startpos - c + 1 < boats[boat]; startpos++); // Move the start counter all the way to the right
                for(endpos = c; endpos >= 0 && (board[r][endpos] == BLANK || board[r][endpos] == HIT) && startpos - endpos + 1 < boats[boat]; endpos--); // Move end counter to the left to encompase size of boat
                if(startpos - endpos + 1 == boats[boat]) // make sure it can actually hold the boat before continuing
                        for(; endpos >= 0 && startpos >= c && (board[r][endpos] == BLANK || board[r][endpos] == HIT) && (board[r][startpos] == BLANK || board[r][startpos] == HIT); startpos--, endpos--)
                                score++; // Move counters to the left and add one to the score for each successful move
        }

        // Now the vertical, mainly the same thing
        for(int boat = 0; boat < BOATCOUNT; boat++)
        {
                for(startpos = r; startpos < ROW - 1 && (board[startpos][c] == BLANK || board[startpos][c] == HIT) && startpos - r + 1 < boats[boat]; startpos++); // Move the start counter all the way to the right
                for(endpos = r; endpos >= 0 && (board[endpos][c] == BLANK || board[endpos][c] == HIT) && startpos - endpos + 1 < boats[boat]; endpos--); // Move end counter to the left to encompase size of boat
                if(startpos - endpos + 1 == boats[boat]) // make sure it can actually hold the boat before continuing
                        for(; endpos >= 0 && startpos >= r && (board[endpos][c] == BLANK || board[endpos][c] == HIT) && (board[startpos][c] == BLANK || board[startpos][c] == HIT); startpos--, endpos--)
                                score++; // Move counters to the left and add one to the score for each successful move
        }

        // Process directly adjacent modifiers
        if(r - 1 >= 0  && board[r-1][c] == HIT) score += AI_ACCURACY_ADJACENT;
        if(r + 1 < ROW && board[r+1][c] == HIT) score += AI_ACCURACY_ADJACENT;
        if(c - 1 >= 0  && board[r][c-1] == HIT) score += AI_ACCURACY_ADJACENT;
        if(c + 1 < COL && board[r][c+1] == HIT) score += AI_ACCURACY_ADJACENT;

        // Process diagonally adjacent modifiers
        if(r - 1 >= 0 && c - 1 >= 0   && board[r-1][c-1] == HIT) score -= AI_ACCURACY_DIAGONAL;
        if(r + 1 < ROW && c - 1 >= 0  && board[r+1][c-1] == HIT) score -= AI_ACCURACY_DIAGONAL;
        if(r - 1 >= 0 && c + 1 < COL  && board[r-1][c+1] == HIT) score -= AI_ACCURACY_DIAGONAL;
        if(r + 1 < ROW && c + 1 < COL && board[r+1][c+1] == HIT) score -= AI_ACCURACY_DIAGONAL;

        return score;
}

/*********************************************************************************************************
Purpose: Sorting function for use in ai_attack_random.  Sorts a 2d array based on the third item in the
        second array.  Bubblesort style

Input:  hit scores[][D_SIZE]    2d array that it needs to sort
                int rows                                Size of scores array counting from zero

Returns: Nothing
*********************************************************************************************************/
void ai_sort_deck(int scores[][D_SIZE], int rows) // munged bubblesort
{
        int temp, index;

        for(; rows > 0; rows--)
        {
                for(index = 0; index < rows; index++)
                {
                        if(scores[index][D_SCORE] < scores[index+1][D_SCORE])
                        {
                                for(int i = 0; i < D_SIZE; i++)
                                {
                                        temp = scores[index+1][i];
                                        scores[index+1][i] = scores[index][i];
                                        scores[index][i] = temp;
                                }
                        }
                }
        }
}

/************************************************************
Name: placementBoat
Purpose: This function uses a switch-case statment to place the carrier, battleship, destroyer, submarine, and patrol boat, in that order.  It places them by calling the direction function.
Input: hit board[][COL] - This is the board that will contain all the AI's boats.
          int x - This is the randomly generated X cordinate.
          int y - This is the randomly generated Y cordinate.  Together with the random X cordinate, these will serve as teh starting point for all points.
Output: NA.
************************************************************/
void placeBoat(hit board[][COL]){
        int x, y;
        int randDirection;
        hit boats[BOATCOUNT] = { CARRIER, BATTLESHIP, DESTROYER, SUBMARINE, PATROLBOAT};
        for(int i = 0; i < BOATCOUNT; i++)
        {
                do{
                randDirection = (rand()%4)+1;
                        x = rand()%ROW;
                        y = rand()%COL;
                }while( !checkBlank(board,x,y,hit2space((int) boats[i]),randDirection) );
                direction(board,randDirection,x,y,hit2space((int) boats[i]),boats[i]);
        }
}

/************************************************************
Name: direction
Purpose: Based upon a randomly generated number, this function will decide which direction to place the remaining points for a said boat.
Input: hit board[][COL] - This is the board that will contain all the AI's boats.
          int x and int y - These are the basis upon which all other points will be place as explain in the previous function.
Output: NA.
************************************************************/
void direction(hit board[][COL],int randDirection,int x, int y,int limit, hit boatType){
        for(int i=0;i<limit;i++){
                if(randDirection==UP){
                        board[x][y-i] = boatType;
                }else if(randDirection == DOWN){  //If the direction is down this will be done.
                        board[x][y+i] = boatType;
                }else if(randDirection==RIGHT){
                        board[x-i][y] = boatType;
                }else{  //If the direction is left this will be done.
                        board[x+i][y] = boatType;
                }
    }
}

/************************************************************
Name: checkBlank
Purpose: This will check the spots that the Ai wishes to place the boat on an confirm it is able
Input: hit board[][COL] - This is the board that will contain all the AI's boats.
          int x and int y - These are the basis upon which all other points will be place as explain in the previous function.
          int direction - A randomly generated direction
Output: Returns true or false
************************************************************/
bool checkBlank(hit board[][COL], const int x, const int y, const int limit, int direction){
        int i;
        bool valid = true;

    switch (direction){
        case UP:
            for(i=0;i<limit;i++){
                if(y-limit < 0 || board[x][y-i] != BLANK) valid = false;
            }
        case DOWN:
            for(i=0;i<limit;i++){
                if(y+limit >= ROW || board[x][y+i] != BLANK) valid = false;
            }
        case RIGHT:
            for(i=0;i<limit;i++){
                if(x-limit < 0 || board[x-i][y] != BLANK) valid = false;
            }
        case LEFT:
            for(i=0;i<limit;i++){
                if(x+limit >= COL || board[x+i][y] != BLANK) valid = false;
            }
    }
        return valid;
}

/*
void say_qoute(){

        char *qoutes[] = {
                "Always in motion is the future...",
                "The force is strong with this one...",
                "The rumors of my death have been greatly exagerated",
                "All your base are belong to us",
                "May the force be with you.",
                "...Admiral, I want that ship - not excuses!",
                "There is a great disturbance in the Force",
                "We have a new enemy, the young Rebel who destroyed the Death Star.",
                "Impressive, most impressive. Obi-Wan has taught you well.",
                "There is no escape. Don't make me destroy you.",
                "You are beaten. It is useless to resist.",
                "I have you now!",
                "It's a trap!",
                "Don't underestimate the Force.",
                "I find your lack of faith disturbing.",
        "Man your ships... and may the Force be with you."
        }
        puts(qoutes[rand() % 5]);
}
*/