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.

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.

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.

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.