Sink the boat game (complex conditions issue)

[Pobunjenik]

Hi everyone!
So, I hereby hope to show that I've made progress in coding java (largely due to the help of this great community). I want to thank everyone for dealing with me (especially James). :)

The goal:
The code below is supposed to seed a layout of boats into a 2D array. This is part 1 of an excersize I've given myself - create code to seed boats horrizontally and vertically, boats must not collide, boats must not be out of bounds.

The issue:
Usually the layout comes out just fine. But sometimes, some boats are missing in length (the length 4 boat becomes a length 3 boat). This doesn't happen only on borders, but in the middle too.
I've tried seeding with a single length 5 boat, and it still happens.

The code:

package potapanjebrodova;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class PotapanjeBrodova {

    int[] ships = {4, 3, 3, 2, 2, 2};    
    char[][] table = new char[11][11];
    Random R = new Random();


    public static void main(String[] args) {

        PotapanjeBrodova PB = new PotapanjeBrodova();
        PB.makeEmpty();
        PB.seeding();
        PB.printTable();

    }

    public void seeding() {
        List<Integer> locationI = new ArrayList<>();
        List<Integer> locationJ = new ArrayList<>();
        boolean reappearingI = false;
        boolean ponavljanjeJ = false;
        int positionI;
        int positionJ;
        int direction;
        int shipLength;

        for (int i = 0; i < this.ships.length; i++) {
            direction = this.R.nextInt(2);
            shipLength = this.ships[i];
            // this DO WHILE will generate unique seeding coords for each ship
            do {
                positionI = this.R.nextInt(10) + 1;
                positionJ = this.R.nextInt(10) + 1;                

                for (int j = 0; j < locationI.toArray().length; j++) {
                    if (locationI.toArray()[j] == positionI) {
                        reappearingI = true;
                    } else {
                        reappearingI = false;
                    }
                }
                for (int j = 0; j < locationJ.toArray().length; j++) {
                    if (locationJ.toArray()[j] == positionI) {
                        ponavljanjeJ = true;
                    } else {
                        ponavljanjeJ = false;
                    }
                }

            } while (this.table[positionI][positionJ] != '_' && (reappearingI == false || ponavljanjeJ == false));           

            do {                
                switch (direction) {
                    case 0:
                        this.table[positionI][positionJ] = 'O';
                        locationI.add(positionI); // to prevent seeding in the same spot
                        if (positionI + this.ships[i] >= this.table.length) {
                            positionI--; // if end of table, change direction
                        } else {
                            positionI++;
                        }
                        break;
                    case 1:
                        this.table[positionI][positionJ] = 'O';
                        locationJ.add(positionJ); // to prevent seeding in the same spot
                        if (positionJ + this.ships[i] >= this.table.length) {
                            positionJ--; // if end of table, change direction
                        } else {
                            positionJ++;
                        }
                        break;
                }
                shipLength--;
            } while (shipLength != 0);
        }
    }

    public void makeEmpty() {
        for (int i = 0; i < this.table.length; i++) {
            for (int j = 0; j < this.table.length; j++) {
                this.table[i][j] = '_';
            }
        }
    }

    public void printTable() {
        for (int i = 0; i < this.table.length; i++) {
            for (int j = 0; j < this.table.length; j++) {
                System.out.print(" " + table[i][j]);
                if (j == this.table.length - 1) {
                    System.out.println();
                }
            }
        }
        System.out.println("X-X-X-X-X-X-X-X-X-X-X-X");
    }
}

PS
I'd like to hear comments on the way I code, what are my strong points, what should I improve, am I using bad logic?

Thanks,
Pob

[bguild]

Just looking at the code I believe I see several problems. On line 48 I suspect you are demonstrating one of the major problems with copy-and-paste code. I think you really want that line to say if(locationJ.toArray()[j] == positionJ). You should prefer using a private method instead of copying your code, because a private method gives a name to what you are doing which provides documentation, and it also means you only need to get it right once instead of twice.

Your entire loop between line 37 and line 56 seems doubtful. You are using a strategy of repeatedly choosing a random location and testing it for correctness until you finally find a position that you can use. That strategy has no guarantee that it will work; you might keep choosing bad positions forever. It would be better to generate a list of all possible positions for a ship and then randomly choose one of those.

Your condition for the while on line 56 is confusing:

this.table[positionI][positionJ] != '_' && (reappearingI == false || ponavljanjeJ == false)

I understand the first clause (this.table[positionI][positionJ] != '_') since you naturally want to keep looping as long as the choosen position is not empty, but then you introduce an additional requirement and that seems like it must be wrong. Surely when the position is occupied you absolutely must loop again; there can be no option of using that position for this ship, yet you are apparently willing to have two ships overlap if reappearingI and ponavljanjeJ.

In lines 63-67 and 72-76, you shouldn't be deciding which direction your ship will run each time through the loop. That can lead to the bow of your ship pointing left, then the rest of your ship proceeds to the right until it suddenly decides to turn around and start heading left again, building into the already constructed portion of your ship. In fact, this is guaranteed to happen when your ship gets near to the to the edges so that positionI or positionJ is too close to table.length.

I notice that you are using table.length for both the i dimension and the j dimension of table. This works as long as both dimensions are the same, but if you ever made them different your program would break. If you are going to bury a landmine like that, you should at least make a comment so people know what can make your program explode.

On lines 38-39, I notice that you are only choosing values for positionI and positionJ between 1 and 10, excluding 0, but I don't see 0 being excluded anywhere else in your program. I can't tell if that is deliberate.

It makes no sense to use locationI.toArray().length and locationI.toArray()[i] when locationI.size() and locationI.get(i) are easier to type, more conventional, cheaper, and have the same result. It would also be more conventional to use !reappearingI instead of reappearingI == false, but they would both do the same thing so it's not a real problem.

[Pobunjenik]

Thank you for your lengthy response! :)

You're absolutely right about line 48. I'll rework that test into a separate method.

I believe you're wrong for 37-56: the table is 10x10 (100 cells), and the ships will occupy 16 in total (4+3+3+2+2+2). This means every ship will always have a free location to be seeded into.
The two lists, locationJ and locationI only keep track of used cells, so that positionJ and positionI may never randomly generate the same number (even tho the chance is very small).

As for ponavljanjeJ in line 56, it's the same as reappearingI (just forgot to translate that variable). :D
Any ship will take 2 or more cells. Lists locationI/J keep track of those cells and booleans reappearingI/J will make the do while loop repeat until a unique set of never before used coordinations is generated.

I've noticed that myself in 63-67 and 72-76, hence the if condition:

                        if (positionI + this.ships[i] >= this.table.length) {
                            positionI--; // if end of table, change direction
                        } else {
                            positionI++;
                        }

Lets say I'm vertically seeding a length 4 ship from positionI 8. The maximum value for positionI is 10 (see line 10 in OP). This means my ship will be out of bounds for sure.
If the length of the ship plus the location (I for vertical, J for horizontal) are greater then the total size of the table, simply don't seed downwards (positionI++), seed the ship upwards (positionI--). This should be ok.

Both dimensions will forever be the same, I'm just rebuilding the old ship bombardment gam, which is traditionally played in a square table. However, I'll keep your suggestion in mind for future programs. :)

Again, you're absolutely right. I didn't even know those existed. :)

EDIT:
Upon fixing the copypasta mistake in line 49, the code still sometimes cuts some boat short.

[JamesCherrill]

Comments:
I looked quickly at that code and decided I didn't have time to try to understand it. It's just too complex & nested. IMHO that's a result of not breaking the app up into enough classes.
Read the rules of the game - the most common noun is "ship". So I would start with a Ship class

class Ship
   final startRow, endRow, legth, direction, charForDisplay
   noOfHits = 0;
   sunk = false;

Then the game board is obviously an array of Ship instances (or nulls).

Now it's easy to write a Ship method to check if any of the ship's squares are already occupied by anthor ship and if not, to add the Ship to the board. Finally we have a simple method to generate ships at random locations/directions and try them until one fits.

It's also going to make things lot easier when you want to know if a Ship has been sunk etc.

[bguild]

I believe you're wrong for 37-56: the table is 10x10 (100 cells), and the ships will occupy 16 in total (4+3+3+2+2+2). This means every ship will always have a free location to be seeded into.

Your table array is 11x11, which causes your printTable method to show an 11x11 grid to the user.

Your locationI and locationJ don't keep track of used cells exactly. You are probably being mislead by their misleading names, which illustrates why it is so important to name things appropriately. locationI is a list, not a location, and it stores all of the rows that have been used by vertical ships. Notice that if you arrange 3, 3, 2, and 2 vertically then you can easily occupy every row of a 10x10 board.

Also, remember that when you flip a coin you don't always get head, tail, head, tail; instead you will often get runs of repeated heads, or tails. Randomly generated locations on your board can repeatedly choose illegal positions for ships, especially as more of your board gets filled, and it could keep doing that forever. Your ship layout strategy could take minutes or hours to complete depending on your luck, and there's really no reason to rely on luck.

I expect that it is your mistaken logic in lines 63-67 and 72-76 that is causing boats to be cut short, unless you've fixed it, but that's the least of your problems.

[Pobunjenik]

Alright, I've finally understood all of what you guys have said, and I'm reworking the code.
I'll post the corrected version once I'm done correcting it. :D

Thanks again! :)

[kedxu]

As a newbie myself, I'm unsure whether this could be helpful, but I'll post it anyway:

Instead of placing the ships one-by-one, you could try

loop
{
    randomlyArrangeShips(); //this ignores previously placed ships

    if(count_occupied_tiles == number_of_tiles_there_should_be)
    {
        //there is no intersection of ships, so keep the layout
        break from loop;
    }
    else
    {
        //keep rearranging
    }
}

I understand that this loop could continue for a very long time until it finds a working layout, but:
(1) you could hard-code a working layout to use if it repeats too much, but this is obviously substandard
(2) in order to eliminate that problem, it would require a lot of work anyway, and would involve keeping track of all possible placement options for each ship and then selecting one of them

[Pobunjenik]

There are 100 tiles, and a FIXED number of ship tiles (16). The amount of combinations is... large.

Anyways, I've reworked parts of the code (mostly the conditions and probing for viable coordinates), and the newest code looks like so:

package potapanjebrodova;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class PotapanjeBrodova {

    int[] ships = {5, 4, 3, 3, 2, 2, 2};
    char[][] table = new char[10][10];
    Random R = new Random();

    public static void main(String[] args) {

        PotapanjeBrodova PB = new PotapanjeBrodova();
        PB.makeEmpty();
        PB.seeding();
        PB.printTable();

    }

    public void seeding() {
        List<Integer> locationsI = new ArrayList<>();
        List<Integer> locationsJ = new ArrayList<>();
        boolean reappearingI = false, reappearingJ = false;
        boolean fitsI, fitsJ;
        int positionI, positionJ, direction, shipLength;

        for (int i = 0; i < this.ships.length; i++) {
            direction = this.R.nextInt(2);
            shipLength = this.ships[i];
            char C = Character.forDigit(shipLength, 10);

            do {
                positionI = this.R.nextInt(table.length);
                positionJ = this.R.nextInt(table.length);

                ///////////////////////////////////////////////////////////////
                if (positionI + this.ships[i] > this.table.length) {
                    fitsI = false;
                } else {
                    fitsI = true;
                }
                if (positionJ + this.ships[i] > this.table.length) {
                    fitsJ = false;
                } else {
                    fitsJ = true;
                }
                for (int j = 0; j < locationsI.size(); j++) {
                    if (locationsI.get(j) == positionI) {
                        reappearingI = true;
                    } else {
                        reappearingI = false;
                    }
                }
                for (int j = 0; j < locationsJ.size(); j++) {
                    if (locationsJ.get(j) == positionJ) {
                        reappearingJ = true;
                    } else {
                        reappearingJ = false;
                    }
                }
                ///////////////////////////////////////////////////////////////

            } while (reappearingI == true || reappearingJ == true ||
                     fitsI == false || fitsJ == false);
            do {
                switch (direction) {
                    case 0:
                        this.table[positionI][positionJ] = C;
                        locationsI.add(positionI);
                        positionI++;
                        break;
                    case 1:
                        this.table[positionI][positionJ] = C;
                        locationsJ.add(positionJ);
                        positionJ++;
                        break;
                }
                shipLength--;
            } while (shipLength != 0);
        }
    }

    public void makeEmpty() {
        for (int i = 0; i < this.table.length; i++) {
            for (int j = 0; j < this.table.length; j++) {
                this.table[i][j] = '_';
            }
        }
    }

    public void printTable() {
        for (int i = 0; i < this.table.length; i++) {
            for (int j = 0; j < this.table.length; j++) {
                System.out.print("|" + table[i][j]);
                if (j == this.table.length - 1) {
                    System.out.println();
                }
            }
        }
    }
}

Lines 34 and 35 generate a set of coordinates, which are examined for validity in 37-62.
First, I check each coordinate (I for vertical, J for horizontal) for length validity - will the ship fall out of bounds? If yes, fitsI/fitsJ becomes false.
Then I check if those coordinates are already seeded, if yes, reappearingI/reapperaingJ become true.
If fitsI/fitsJ is false, or if reappearingI/reapperaingJ is true - new coordinates will be generated.

My current (and hopefully last) issue:
run:

run:
|_|_|_|_|_|_|_|2|_|_
|_|_|_|3|3|3|_|2|_|_
|_|_|_|_|_|_|_|_|_|_
|_|_|_|_|_|_|_|3|3|3
|_|_|_|2|_|_|_|_|_|_
|_|_|_|2|_|_|_|_|_|_
|_|_|_|_|_|_|4|4|2|4
|_|_|_|_|_|_|_|_|2|_
|_|_|_|_|_|_|_|_|_|_
|_|_|_|_|_|_|_|_|_|_
BUILD SUCCESSFUL (total time: 0 seconds

Notice how that size 2 ship seeded over that size 4 ship?
The initial coordinates for the 2 were unique, but now I need to probe for the rest of the ship's length.
I've tried writing a FOR loop that goes (int i = positionI; i < positionI + shipLength; i++)
But when I use IF to see if the slots in a ship's length's line are taken, my loop lands out of bounds. :[

[bguild]

in order to eliminate that problem, it would require a lot of work anyway,

It's actually not hard at all. With only a 10x10 grid and 7 ships to place, you can just do a simple exhaustive search. If you can produce a list of all places where each ship could be placed, then you can simply make one random decision for each ship with no danger of searching forever.

To produce a list of spaces where a ship can be placed, just consider each space on the grid one at a time. First check that it is far enough away from the edges and other ships. If it is, then you temporarily place your ship at that location and recursively produce the list for the next ship, just to check that placing your ship here will leave at least one option for all the remaining ships. If the list for the next ship is empty, then call this bad, otherwise add it to your list. Remove your ship from this space either way and move on to the next space.

When you're done, you've got a list of all the spaces where you can safely place your ship without overlapping other ships or clogging up the grid to the point where you won't have any space for later ships. Randomly choose one of them, place the ship there, then move on to the next ship.

If that turns out to be slow you can save a big portion of the computer time with a little more typing by creating a second method that does the same thing except instead of producing a list of spaces where a ship can be placed, it just returns true if it is possible to place the ship anywhere on the grid. That means you save yourself from having to build the list and you can stop as soon as you find the first useable space. It's possible that the method would always return true if there is no way to arrange the ships that hopelessly clogs up the grid, but it costs so little to check and some day you might want to add more ships or use bigger ships.

[JamesCherrill]

This is all a premature optimisation.
I tried the full game setup (battleshup, 2 destroyers ... 5 subs) by the brute force random approach, and on average there are only about 10 unused random ships. Not a problem.
(code follows if you're interested - just a hack)

import java.util.Random;

public class Battleships {

static Random random = new Random();

   public static void main(String[] args) {
      new Battleships();
   }

   Ship[][]shipGrid = new Ship[10][10];
   int collisions = 0; // new random ships that were not used because they collided

   Battleships() {
      addRandomShip(5, 'B'); // battleship
      addRandomShip(4, 'D'); // destroyer
      addRandomShip(4, 'D'); // destroyer
      for (int i = 0; i <3; i++ ) addRandomShip(3, 'C'); // cruiser
      for (int i = 0; i <4; i++ ) addRandomShip(2, 'M'); // minesweeper
      for (int i = 0; i <5; i++ ) addRandomShip(1, 'S'); // submarine
      printShipGrid();
   }

   void addRandomShip(int length, char printChar) {
      Ship s;
      do {
         s = new Ship(length, printChar);
         collisions++;
      } while (! s.fitsOnGrid());
      s.addToGrid();
      collisions--;
   }

   void printShipGrid() {
      for (int r = 0; r <10; r++) {
         for (int c = 0; c < 10; c++) {
            System.out.print((shipGrid[r][c]==null)?'.':shipGrid[r][c].printChar);
         }
         System.out.println();
      }
      System.out.println(collisions + " collisions");
   }


   class Ship {
     final int row, col, length;
     final boolean vertical;
     final char printChar;

     Ship(int length, char printChar) {
        // create ship at random position
        this.length = length;
        this.printChar = printChar;
        vertical = random.nextBoolean();
        if (vertical) {
           row = random.nextInt(10-length +1);
           col = random.nextInt(10);
        } else {
           row = random.nextInt(10);
           col = random.nextInt(10-length +1);
        }
     }

     boolean fitsOnGrid() {
        if (vertical) {
           for (int r = row; r <= row+length-1; r ++) {
              if (shipGrid[r][col] != null) return false; //collision
           }
        } else {
           for (int c = col; c <= col+length-1; c ++) {
              if (shipGrid[row][c] != null) return false; //collision
           }
        }
        return true; // no collisions, this ship fits OK
     }

     void addToGrid() {
        if (vertical) {
           for (int r = row; r <= row+length-1; r ++) {
              shipGrid[r][col] = this;
           }
        } else {
           for (int c = col; c <= col+length-1; c ++) {
              shipGrid[row][c] = this;
           }
        }
     }

   }

}

[Pobunjenik]

I like the logic you used, James! Very smart stuff. :)
However, the game requires all ships to be placed before the game actually begins, so no skipping.
More about the game right over there -> Battleship (game)

As for my code, I know exactly what I have to do (in theory), but I just can't seem to cook up a code to do it.

Here is a step by step of what I think has to be done to get flawless seeds on every iteration:
- generate coordinates
- generate direction
- check for collision
- check for out of bounds
- in case of collison or out of bounds, return to step 1

PS
The story behind the code:
This is a pet project of mine. A colleague of mine and I discuessed about making a program play Battleships on its own.
That means: program seeds ships & program shoots at them.

This is part 1 - program seeds ships. :)

[riahc3]

Its a good excerise, Java or not.

I'd like to hear comments on the way I code, what are my strong points, what should I improve, am I using bad logic?

The way someone code is very personal, for me. Makings lots of classes with no comments is the same as making one big entire class with lots and lots of comments. People are object obsessed and I believe programming is what is easier for you to read, not better organized (Exceptions are using a if 1==1 vs a while(1==1) and at the end change 1 to another number, if its a simple condition; You obviously use the if).

A good thing that is done is to think and write down what to do before you code it. Makes things a lot easier and faster. I dont do it personally but I agree that it is better.

[Pobunjenik]

I'm glad you like it, riahc3. :)

Anyways, I'm still stuck, but I'm not giving up!
I've reworked the conditioning part (lines ~ 35-67) completely. They now look like this:

            do {
                direction = this.R.nextInt(2);
                positionI = this.R.nextInt(9);
                positionJ = this.R.nextInt(9);

                ///////////////////////////////////////////////////////////////                
                if (positionI + this.ships[i] > this.table.length
                        || positionJ + this.ships[i] > this.table.length) {
                    fits = false;
                } else {
                    fits = true;
                }
                if (fits == true) { // This gets executed ONLY if the ship is NOT out of bounds.
                    switch (direction) {
                        case 0: 
                            for (int j = positionI; j <= ships[i]; j++) { // Go from slot to slot in shipLength's value, execute IF for each slot:
                                if (table[j][positionJ] != '_') { // I believe this is ok.
                                    collisionI = true; // This seems to get ignored.
                                    break; // Break FOR loop if a collision is detected.
                                } else {
                                    collisionI = false; // No collisions, proceed to seed the ship.
                                }                                
                            }
                            break;
                        case 1: // Same problem, except different seed direction.
                            for (int j = positionJ; j <= ships[i]; j++) {
                                if (table[positionI][j] != '_') {
                                    collisionJ = true;
                                    break;
                                } else {
                                    collisionJ = false;
                                }
                            }
                            break;
                    }
                }

                ///////////////////////////////////////////////////////////////

            } while (collisionI == true || collisionJ == true || fits == false); // I don't think this part is wrong.

The goal:
Make sure that the ship fits inside the table and that the ship doesn't overlap other ships BEFORE seeding the ship.

The problem:
My code seems to completely ignore the collision tests.
I want the code to go from slotA to slotB (covering the entire ship's length based on the direction) and check if ALL slots the ship would occupy are empty ('_' means empty).
If it finds even 1 slot occupied, the FOR loop should break and a new set of coordinates should be generated and tested in the same way.

[JamesCherrill]

"No skipping"?
My code adds all ships then displays them. Just try it!

[Pobunjenik]

Completed!

package potapanjebrodova;

import java.util.Random;

public class PotapanjeBrodova {
    // 6, 4, 4, 3, 3, 3, 2, 2, 2, 2

    int[] ships = {6, 4, 4, 3, 3, 3, 2, 2, 2, 2};
    char[][] table = new char[10][10];
    Random R = new Random();

    public static void main(String[] args) {

        PotapanjeBrodova PB = new PotapanjeBrodova();
        PB.makeEmpty();
        PB.seeding();
        PB.printTable();

    }

    public void seeding() {

        boolean fits;
        int positionI, positionJ, direction, shipLength, collision;

        for (int i = 0; i < this.ships.length; i++) {
            shipLength = this.ships[i];
            char C = Character.forDigit(shipLength, 10);

            do {
                direction = this.R.nextInt(2);
                positionI = this.R.nextInt(9);
                positionJ = this.R.nextInt(9);
                collision = 0;
                if (positionI + this.ships[i] > this.table.length
                        || positionJ + this.ships[i] > this.table.length) {
                    fits = false;
                } else {
                    fits = true;
                }
                if (fits) {
                    switch (direction) {
                        case 0:
                            outterloop:
                            for (int j = positionI; j < positionI + this.ships[i]; j++) {
                                for (int k = positionJ; k < positionJ + 1; k++) {
                                    if (this.table[j][k] != '_') {
                                        collision++;
                                        break outterloop;
                                    }
                                }
                            }
                        case 1:
                            outterloop:
                            for (int j = positionI; j < positionI + 1; j++) {
                                for (int k = positionJ; k < positionJ + this.ships[i]; k++) {
                                    if (this.table[j][k] != '_') {
                                        collision++;
                                        break outterloop;
                                    }
                                }
                            }
                    }
                }
                System.out.print("Ship:" + (i + 1) + " Size:" + this.ships[i] + " COL:" + collision + " FITS: " + fits + "\n");
            } while (collision != 0 || fits == false);

            do {
                switch (direction) {
                    case 0:
                        this.table[positionI][positionJ] = C;
                        positionI++;
                        break;
                    case 1:
                        this.table[positionI][positionJ] = C;
                        positionJ++;
                        break;
                }
                shipLength--;
            } while (shipLength != 0);
        }
    }

    public void makeEmpty() {
        for (int i = 0; i < this.table.length; i++) {
            for (int j = 0; j < this.table.length; j++) {
                this.table[i][j] = '_';
            }
        }
    }

    public void printTable() {
        System.out.println("\n _ _ _ _ _ _ _ _ _ _");
        for (int i = 0; i < this.table.length; i++) {
            for (int j = 0; j < this.table.length; j++) {
                System.out.print("|" + table[i][j]);
                if (j == this.table.length - 1) {
                    System.out.println("|");
                }
            }
        }
    }
}

This code works! I've tested it countless times.
Here is an output example (with line 65, which I used to debug):

run:
Ship:1 Size:6 COL:0 FITS: true
Ship:2 Size:4 COL:1 FITS: true // Ship no. 2 fits, but it's colliding with something.
Ship:2 Size:4 COL:0 FITS: true // So here we try for ship no. 2 again, and it fits with 0 collisions.
Ship:3 Size:4 COL:1 FITS: true
Ship:3 Size:4 COL:1 FITS: true
Ship:3 Size:4 COL:0 FITS: false // This one has no collisions, but it goes out of bounds.
Ship:3 Size:4 COL:1 FITS: true // Try ship no. 3 again, success!
Ship:3 Size:4 COL:0 FITS: false
Ship:3 Size:4 COL:0 FITS: true
Ship:4 Size:3 COL:0 FITS: true
Ship:5 Size:3 COL:0 FITS: false
Ship:5 Size:3 COL:1 FITS: true
Ship:5 Size:3 COL:0 FITS: true
Ship:6 Size:3 COL:0 FITS: true
Ship:7 Size:2 COL:0 FITS: true
Ship:8 Size:2 COL:0 FITS: true
Ship:9 Size:2 COL:2 FITS: true // This one collided with 2 occupied slots.
Ship:9 Size:2 COL:1 FITS: true
Ship:9 Size:2 COL:0 FITS: true
Ship:10 Size:2 COL:1 FITS: true // Collision.
Ship:10 Size:2 COL:1 FITS: true // Again.
Ship:10 Size:2 COL:1 FITS: true // And again.
Ship:10 Size:2 COL:0 FITS: true // Seeded!

 _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|4|3|3|3| // This is the final layout.
|_|_|_|_|_|_|4|_|_|_|
|6|4|_|_|_|_|4|_|_|_|
|6|4|_|_|2|2|4|2|_|_|
|6|4|_|_|_|_|2|2|_|_|
|6|4|_|_|3|_|2|_|_|_|
|6|_|_|3|3|_|2|2|_|_|
|6|_|_|3|3|_|_|_|_|_|
|_|_|_|3|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
BUILD SUCCESSFUL (total time: 0 seconds)

I have to admit, lines 30-66 did test my limits.
Turns out the logic in my previous attempt was good, but the collision test was flawed (FOR loop didn't hop from slot to slot as intended).

[bguild]

This is all a premature optimisation.

It's not premature optimisation to find all the possible positions for a ship before making the random choice. It is more like doing it the slow way that guarantees correctness, which is far from optimisation. I've altered your elegant solution to turn it into an almost identical solution that doesn't depend on luck or the implementation of java.util.Random.

import java.util.*;

public class Battleships {
    static final Random random = new Random();

    public static void main(String[] args) {
        new Battleships().printShipGrid();
    }

    final Ship[][] shipGrid = new Ship[10][10];
    Battleships() {
        addRandomShip(5, 'B'); // battleship
        addRandomShip(4, 'D'); // destroyer
        addRandomShip(4, 'D'); // destroyer
        for (int i = 0; i < 3; i++) addRandomShip(3, 'C'); // cruiser
        for (int i = 0; i < 4; i++) addRandomShip(2, 'M'); // minesweeper
        for (int i = 0; i < 5; i++) addRandomShip(1, 'S'); // submarine
    }

    void addRandomShip(int length, char printChar) {
        List<Ship> possibleShips = new ArrayList<Ship>(200);
        for (int r = 0; r < 10 - length + 1; r++) {
            for (int c = 0; c < 10; c++) {
                Ship maybeShip = new Ship(r,c,true,length,printChar);
                if(maybeShip.fitsOnGrid()) possibleShips.add(maybeShip);
            }
        }
        for (int r = 0; r < 10; r++) {
            for (int c = 0; c < 10 - length + 1; c++) {
                Ship maybeShip = new Ship(r,c,false,length,printChar);
                if(maybeShip.fitsOnGrid()) possibleShips.add(maybeShip);
            }
        }
        if(possibleShips.isEmpty()) throw new RuntimeException("A ship couldn't be placed");
        Ship s = possibleShips.get(random.nextInt(possibleShips.size()));
        s.addToGrid();
    }

    void printShipGrid() {
        for (int r = 0; r < 10; r++) {
            for (int c = 0; c < 10; c++) {
                System.out.print((shipGrid[r][c] == null) ? '.' : shipGrid[r][c].printChar);
            }
            System.out.println();
        }
    }

    class Ship {
        final int row, col, length;
        final boolean vertical;
        final char printChar;
        Ship(int row, int col, boolean vertical, int length, char printChar) {
            this.row = row;
            this.col = col;
            this.vertical = vertical;
            this.length = length;
            this.printChar = printChar;
        }

        boolean fitsOnGrid() {
            if(vertical) {
                for (int r = row; r <= row + length - 1; r++) {
                    if(shipGrid[r][col] != null) return false; // collision
                }
            } else {
                for (int c = col; c <= col + length - 1; c++) {
                    if(shipGrid[row][c] != null) return false; // collision
                }
            }
            return true; // no collisions, this ship fits OK
        }

        void addToGrid() {
            if(vertical) {
                for (int r = row; r <= row + length - 1; r++) {
                    shipGrid[r][col] = this;
                }
            } else {
                for (int c = col; c <= col + length - 1; c++) {
                    shipGrid[row][c] = this;
                }
            }
        }
    }
}

[Pobunjenik]

I don't see why you'd ever test for all possible locations, but I see how the logic is correct.
Just find the first available slot and use it! :D

You've got 100 slots, and only 31 slots are occupied by ships (according to the vanilla rules of the game). So, in every single iteration, even when all ships are seeded - you'll have a minimum of 69 empty slots.
In other words, you'll get the job done fast and you'll never fall into an inifinte loop.

[JamesCherrill]

I've altered your elegant solution to turn it into an almost identical solution that doesn't depend on luck or the implementation of java.util.Random.

That's OK, I just wish you had put that new code in its own method eg
List<Ship> getAllPossibleShips(...) { ...

:-)

[JamesCherrill]

Now this is over, I'm still a bit unhappy with the code I posted earlier - in particular those almost-the-same loops inside the if (vertical) blocks. So here's a much cleaner/shorter version that has a width and height for each ship, so it doesn't need the vertical/horizontal boolean or the related if tests. It also opens up some possibilites such as an aircraft carrier that's 6x2 cells. There are a few other tidy-ups as well.

@pobunjenic: yhou may want to hang on to this one. I still can't see how you will know when a ship has been sunk using your current data structures.

import java.util.Random;

public class Battleships {

   private static Random random = new Random();

   public static void main(String[] args) {
      new Battleships();
   }

   final int ROWS, COLS;
   final Ship[][] shipGrid;

   Battleships() {
      // Milton Bradley version of the rules, (via Wikipedia):
      ROWS = 10; COLS = 10;
      shipGrid = new Ship[ROWS][COLS];
      addShip("AircraftCarrier", 5); 
      addShip("Battleship", 4); 
      addShip("Battleship", 4);
      for (int i = 0; i < 3; i++)
         addShip("Submarine", 3);
      for (int i = 0; i < 4; i++)
         addShip("Cruiser", 3); 
      for (int i = 0; i < 5; i++)
         addShip("Destroyer", 2);
      printShipGrid();
   }

   void addShip(String description, int length) {
      Ship s;
      int collisionCounter = 0;
      do {
         if (++collisionCounter > 100) {
            throw new RuntimeException("Too many random collisions, bguild was right.");
         }
         s = new Ship(description, length);
      } while (s.collidesWIthAnotherShip());
      s.addToGrid();
   }

   void printShipGrid() {
      for (int r = 0; r < ROWS; r++) {
         for (int c = 0; c < COLS; c++) {
            System.out.print((shipGrid[r][c] == null) ? '.' : shipGrid[r][c].printChar);
         }
         System.out.println();
      }
   }

   class Ship {
      private final int row, col, width, height;
      public final String description;
      public final char printChar;

      Ship(String description, int length) {
         // create ship with random direction & position
         if (random.nextBoolean()) {
            width = length;
            height = 1;
         } else {
            height = length;
            width = 1;
         }
         row = random.nextInt(ROWS - height + 1);
         col = random.nextInt(COLS - width + 1);
         this.description = description;
         this.printChar = description.charAt(0);
      }

      boolean collidesWIthAnotherShip() {
         for (int r = row; r <= row + height - 1; r++) {
            for (int c = col; c <= col + width - 1; c++) {
               if (shipGrid[r][c] != null) return true; //collision
            }
         }
         return false; // no collisions, this ship is OK
      }

      void addToGrid() {
         for (int r = row; r <= row + height - 1; r++) {
            for (int c = col; c <= col + width - 1; c++) {
               shipGrid[r][c] = this;
            }
         }
      }

   }

}

[Pobunjenik]

yhou may want to hang on to this one. I still can't see how you will know when a ship has been sunk using your current data structures.

I see your concern, but this code's job was only to generate a valid layout.
If I ever decide to make this into a game, I'd have another class pick up the generated layout and generate a neat table with each slot having 3 attributes (empty, ship, hit). I believe this is possible by using only a 2D array and it's values (_, 6, 4, 3, or 2).

The logic:
- pick up 2D array
- go through array, mark '' as empty (boolean null), and whatever != '' as a ship cell (boolean true)
- use ancient magic to allow players to shoot
- let the player shoot
- test

if (slot == null){
    // MISS!
} else if (slot == true){
    // HIT!
    slot = false;
}

And repeat!

PS
The numbers could later be used to display different icons for each ship. :)

PPS
I'd appreciate a hint... Just a hint!
What direction must I take to make a table similar to the one found here? Just the structure, the mouseovers and such I'll find. :)

[Pobunjenik]

• go through array, mark '_' as empty (boolean null), and everything else as a ship cell (boolean true)

Had to correct a formating issue.

[JamesCherrill]

1. All you need is a boolean[][] - has the player targetted this cell? You can then use the existing Ship[][] array to see if that's a hit, or what to display to the user for that cell.

2. Draw a grid - subclass JPanel and in the paintComponent method 2 loops to draw horizontal and vertical lines, OR nested loop to draw little boxes - easier that way to draw the box's contents at the same time.

ps Conway's Life is another really good thing to practice your Java with.

[kedxu]

Just a note: if you want to know or might want to know later whether a ship has been sunk, perhaps to tell the player "You just sank a ship!", simply storing the empty/ship/hit status of each tile will not work--that means you can't just use a 2D boolean array. You'd need as James said a 'ship' class, with each ship storing its occupied cells. Otherwise, you could never tell what is and isn't part of the same ship, especially when they're directly adjacent.

[Pobunjenik]

My current code generates a char[][], with the cell's contents being either _, 6, 4, 3 or 2.
In a day or two, I'll try to build a different class which goes through the char[][] and visualises something like this (by following James's advice):
-if _, empty cell.
-if number, ship (and assign color to cell according to number)

Does this even make sense? o.O Exporting a 2D array to a makeThisLookPretty class?

[JamesCherrill]

(by following James's advice)

Not my advice. See my code for my best suggestion.

[Nandomo]

Seems Like we are working on the same project my good sir.

[Pobunjenik]

Seems Like we are working on the same project my good sir.

How so?

[Nandomo]

I am also creating a battleship game, but I am stuck closing my GUI after I refresh with a new one, already have my ship placement logic.

[Pobunjenik]

Cool. :D
Would you like to work together? :D

[Pobunjenik]

Alright! I've reworked this code into what I consider to be correct.
I've tested the new code by looping the seeding and printing methods 100 times to look for bugs - none were found!
No ships collided, no ships were out of bounds and I've even built in a small method to fire at ships (which returns correct values for both hits and misses).
I've accomplished this by having 2 2D char arrays, one that contains the actual layout of the ships, and another empty one which displays hits and misses as the user fires.

GUI time.
I've googled like a madman to find instructions on how to transfer data from a 2D array (in this case, char[][] board) to a jTable (which is in a separate class called GUI.java).
I would appreciate some tips so that I can get some friends to play the game on their PCs. :D

NOTE:
Here is a print of the board (the one which contains the ships):

 _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|2|2|_|_|_|
|_|_|_|_|_|3|3|3|_|_|
|_|_|4|4|4|4|_|3|_|_|
|_|_|6|2|_|2|2|3|_|_|
|_|_|6|2|_|_|_|3|_|_|
|2|_|6|_|_|_|_|_|_|_|
|2|_|6|_|4|_|_|_|_|_|
|_|_|6|_|4|_|_|3|3|3|
|_|_|6|_|4|_|_|_|_|_|
|_|_|_|_|4|_|_|_|_|_|

The first line and the '|' symbol are just for looks, they're not actually part of the array.