Морской бой алгоритм расстановки кораблей

Добрый день хочу узнать как написать алгоритм расстановки кораблей чтобы они не прикасались друг к другу ?

Поле 10×10 это двухмерный массив из символов

Корабли из обычного морского боя :

4 клетки
3 клетки
2 клетки
1 клетка

  • Вопрос задан более трёх лет назад
  • 4142 просмотра

Требуется случайная генерация?

1. определяешь случайным образом положение корабля
2. исключаешь занятые клетки с массива, если места нет а корабли есть – обнуляешь поле.
3. идешь к пункту 1, пока не расставишь все корабли.

Какой-то слишком общий вопрос. Вы непонимаете, как делать проверку на соседние пустые клетки в двумерном массиве?

Создаете функцию, где по циклу или отдельными проверками делаете так:

и проверяете для всех нужных размеров. Сократить тут можно немного.

>и проверяете для всех нужных размеров. Сократить тут можно немного.

то есть вам нужно будет сделать проверку всех точек, и для каждого корабля учесть, что он должен продолжаться. Тут нет какого-то волшебного алгоритма. Нужно просто проверить ВСЕ точки.

Вступление.

Игру «Морской бой», думаю, представлять не надо. Вряд ли найдётся хоть один человек, который хотя бы раз не играл в неё. Давайте и мы создадим полноценный «Морской бой», используя HTML-вёрстку для отображения структуры игры на экране монитора, визуально оформим её с помощью таблицы стилей, а с помощью чистого JavaScript напишем «движок», определяющий поведение игры.

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

Читайте также:  Мои звонки приложение для айфона

Как говорится — лучше один раз увидеть. На приведённом ниже скриншоте прекрасно видно, что представляет из себя игровое поле, сколько типов кораблей, в зависимости от количества палуб будет в эскадре, как выглядит промах, попадание и отметка, где корабля точно быть не может.

Надеюсь всё всем понятно. Ну а теперь составим техническое задание, чтобы ничего не забыть и не пропустить.

Техническое задание на создание игры «Морской бой»

Количество и типы кораблей, их расположение.

Как и в реальной игре, эскадра будет состоять из:
— одного четырёхпалубного;
— двух трёхпалубных;
— трёх двухпалубных;
— четырёх однопалубных кораблей.
Корабли могут располагаться вертикально и горизонтально, но при этом между кораблями должна быть хотя бы одна пустая клетка, в том числе и по диагонали. Корабли не могут иметь Г-образную форму.

Расстановка кораблей и редактирование их положения.

Корабли игрока могут расставляться по случайному закону или самим игроком, путём перетаскивания их на игровое поле. И в первом, и во втором случае можно редактировать направление положения палуб (вертикальное или горизонтальное), путём клика правой кнопкой мышки по первой палубе и расположение, путём перетаскивания. Первая палуба — при горизонтальном расположении корабля — самая левая, при вертикальном — самая верхняя.
При перетаскивании или повороте корабля скрипт постоянно отслеживает корректность координат корабля. Если корабль будет соприкасаться с соседним или выходить за пределы игрового поля, то рамка корабля окрасится в красный цвет, а корабль, после отпускания кнопки мышки, вернётся в исходное положение. В противном случае, рамка корабля будет зелёная.
Нет необходимости пытаться установить корабль точно по границам клеток — программа сама откорректирует его положение, установив в ближайшие валидные координаты.
В момент начала игры, редактирование положения кораблей отключается.

Читайте также:  Максимальное смещение от положения равновесия это

Ведение морского боя

Если сражение первое, рандомно определяем, кто стреляет первым. Далее, первым стреляет победитель.
Координаты выстрела передаются путём клика по выбранной клетке — ввода координат с клавиатуры не будет.
Попадание отмечается красным крестиком, промах — точкой, клетку, где корабля точно быть не может, отмечаем / снимаем отметку кликом правой кнопкой мышки.
Сообщений «ранил», «убил / потопил» не будет — самостоятельно определяем тип корабля.
Под игровыми полями выводятся сообщения о том, чей выстрел и результат выстрела.

Искусственный интеллект противника.

Для ведения морского боя, компьютер должен обладать хотя бы примитивным искусственным интеллектом. Он должен уметь:
— формировать координаты выстрела, согласно заложенного алгоритма ведения морского боя.
— при попадании в палубу корабля, продолжить его обстрел, пока корабль не будет потоплен.
— отмечать клетки, куда стрелять не имеет смысла и исключать координаты этих клеток из матрицы возможных выстрелов.

На этих требования к ИИ мы пока и остановимся, хотя можно рассмотреть варианты размещения кораблей компьютером, при которых сильно уменьшается вероятность попадания в однопалубные корабли.

Окончание морского боя.

Выводится сообщение о победителе. Если выиграл компьютер, то отображаются его не потопленные корабли.

HTML-вёрстка для игры «Морской бой».

При создании HTML страницы, наша главная задача — воспроизвести внешний вид игрового поля морского боя максимально похожий на тот, к которому вы привыкли, играя на тетрадочных листах. Разметка HTML не сложная и будет включать в себя следующие основные блоки:

  1. Основной родительский элемент, background которого похож на лист тетрадки в клетку.
  2. Два игровых поля — игрока, где мы будем расставлять свои корабли и контролировать выстрелы компьютера, и компьютера, где мы будут отмечаться наши попадания и промахи. Им задаётся background в виде рамки размером 10х10 клеток с буквенным обозначением строк и цифровым обозначением колонок.
  3. Контейнер с инструкцией по ручной расстановке кораблей и набором кораблей, которые необходимо перетащить на своё игровое поле.
  4. Два блока, верхний и нижний, для вывода информационных сообщений.
  5. Кнопка запуска игры.
Читайте также:  Можно ли взломать айпад

Первоначально, при загрузке страницы, в контейнере инструкции отображаются только элементы для выбора способа размещения кораблей:
— рандомное размещение при помощи js-скрипта;
— самостоятельное размещение игроком.
Кнопка запуска игры изначально не видна. Она появится только после того, как игрок разместит свои корабли.

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

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

2 ответа 2

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

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

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

Читайте также:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector