Не совсем обычная игра «Морской бой» на JavaScript

Когда-то давно я, как и большинство начинающих программистов, хотел написать компьютерную игру. Выбор пал на «Морской бой» — игру простую, но не до тривиальности. Я начал с разработки теории (как именно должен выбирать себе цель «искусственный интеллект»). Затем мне стало интересно изобрести собственную модификацию правил. В моём варианте не было обычных двух полей, а корабли обеих сторон расставлялись на одном большом поле вперемешку. Как это возможно, я расскажу ниже.

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

В получившуюся игру можно играть как мышью на настольном компьютере, так и на современном планшете или смартфоне, хотя графика, безусловно, чересчур проста для XXI века.

Играть сейчас

Нажмите на кнопку, чтобы запустить игру. Требуется браузер с поддержкой HTML5 (то есть практически любой современный, в том числе должен работать IE версии выше 9). Игра поддерживается только для одного игрока против компьютера.

Отмечу, что на планшете iPad (в любом браузере) почему-то наблюдается неприятное моргание экрана после каждого хода. Я пока не могу разобраться, в чём дело. В настольных браузерах такого эффекта нет.

Правила игры

Имеется одно большое прямоугольное поле. Размер поля выбирается случайным образом — я заложил выбор случайного числа в промежутке от 10 до 20 включительно. Однако общая площадь поля не может быть меньше 200 и больше 250 ячеек. На маленьком поле корабли не поместятся, на большом игра будет слишком долгой и скучной.

Расстановкой кораблей перед началом матча занимается компьютер. В отличие от человека компьютер «умеет» быть честным, то есть он не будет в процессе игры использовать информацию о расположении кораблей противника.

Набор кораблей традиционный: 1 размером 4 клетки, 2 по 3 клетки, 3 по 2 и 4 по одной. Чтобы было веселее, я добавил пару специальных объектов — плавучих мин. Если кто-то из игроков вместо вражеского корабля попадает на мину, то компьютер случайным образом «подбивает» (или «убивает», если корабль занимает одну ячейку) корабль этого игрока.

Игроки ходят по очереди, по одному выстрелу за ход (вне зависимости от его результативности — видел я модификации, где результативный ход даёт право на дополнительный выстрел). Игра заканчивается, если у одной из сторон не осталось «живых» кораблей (мины не считаются).

Помимо своих кораблей и мин игрок может видеть на экране «подбитые» или «убитые» корабли противника и те пустые ячейки, по которым он стрелял (ячейки, по которым стрелял компьютер, на экране не отмечаются, иначе партии будут совсем короткими). Аналогично, компьютер «не видит» отметок игрока. Выглядит это примерно так:

Зелёным цветом выделены корабли игрока, красным — «убитые» корабли противника, крестики без рамок отмечают его же «подбитые» корабли. Чёрный шарик — мина игрока (красный фон означает, что она уже «убита»). Наконец, жёлтая ячейка — та, над которой сейчас находится курсор мыши (если играть с сенсорного устройства вроде планшета, то её не будет видно).

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

Как компьютер выбирает цель

Дано: поле для игры «Морской бой» конечного размера, часть ячеек заполнена. Нужно определить, где вероятнее всего можно обнаружить корабль (избежав, естественно, полного перебора всех мыслимых вариантов).

Рассмотрим отдельную ячейку (на рисунке обозначена крестиком). Кружки отмечают те ячейки, в которых не может быть никаких кораблей. Гарантированно непригодной для заполнения является ячейка, которая либо уже была проверена («обстреляна») ранее, либо непосредственно граничит с любой из 8 сторон с собственным или «убитым» вражеским кораблём (мы считаем, что корабли не могут соприкасаться никак, даже углами). Посчитаем, сколькими способами может размещаться корабль, чтобы занимать эту ячейку. Возьмём для примера корабль, состоящий из трёх ячеек. Видно, что в нашем примере существует всего пять разных способов его размещения.

Обобщив эти соображений на всё поле, можно вывести общую формулу.

Обозначим C_N количество кораблей длиной N, L — расстояние от нужной ячейки до ближайшей гарантированно непригодной для заполнения ячейки или до края доски слева, включая исходную ячейку, R — такое же расстояние справа, T — сверху, B — снизу.

Введём дополнительное обозначение для упрощения: M_AB — это наименьшее из чисел A и B.

 Далее, для каждого значения N > 1 можно вывести формулу: ячейка может быть заполнена таким количеством способов:

C_N (M_LN + M_RN + M_TN + M_BN − 2N)

Здесь множитель 2 при N намекает на количество измерений (соответственно, если бы мы играли в трёхмерном пространстве, множитель был бы 3, а число слагаемых вида M_AB было бы равно 6).

Просуммировав эти значения по всем возможным размерам кораблей N (мы обозначим буквой M наибольшую длину корабля, в нашей игре M = 4), мы получим количество способов, которым ячейка может вообще быть заполнена (кроме случая с N = 1, так как единичным «кораблём» может быть заполнена любая ячейка, если она не граничит с «убитым» вражеским или с собственным кораблём игрока):

M
∑	CN (MLN + MRN + MTN + MBN − 2N)
N = 2

Посчитав наибольшие значения этой формулы по всей доске, мы получим самые вероятные расположения кораблей противника. Посчитав наименьшие значения на этапе заполнения доски, мы получим наиболее выгодные для нас позиции собственных кораблей (это условие я не использовал, в этой версии корабли расставляются случайным образом).

Вот и всё. Остаётся добавить условие: если любая из 4 ячеек, граничащих с этой, содержит фрагмент «подбитого» (но не «убитого»!) корабля, то вероятность попасть в неё резко возрастает. Так что если на доске есть такие ячейки, то должны проверяться только они.

---

Вот такая получилась «проба пера». Исходник можно посмотреть в Google Docs здесь [последнее обновление от 19.12.2013] или в JSFiddle [доработано 23.06.2017 с заменой обработчиков событий на addEventListeners].