C Programming - Battleship Program - How to prevent ships from overlapping?

Question

I've created a program where I can randomly position two ships, with random orientation (horizontal or vertical), within a 2D array's borders.

The only problem that I'm facing is trying to prevent the ships from overlapping.

Here's a snippet from my code:

for ( row = 0; row < SIZE; row++ )
{
    printf( "%c | ", a++ );

    for ( column = 0; column < SIZE; column++ )
    {
        board[row][column] = ' ';

        for ( i = 0; i < 4; i++ )
        {
            if ( battleship[i].column == column )
            {
                if ( battleship[i].row == row )
                {
                    board[row][column] = 'B';
                }
            }
        }

        for ( i = 0; i < 5; i++ )
        {
            if ( carrier[i].column == column )
            {
                if ( carrier[i].row == row )
                {
                    board[row][column] = 'A';
                }
            }
        }

        printf( "%c ", board[row][column] );
    }

    printf( "|\n" );
}

How can I check to see if a ship is already there, and if there is, restart the loop from the beginning, clearing the existing values?

Answer 1

You are decreasing the efficiency of your code by going through each point on the board and then checking if that point on the board corresponds to the 4 or 5 points of the battle ship or carrier.

Why not just fill the board with empty space characters ' '. Then loop through your battle ship and carrier objects and check to see if the points on the board that the battle ship or carrier are to occupy are all empty spaces ' ' or not. If what they are to occupy are all empty spaces ' ', then it collides with nothing and you can change the board points to either 'A' or 'B' accordingly. If it does collide you can randomly generate that ships position and check again.

Answer 2

Wouldn't the simplest solution be to create a function that checks the current location to see if it is empty or not? Perhaps bool isEmpty() where you check the board to determine if the space you are inputting into is in fact empty or if there is a character residing there? the complexity is to check the board and not the 'ships length' against each other.

EDIT: This is exactly the same answer to David Pisani.

Answer 3

It would be better if you had distinct routines like

clear_board
place_ships
init_ships

clear_board will just set all the cells to space

place_ships will go through the battleship array and place the Bs. Then it will go through the carrier array and place the As.

Your question is about init_ships. It is similar to a card shuffling algorithm. Say your grid is never more than 64Kx64K.

int possible[SIZ * SIZ], ix, ship, empty;
for (ix = 0; ix < SIZ * SIZ; ++ix)
    possible[ix] = ix;

// Allocate the battleships
empty = SIZ * SIZ;
for (ship = 0; ship < MAXBATTLESHIPS; ++ship)
{
    ix = rand() % empty;   // Not the best way - this is just an example
    battleship[ship].column = possible[ix] % SIZ;
    battleship[ship].rw = possible[ix] / SIZ;
    if (ix != empty - 1)
    {
        possible[ix] = possible[empty - 1];
    }
    --empty;
}

Do the same for carriers