Морской бой. Как правильно расставить корабли?

#java #алгоритм

Пробую написать простенький морской бой на Java. Все почти сделал, кроме правильного
алгоритма помещения кораблей на карту. В коде комментариями описано где именно проблема.

public class Main {
public static void main(String[] args) {
    Random rand = new Random();
    Field field = new Field();
    Player player = new Player();
    player.getName();
    field.init();
    final int NUMBEROFSHIPS =10;
    Ship [] ships = new Ship[NUMBEROFSHIPS];
    for (int i = 0; i < NUMBEROFSHIPS; i++) {
        boolean isShipSettedUp = false;
        do { //вот здесь проблемы
             //корабли расставляются рандомно на свободное место на карте
            // получается так, что для последних кораблей не хватает 
           //места и идет зацикливание 
           //Ship(координата Х, координата У,  размер, вертикален ли)
            if (i <=3) ships[i] = new Ship(rand.nextInt(10), rand.nextInt(10), 1, false);
            if (i >3 && i <=6) ships[i] = new Ship(rand.nextInt(10), rand.nextInt(10),
2, false);
            if (i >6 && i <= 8) ships[i] = new Ship(rand.nextInt(10), rand.nextInt(10),
3, false);

            if (i > 8 && i <=9) ships[i] = new Ship(rand.nextInt(10), rand.nextInt(10),
4, false);
            if (field.isCanSetShip(ships[i])) {
                field.setShip(ships[i]);
                isShipSettedUp =true;
           }
        } while(!isShipSettedUp);
    }
    System.out.println("Game start!");
    do {
        field.show();
        System.out.println("Where to shoot?");
        System.out.println("Enter column: ");
        int shootX = player.getShoot();
        System.out.println("Enter row: ");
        int shootY = player.getShoot();
        Shoot shoot = new Shoot(shootX,shootY);
        field.doShoot(shoot);
    } while (field.isNotGameOver());
}
}


Класс Field:

public class Field {
final int FIELDSIZE = 10;
char[][] cells = new char[FIELDSIZE][FIELDSIZE];
Ship ship;
void init() {
    for (int i = 0; i < FIELDSIZE; i++) {
        for (int j = 0; j < FIELDSIZE; j++) {
            cells[i][j] = '.';
        }
    }
}
void setShip(Ship ship) { //помечаю ячейку в массиве, что здесь корабль
    this.ship = ship;
    if (ship.isVertical) {
        for (int i = 0; i < ship.size; i++) {
            cells[ship.positionX + i][ship.positionY] = 'X';
        }
    } else {
        for (int i = 0; i < ship.size; i++) {
            cells[ship.positionX][ship.positionY + i] = 'X';
        }
    }
}

void doShoot(Shoot shoot) {
    switch (cells[shoot.xCoord][shoot.yCoord]) {
        case '.':
            System.out.println("MISS");
            cells[shoot.xCoord][shoot.yCoord] = '*';
            break;
        case 'X':
            System.out.println("GOAL");
            cells[shoot.xCoord][shoot.yCoord] = '_';
            show();
            break;
        case '*':
            System.out.println("You already shoot here...");
            break;
        default:
            System.out.println("Error!");
    }
}

void show() {
    for (int i = 0; i < FIELDSIZE; i++) {

        if (i == 0) {
            for (int k = 0; k < FIELDSIZE; k++) {
                System.out.print("\t" + k);
            }
            System.out.println();
        }
        System.out.print(i);
        for (int j = 0; j < FIELDSIZE; j++) {
            System.out.print("\t" + cells[i][j]);
        }
        System.out.println();
    }
}

boolean isShipPresent(int positionX, int positionY) {
    return cells[positionX][positionY] == 'X';
}

boolean isNotGameOver() {
    boolean isPresent = false;
    for (int i = 0; i < FIELDSIZE; i++) {
        for (int j = 0; j < FIELDSIZE; j++) {
            if (cells[i][j] == 'X') isPresent = true;
        }
    }
    return isPresent;
}
//Проверка на то, можно ли в данном участке поставить корабль
//Написано не очень правильно, только учусь :(
boolean isCanSetShip(Ship ship) {
    boolean canSet = true;
    if (ship.positionX + ship.size > FIELDSIZE - 1 || ship.positionY + ship.size
> FIELDSIZE - 1)
        canSet = false;
    else {

        //Если корабль стоит горизонтально
        if (!ship.isVertical) {
            if (ship.positionX == 0 && ship.positionY > 0) {
                for (int i = 0; i <= ship.size; i++) {
                    for (int j = -1; j <= 1; j++) {
                        if (ship.positionY + j < FIELDSIZE && ship.positionY + j >= 0) {
                            if (isShipPresent(ship.positionX + i, ship.positionY
+ i)) canSet = false;
                        } else canSet = false;
                    }
                }
            }
            if (ship.positionY == 0 && ship.positionX > 0) {
                for (int i = -1; i <= ship.size; i++) {
                    for (int j = 0; j <= 1; j++) {
                        if (ship.positionX + i < FIELDSIZE && ship.positionX + i >= 0) {
                            if (isShipPresent(ship.positionX + i, ship.positionY
+ j)) canSet = false;
                        } else canSet = false;
                    }
                }
            }
            if (ship.positionX == 0 && ship.positionY == 0) {
                for (int i = 0; i <= ship.size; i++) {
                    for (int j = 0; j <= 1; j++) {
                        if (isShipPresent(ship.positionX + j, ship.positionY + i))
canSet = false;
                    }
                }
            }
            if (ship.positionX > 0 && ship.positionY > 0) {
                for (int i = -1; i <= ship.size; i++) {
                    for (int j = -1; j <= 1; j++) {
                        if (ship.positionX + j >= 0 && ship.positionY + i >= 0 &&
ship.positionX + j < FIELDSIZE && ship.positionY + i < FIELDSIZE) {
                            if (isShipPresent(ship.positionX + j, ship.positionY
+ i)) canSet = false;
                        } else canSet = false;
                    }
                }
            }
        } else {
            //если корабль вертикально
            //пока не использую. На данный момент все корабли с горизонтальным положением
        }
    }
    return canSet;
}
}


Как правильно организовать алгоритм?
    

Ответы

Ответ 1

Запретная зона вокруг корабля представляет собой прямоугольник, внутри которого не
должно быть других кораблей. Зная верхнюю левую и нижнюю правую точки, можно проверить
все точки внутри. Чтобы не возиться с частными случаями, можно просто обрезать проверяемую
область.

public boolean canSetShip( Ship ship ) {
    // проверяем, что наш корабль попадает в поле
    if ( ship.positionX < 0 || ship.positionY < 0 || FIELDSIZE <= ship.positionX
|| FIELDSIZE <= ship.positionY ) return false;
    if ( ship.isVertical && FIELDSIZE <= ship.positionY + ship.size ) return false;
    if ( !ship.isVertical && FIELDSIZE <= ship.positionX + ship.size ) return false;

    // проверяем, что в зоне вокруг корабля никого нет
    // обрезаем зону
    int minX = Math.max( 0, ship.positionX - 1 );
    int minY = Math.max( 0, ship.positionY - 1 );
    int maxX = Math.min( FIELDSIZE - 1, ship.positionX + 1 + (ship.isVertical ? 0
: ship.size) );
    int maxY = Math.min( FIELDSIZE - 1, ship.positionY + 1 + (ship.isVertical ? ship.size
: 0) );

    // сама проверка
    for ( int x = minX; x <= maxX; x++ ) {
        for ( int y = minY; y <= maxY; y++ ) {
            if ( isShipPresent( x, y ) ) return false;
        }
    }
    return true;
}


Еще вам стоит переделать установку кораблей (странно, что "вертикальный" корабль
расположен по оси X) и вывод поля (сейчас у вас cells[positionX][positionY] при positionX
= 5; positionY = 3 выведется, как 4ая ячейка в 6ой строке).


Ответ 2

По самому алгоритму.
Большие корабли (3 и 4 - палубные - в любом случае) надо расставлять по стенкам,
чтобы их запретная зона не мешала другим кораблям прятаться, и проблема размещения
снимается.
Да, на стенке проще искать. Зато потом замучаются однопалубные по всей карте искать.
Так что алгоритм ещё и усилится.