Battleship game - ships overlapping

Question

I'm writing a simple battleship game in Java using the ACM library. After the game starts, ships are supposed to be put on the canvas at random locations but the problem is that the ships might cover each other and this is not allowed in the game. How can I avoid the ships being placed on top of each other?

My code is:

private void putSmallShips() {
    for (int i = 0; i < SMALL_SHIP_QUANTITY; i++){
        smallShip = new GRect(SMALL_SHIP_WIDTH, SHIP_HEIGHT);
        int x = rgen.nextInt(10, 510);
        int y = rgen.nextInt(10, 510);
        while (true){
            gobj = getElementAt(x, y);
            if (gobj == null) break;
            x = rgen.nextInt(10, 510);
            y = rgen.nextInt(10, 510);
        }
        smallShip.setLocation(x, y);
        add(smallShip);
    }
}

private void putMiddleShips() {
    for (int i = 0; i < MIDDLE_SHIP_QUANTITY; i++){
        middleShip = new GRect(MIDDLE_SHIP_WIDTH, SHIP_HEIGHT);
        int x = rgen.nextInt(10, 530);
        int y = rgen.nextInt(10, 530);

        while (true){
            gobj = getElementAt(x, y);
            if (gobj == null) break;
            System.out.println("opa!");
            x = rgen.nextInt(10, 530);
            y = rgen.nextInt(10, 530);
        }
        x = x + i * 10;
        y = y + i * 10;
        middleShip.setLocation(x, y);
        add(middleShip);
    }
}

private void putBigShips() {
    for (int i = 0; i < BIG_SHIP_QUANTITY; i++){
        bigShip = new GRect(BIG_SHIP_WIDTH, SHIP_HEIGHT);
        int x = rgen.nextInt(10, 550);
        int y = rgen.nextInt(10, 550);
        while (true){
            gobj = getElementAt(x, y);
            if (gobj == null) break;
            x = rgen.nextInt(10, 550);
            y = rgen.nextInt(10, 550);
        }
        bigShip.setLocation(x, y);
        add(bigShip);
    }
}

As you see I put a while loop inside the for loop, but it doesn't help.

Nieberg

Well the quick way would be to check to see if any of the locations the ship would occupy are already occupied... – Valentinevalentino

The while loop ensures the start of the ship will not be placed at the exact same point, but does not account for the rest of the ship, hence the overlapping. Could you also post the code of your add function as that is likely the best place to put the code, including the while loop and random number generation. – Paginal

Answer 1

First of all I'd suggest you split model layer and presentation layer.

In other words you can define class BattleShip, that class would hold ship position, size and another properties and it also can contain method to check if it intersects with some another ship.

Then you can create instances and add them to collection only if the instance doesn't intersect with any instance present in collection.

Then you can render them all on screen in one go.

Chasseur

Answer 2

I'd create an Array and store the values of each ship location as you enter them onto the canvas. Then for the next ship, before you place it, check whether that location is already taken on the canvas. Obviously you'll have to remember that ships are different lengths and some are horizontal and vertical too.

Geisel

Answer 3

I had recently implemented this game as part of an interview. My solution was to just partition/tile randomly the grid into N > 3 areas and then place the 3 ships that were required (2 battleships and 1 destroyer), by placing one ship into one area. The N areas do not overlap pairwise and taken together they cover the whole grid (I think this is called tiling of the grid). So as the N areas do not overlap, the ships don't overlap too. The interviewers liked this solution a lot. Also, the randomness was guaranteed too.

An alternative solution was to keep placing ships at random positions and keep checking if ship K overlaps with any of the previous ships placed (1,2,3,...,K-1) but this had some obvious drawbacks which I didn't like: 1) the ship overlap check itself which has to be made is not really elegant and clean; 2) the fact that this is not a deterministic procedure, and you don't know in advance if your placing algorithm will terminate, and if it does in how many steps it will terminate.

So I just did this random partitioning/tiling solution mentioned above.

Cologne

I think placing ships in random positions makes more sense game-wise. It would be a little irritating to play game if you know ship places in advance. – Chasseur

@Chasseur Yes, sure but the randomness is guaranteed too (as the partitioning/tiling of the grid is random, i.e. I don't always use the same tiling of the grid). – Cologne