На главную Статьи Письмо мне Реализация игры "Морской бой"

Список необходимой литературы

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

Эта небольшая статья может оказаться интересна тем, кто увлекается программированием и хочет узнать новые алгоритмы или решения новых задач. Речь пойдет о реализации игры "Морской бой" (подобной той, что можно скачать) на Делфи, а точнее, на Паскале, т.к. вопросов, связанных с организацией интерфейса, мы касаться не будем. Если Вас не устраивает язык Pascal, то можете перевести представленный ниже код на любой другой язык. Выбор пал именно на Паскаль по двум причинам: во-первых, игра была написана на нем; во-вторых, он наиболее нагляден и идеально подходит для представления алгоритмов. Сразу оговорюсь, что полный исходный текст программы выложен не был, т.к. эту игру я писал достаточно давно, когда еще учился в школе, и код получился достаточно запутанным и непонятным (тогда я так писал). Тем не менее, если Вам очень нужны исходники, напишите мне, и я вышлю их по мылу.

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

Алгоритм размещения кораблей на игровом поле

Игровое поле нужно как-то хранить в памяти компьютера. Наиболее простая реализация - в виде матрицы 10x10 клеток (ячеек). Определим соответствующий тип и переменные, которые нам понадобятся: 


type TPole = array[1..10,1..10] of Integer;
var Pole: TPole;

Обусловимся, что пустая ячейка будет иметь значение -1, а ячейка, в которой находится корабль: 0. Перед началом процесса размещения кораблей необходимо очистить поле. Помимо этого надо еще и обновить счетчик случайных чисел, что бы добиться реальной случайности позиций флота компьютера. Все эти действия лучше оформить в виде отдельной процедуры:


procedure Init (var Pole: TPole);
var X, Y: Integer;
begin
  Randomize;
  for X := 1 to 10 do
    for Y := 1 to 10 do
      Pole[X,Y] := -1;
end; {proc Init}

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


function Freedom (x, y: Integer; Pole: TPole): Boolean;
const d: array[1..8,1..2] of Integer =
      ((0,1),(1,0),(0,-1),(-1,0),(1,1),(-1,1),(1,-1),(-1,-1));
var i: Integer;
    dx, dy: Integer;
begin
  if (x > 0) and (x < 11) and (y > 0) and (y < 11) and (Pole[x,y] = -1) then
  begin
    for i := 1 to 8 do
    begin
      dx := x + d[i,1];
      dy := y + d[i,2];
      if (dx > 0) and (dx < 11) and (dy > 0) and (dy < 11) and (Pole[dx,dy] > -1) then
      begin
        Result := False;
        Exit;
      end; {if}
    end; {for}
    Result := True;
  end else Result := False;
end; {func Freedom}

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


procedure Ships (var Pole: TPole);
var N, M, i: Integer;
    x, y, kx, ky: Integer;
    B: Boolean;
begin
  Init (Pole);
  for N := 3 downto 0 do
    for M := 0 to 3 - N do
    repeat
      x := Random (10) + 1;
      y := Random (10) + 1;
      kx := Random (2);
      if kx = 0 then ky := 1
                else ky := 0;
      B := True;
      for i := 0 to N do
        if not Freedom (x + kx * i, y + ky * i, Pole) then B := False;
      if B then
        for i := 0 to N do
          Pole[x+kx*i,y+ky*i] := 0;
    until B;
end; {proc Ships}

Это, собственно, и все, что касается размещения кораблей компьютера. Теперь достаточно сделать вызов: Ship (Pole); и корабли будут случайным образом расставлены по своим местам. Подобным образом можно помочь пользователю, что бы он каждый раз не тратил время на эту операцию, вызвав Ship (Play); где Play - поле игрока (тип TPole).

Стратегия игры компьютера

Задача заключается в разработке алгоритма, по которому компьютер сможет играть в "Морской бой" с максимальным качеством и при этом не подглядывая расположение флота игрока. Дополнительное и очевидное условие: при каждой новой игре вне зависимости от размещения сил противника компьютер должен играть по-разному, т.е. его ходы должны быть не предсказуемы. Необходимо вспомнить правила игры: участники поединка делают ходы поочередно, причем, если один из игроков попадает по кораблю соперника, то он получает право следующего хода. Если реализовать поиск цели компьютером в виде отдельной процедуры, то надо как-то научить его запоминать исходы прошлых выстрелов, чтобы адекватно произвести следующий. Из этого факта вытекает, что самое простое и рациональное решение данной проблемы можно оформить в виде конечного автомата, наиболее точно описывающего последовательность действий. Если Вы не знаете теорию автоматов, то можете прочесть соответствующую литературу, ссылку на которую можно найти в моем списке литературы. Можно выделить три состояния:

  1. прострел игрового поля по случайным координатам до попадания по кораблю, после чего переход во второе состояние;
  2. обстрел вокруг подбитой ячейки поля для определения направления корабля (вертикальное или горизонтальное), после очередного попадания - переход в третье состояние;
  3. расстрел корабля в полученном направлении до полного его уничтожения, после чего переход в первое состояние.

И так, вся игра зациклена на трех основных действиях: прострел, обстрел и расстрел. Все эти действия должны продолжаться до тех пор, пока у одной из сторон не будут уничтожены все корабли.

Компьютеру потребуется еще одно поле, на котором он будет вести игру. Назовем его Play. Помимо этого нужно помнить, какие корабли остались у игрока, а какие уже разбиты. Объявим все необходимые переменные:


var Play: TPole;
    Kor: array[1..4] of Integer;
    State: Integer;// состояние автомата
    Len: Integer;// кол-во подбитых палуб текущего корабля
    Pkx, Pky: Integer;// направление удара
    Px, Py: Integer;// позиция попадания

Перед началом игры надо настроить все значения. Это удобно сделать в отдельной процедуре:


procedure Start;
var I: Integer;
begin
  Init (Play);
  Ships (Pole);
  State := 1;
  for I := 1 to 4 do
    Kor[I] := 5 - I;
end; {proc Start}

Предположим, что у нас есть функция, которая выдает истину, если в ячейки (x,y) игрока стоит корабль и ложь в противном случае: function Killed (x, y: Integer): Boolean;. Еще потребуется функция, определяющая длину самого большого корабля игрока:


function MaxShip: Integer;
var i: Integer;
begin
  for i := 1 to 4 do
    if Kor[i] > 0 then Result := i;
end; {func MaxShip}

И функция, определяющая проигрыш юзера:


function GameOver: Boolean;
var I: Integer;
begin
  for I := 1 to 4 do
    if Kor[I] > 0 then
    begin
      Result := False;
      Exit;
    end; {if}
  Result := True;
end; {func GameOver}

Все вспомогательные подпрограммы готовы и можно приступить к реализации самого автомата. Для большей наглядности каждое состояние оформим в виде отдельной процедуры. И так, все по порядку.


Прострел. На этом этапе компьютер должен поймать какой-либо из кораблей противника. Для этого он будет стрелять по произвольным незанятым клеткам поля игрока. Гораздо эффективнее сначала разделаться с большими кораблями, поэтому выбирая координаты для выстрела надо проверять, что бы в этой позиции мог разместиться самый большой из оставшихся кораблей. Процесс прекращается, как только произойдет попадание. Обозначим подбитую часть корабля значением 1, а промах -2 соответствующей ячейки поля. Если у игрока остались только однопалубные корабли, то этим попаданием корабль уничтожен полностью и обстреливать его нет смысла. В противном случае надо перейти ко второму состоянию. Приведем код описанной функции:


function State1 (var x, y: Integer): Boolean;
var k, i, n, m: Integer;
    B: Boolean;
    tmp: Integer;
begin
  repeat
    repeat
      x := Random (10) + 1;
      y := Random (10) + 1;
    until Freedom (x, y, Play);
    Pkx := Random (2);
    Pky := Pkx - 1;
    for m := 1 to 2 do
    begin
      i := 0;
      k := 0;
      for n := 1 to 2 do
      begin
        while Freedom (x + Pkx * i, y + Pky * i, Play) do
        begin
          Inc (k);
          Inc (i);
        end; {while}
        Pkx := -Pkx;
        Pky := -Pky;
        i := 1;
      end; {for}
      B := k >= MaxShip;
      if B then Break;
      tmp := Pkx;
      Pkx := Pky;
      Pky := tmp;
    end; {for}
  until B;
  Result := Killed (x, y);
  if Result then
  begin
    Px := x;
    Py := y;
    Len := 1;
    if MaxShip > 1
      then State := 2
      else Dec (Kor[Len]);
  end; {if}
end; {func State1}

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


Обстрел. На этом шаге задача заключается в определении направления пойманного корабля. Для этого надо обстрелять четыре ячейки (если они свободны), которые могут служить продолжением. В случае, когда все четыре клетки обстреляны, а попадания не произошло (однопалубный корабль), надо перейти к первому состоянию. Если в какой-то момент удалось подбить еще одну палубу противника, то можно переходит к расстрелу данного корабля, т.к. его направление стало известно. Аналогично первому состоянию, если у игрока остались корабли не более двух палуб, то этим попаданием корабль уничтожен полностью и надо вернуться к прострелу. Посмотрим, как все это выглядит:


function State2 (var x, y: Integer): Boolean;
var Old: ShortInt;
    tmp: Integer;
    k: Integer;
begin
  Old := Play[Px,Py];
  Play[Px,Py] := -1;
  repeat
    if not Freedom (Px + Pkx, Py + Pky, Play) and not Freedom (Px - Pkx, Py - Pky, Play) then
    begin
      tmp := Pkx;
      Pkx := Pky;
      Pky := tmp;
    end; {if}
    if Random (2) = 0 then
    begin
      x := Px + Pkx;
      y := Py + Pky;
    end else
    begin
      x := Px - Pkx;
      y := Py - Pky;
    end; {if}
  until Freedom (x, y, Play);
  Result := Killed (x, y);
  if Result then
  begin
    Len := 2;
    State := 1;
    if MaxShip > 2
      then State := 3
      else Dec (Kor[Len]);
  end else
  begin
    k := 4;
    if not Freedom (Px + 1, Py, Play) then Dec (k);
    if not Freedom (Px - 1, Py, Play) then Dec (k);
    if not Freedom (Px, Py + 1, Play) then Dec (k);
    if not Freedom (Px, Py - 1, Play) then Dec (k);
    if k < 2 then State := 1;
  end; {if}
  Play[Px,Py] := Old;
end; {func State2}

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


function State3 (var x, y: Integer): Boolean;
var Old: ShortInt;
    i: Integer;
    B: Boolean;
begin
  for i := 1 to 2 do
  begin
    x := Px;
    y := Py;
    while Play[x,y] = 1 do
    begin
      Inc (x, Pkx);
      Inc (y, Pky);
    end; {while}
    Old := Play[x-Pkx,y-Pky];
    Play[x-Pkx,y-Pky] := -1;
    B := Freedom (x, y, Play);
    Play[x-Pkx,y-Pky] := Old;
    if B then Break;
    Pkx := -Pkx;
    Pky := -Pky;
  end; {for}
  if B then
  begin
    Result := Killed (x, y);
    if Result then
    begin
      Inc (Len);
      if Len = MaxShip then
      begin
        Dec (Kor[Len]);
        State := 1;
      end; {if}
    end;
  end else
  begin
    Dec (Kor[Len]);
    State := 1;
    Result := State1 (x, y);
  end; {if}
end; {func State3}

Осталось собрать все это в одной процедуре, которая будет контролировать результат выстрела и обеспечивать повторный ход при попадании:


procedure Comput;
var x, y: Integer;
    Kill: Boolean;
begin
  repeat
    case State of
      1: Kill := State1 (x, y);
      2: Kill := State2 (x, y);
      3: Kill := State3 (x, y);
    end; {case}
    if Kill then Play[x,y] := 1
            else Play[x,y] := -2;
  until not Kill or GameOver;
end; {proc Comput}

Можно заметить, что функция Killed вызывается ровно один раз при каждом ходе компьютера. От сюда следует, что компьютер не подглядывает расположение кораблей игрока, т.к. другой возможности узнать о состоянии какой-либо ячейки поля юзера у него нет. В этом можно убедиться на практике, собрав все эти части кода вместе и сделав консольное приложение, в котором функция Killed спрашивала бы у игрока, попал компьютер или промазал. Все это легко с минимальными изменениями реализовать на Turbo Pascal 7.0, готовый вариант можно скачать (8K), в архиве исходный текст и откомпилированная программа.

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

Остается пожелать Вам удачи в реализации данной игры и в разработке новых программ!


Counter CO.KZ
Hosted by uCoz