Алгоритм реализации работы

2.2 Алгоритм реализации работы

 

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

Игровое поле нужно как-то хранить в памяти компьютера. Наиболее простая реализация - в виде матрицы 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

3. БЛОК - СХЕМА

ЗАКЛЮЧЕНИЕ

В результате выполнения данной курсовой работы был получен игровой программный продукт, названный «Морской бой». Было проведено исследование компонентов программной среды Turbo Pascal 7.0, которые использовались при создании игры.

В результате исследования были выявлены следующие недостатки полученного программного продукта:

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

2.  При полном потоплении корабля это никак не отражается;

3.  Невозможность возврата на несколько ходов назад;

4.  Работоспособность приложения только в среде Windows;

Однако, помимо недостатков, есть и достоинства у этого программного продукта:

1.  Автоматическая расстановка кораблей ;

2.  Программный продукт малотребователен к системным ресурсам компьютера. Минимальная конфигурация: процессор – не ниже Pentium, оперативная память – не ниже 16 Mb, операционная система – Windows 95 / 98/ Me / NT / 2000 / XP.

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1.    Немнюгин С. Turbo Pascal / Учебный курс.– СПб: Питер, 2001.

2.    Сухарев М. Turbo Pascal 7.0. Теория и практика программирования.- СПб.: Наука и техника. 2004.

3.    Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие – М.: Издательство ООО ОМД «Групп», 2002.

4.    Федоренко Ю. Алгоритмы и программы на Turbo Pascal / Учебный курс.– СПб: Питер, 2001.