Алгоритмы используемые в играх.
Игры класса Аrcade охватывают огромную область, имеющую лишь один объединяющий признак, - высокие требования к спинному мозгу. Поэтому практически невозможно описать и проанализировать один алгоритм на всех. В самом деле, что общего между PipeDream и Принцами Персии? Поэтому здесь можно выделить, например, одну большую группу, в которой главный герой перемещается по бесчисленным лабиринтам замков или космических кораблей, дерется на мечах или стреляет из бластера в тучи мерзких существ, выскакивающих из всех дыр и дверей, перепрыгивает ямы и ловушки и подбирает различные полезные или вредные предметы, которые могут пригодиться в дальнейшем или просто приносят очки. Конечная цель здесь бывает различной в игровом смысле - или спасти принцессу, или Вселенную, или найти Волшебную чашу, но внутри игры конечной целью является, как правило, нахождение хорошо спрятанного объекта. Эта группа имеет название “Платформы и лестницы”.
Отметим только, что возможен несколько более общий случай, когда герой передвигается не только по горизонтали и вертикали, как при виде сбоку, но и по вертикали и горизонтали как при виде сверху. Этот тип путешествия в лабиринтах тоже встречается в ряде компьютерных игр.
Итак, рассмотрим возможные структуры данных в типичных platforms & ladders- играх. Во-первых, это сам лабиринт. Он представляется трехмерным массивом (LxNxM). Первое измерение - это список из L уровней, отличающихся друг от друга конфигурацией лабиринтов и их сложностью. Второе и третье измерения описывают двумерный массив размером NхM, определяющий конкретную структуру L-го лабиринта. В реальности параметры M и N могут определять как длину и ширину при виде сверху, так длину и высоту при виде сбоку.
Конкретный элемент массива определяет наличие в месте (i,j) стены и прочих персонажей игры. Для визуализации лабиринта используется специальная таблица связей значений элементов этого массива с кодами спрайтов, служащих для отображения этого элемента на экране. Экран представляет собой прямоугольную матрицу, каждый элемент которой соответствует некоторому элементу игрового массива со сдвигом от начала в зависимости от местоположения героя. Как правило, на экране присутствует не весь лабиринт, а только его маленькая часть. Хотя это может показаться удивительным, но "ВСЕ" игры этого жанра построены именно так.
Хотя герой вроде бы может передвигаться в стороны на 1-2 пиксела, а квадраты изображения имеют размеры не менее 20 пикселов, но здесь нет ошибки. Дело в том, что спрайт героя на экране может быть привязан к точным координатам, но перемещение его по внутреннему массиву программы происходит по дискретным координатам. Если герой смещен относительно подъемника на 5 пикселов, то попытка подняться вверх либо ни к чему не приведет, либо поставит героя "ТОЧНО" в центр лестницы (ее новых позиций в массиве). Вы можете убедиться в этом самостоятельно. Этот принцип является основополагающим и фундаментальным для большинства компьютерных игр, таких как военные, RPG и многих других. Мы еще встретимся с этой идеей в дальнейшем.
Отображение экрана (крайне условное, так как на практике происходит предварительное формирование образа экрана в буфере, подготовительные анимационные процедуры и т.д.) выглядит так:
for I := CurrentScreen.Left
{позиция ^ текущего левогоотображаемого на экран элемента массива}
{позиция V текущего правого отображаемого на экран элемент массива}
to CurrentScreen.Right do
for J := CurrentScreen.Top
{позиция ^ текущего верхнего отображаемого на экран элемента массива}
{позиция V текущего нижнего отображаемого на экран элемента массива}
to CurrentScreen.Bottom do
DrawScreenCell( I-CurrentScreen.Left,J-CurrentScreen.Right,SpriteNum[ Labir[
GameLevel, I, J ] ] );
где SpriteNum - массив, элементами которого являются номера спрайтов, а индексами - значения элементов массива, описывающего лабиринт. Процедура DrawScreenCell получает номера ячейки (I,J) в координатах элементов экрана и рисует соответствующий спрайт. Например, если массив с координатами (50,32) имеет значение 5, что соответствует стене, то в таблице SpriteNum пятым элементом может быть значение 12. По значению 12 процедура DrawScreenCell в позиции экрана (50*CELL_WIDTH,32*CELL_HEIGHT) выведет прямоугольник стены. Вообще таблица SpriteNum нужна только для экономии места, потому что многим элементам лабиринта соответствуют одни и те же изображения. Например, стенам простым и фальшивым (см.ниже).
Координаты экрана, наложенные на массив (CurrentScreen.Left, Top, Right, Bottom) перемещаются вместе с героем при каждом его шаге, либо при его приближении к границам экрана.
Для свободного элемента пространства обычно выбирается значение 0. Стены могут принимать значения подчас из достаточно широкого диапазона, например, обычные и скользкие поверхности, причем это отличие отдельных частей может быть только внутренним, а на экране игрок не обнаружит разницы, пока герой не встанет на такую поверхность. Это достигается элементарными проверками типа
if Labir[ GameLevel, Hero.Pos.X, Hero.Pos.Y ] = SLIDE_FLOOR then
begin { скольжение героя }
end;
Иногда появляются экзотические элементы типа трамплинов, пружин и т.д. Внутренне они ничем не отличаются от тех же скользких поверхностей.
Каждый конкретный код стены напрямую привязывается к его изображению на экране. Некоторые диапазоны значений соответствуют одному изображению, некоторые значения индивидуальны. Например, наклонный пол записан в ячейках игрового поля (5,5),(6,6),(7,7). На экране каждый из этих элементов отображается в виде наклонного участка.
Помимо стен, возможны и другие типы статических элементов. Это в первую очередь лестницы как точки перехода на другой уровень или подъема по вертикальному лабиринту. Они, как и стены, могут иметь ряд кодирующих значений для отличия по внешнему виду, например, лестница со ступеньками, вход в тоннель или висящая веревка.
В многих играх присутствует такой элемент стен как движущиеся платформы. Несмотря на свою принадлежность к типу стен, внутри программы они относятся к совсем другому типу движущихся объектов. Об этом будет сказано ниже.
Двери и ключи или рычаги для их открытия программируются схожим образом. Точка массива со значением “дверь” кодируется двумя значениями. Первое из них соответствует положению “дверь закрыта”, второе - “дверь открыта”. В исходном состоянии игры некоторые из дверей открыты, некоторые закрыты. Состояние “открытости” может как отображаться на экране, так и быть неотличимым от “закрытости”. Когда герой оказывается в точке массива со значением “дверь”, то производит проверка ее открытости или наличия у героя “ключа” для этой двери.
if( Labir[ GameLevel ][ Hero.Pos.X ][ Hero.Pos.Y ] == CLOSED_DOOR &&
Hero.Have( KEY_FOR_CLOSED_DOOR ) )
{
// Открыть дверь
}
Кнопки или рычаги также принимают два значения в зависимости от их положения. Когда герой нажимает на кнопку, то может открыться дверь, которая пока не видна на экране.
// Если герой нажал на кнопку, то перевести ее в другое положение ... Labir[ GameLevel ][ Button.X ][ Button.Y ] = PUSH_DOWN; // и открыть соответствующую дверь: Labir[ GameLevel ][ Button.Door.X ][ Button.Door.Y ] = OPENED_DOOR;
В больших и сложных играх связи между различными кнопками и дверями гораздо сложнее. Там необходимо дополнительно хранить таблицы взаимосвязей между конкретными кнопками, рычагами и открываемыми ими дверями. В качестве элементов таких массивов выступают координаты кнопок и соответствующие им координаты двери (или дверей).
Интересными декоративными элементами являются невидимые или фальшивые стены. Первые отображаются пустым местом, но не дают герою продвигаться дальше. Для этого при проверке возможности перемещения героя в некотором направлении включается дополнительная проверка на наличие впереди невидимой стены. Для фальшивых стен все наоборот. Они отображаются на экране тем же спрайтом, что и настоящие, но не мешают герою проходить сквозь них. При этом они могут как оставаться на месте, так и исчезать. Для этого служат проверки типа:
if Labir[ GameLevel,Hero.Pos.X,Hero.Pos.Y ] = FALSITY_WALL then
begin
{ отметить элемент лабиринта пустым: }
Labir[ GameLevel,Hero.Pos.X,Hero.Pos.Y ] := EMPTY;
{ и сопроводить это грохотом: }
PlayMelody( CRASH_MUS );
end;
Если стена остается на месте, то, очевидно, ничего делать не надо.
Также фиксируется начальное расположение предметов, помогающих или мешающих герою. Это могут быть различные виды оружия (лук, копье, меч), просто сюрпризы с очками, дополнительные жизни или предметы, позволяющие быстрее передвигаться. Они носят объединяющее название PowerUp. Их распределение может либо задаваться сценаристом изначально с помощью редакторов лабиринтов, входящих в обязательный инструментарий при создании подобных игр, либо быть случайным, тогда каждому из предметов ставится в соответствие некоторая величина вероятности появления в свободном месте.
Допустим, если вы хотите разместить примерно пять жизней в лабиринте размером 50 х 50, то исходный текст будет выглядеть примерно так:
const LIFE_PROB = (50*50 / 5); // количество свободного пространства // на 1 жизнь for( i = 0; i < 50; i ++ ) for( j = 0; j < 50; j ++ ) if( random( LIFE_PROB ) == 0 ) Labir[ i, j ] = LIFE_VALUE;
Конечно, в реальности жизней может получиться 3 или 6, но в среднем при большом числе повторов игры их будет 5.
При случайном распределении стен следует использовать вероятности появления в одной точке от 0.4 до 0.6. При этом при значении 0.4 лабиринт будет слишком пустым, а при 0.6 - невозможным для прохода. Значение около 0.55 близко к оптимальному.
Пример заполнения лабиринта случайными стенами:
for x := 1 to N do for y := 1 to M do if random( 100 )Помещая в начало программы вызов функции randomize(), вы зададите каждый раз новое случайное распределение предметов. Для некоторых игр бывает полезным сделать фиксированное распределение, повторяющееся каждый раз при вызове программы. Для этого просто не используйте randomize(). Такой прием обычно используют в игровых автоматах с целью поддержания в человеке желания пройти одну игру до конца, быстро преодолевая уже известные этапы, и выкачивания из него большего количества денег. Оба эти подхода имеют как плюсы, так и минусы.
Преимуществом первого является осмысленная структура лабиринта и расположения в нем предметов, а недостатком - практически полная предопределенность событий. Впрочем, многим игрокам это нравится. При случайном распределении структуры лабиринтов получаются слишком искусственными и “нечеловеческими”. Но опять-таки, и эти варианты нравятся определенным, достаточно большим группам пользователей. На практике используются различные комбинации этих подходов.
Для создания самого лабиринта и его стен привлекаются сценаристы, заранее разрабатывающие структуру переходов и расположение стен, а распределение различных вспомогательных предметов задается случайно. Это позволяет удовлетворить запросы всех групп играющих.
Практически обязательными персонажами игр данного стиля являются монстры-противники. Внутри программы к ним прибавляется также группа пуль (см.ниже) и стен-платформ. Общей их характеристикой является то, что все эти объекты движутся. Их неудобно представлять значениями игрового массива, так как при этом будет тратиться слишком много сил на их поиск в каждый момент времени. Для эффективного решения этой задачи используются вспомогательные списки из объектов “движущийся элемент”. Это могут быть списки указателей на соответствующие структуры, конкретная техника реализации не принципиальна.
В каждом объекте “движущийся элемент” должно быть поле, конкретизирующее тип данного объекта, - платформа, монстр и т.п., его координаты, скорость движения или частота стрельбы, траектория движения и дополнительная информация. Для платформ это может быть диапазон перемещения, для самострелов - дальность и направление выстрела, для роботов - способ реакции на героя (например, нападать только тогда, когда герой вступил в некоторую зону и отставать при выходе из нее), и степень “понимания” обстановки, то есть вероятность правильного выбора направления передвижения. Например, для злых чудовищ, блуждающих по лабиринту в поисках героя, в зависимости от уровня можно задавать различные значения этой величины. Тогда на первом уровне чудовища будут блуждать абсолютно хаотично, на втором - с вероятностью, допустим, 0.2 каждый шаг будет не случайным, а делаться в направлении героя и так далее.
Немаловажен и способ появления монстров. Если лабиринты задаются заранее, то движущиеся монстры могут как расставляться в начале каждой новой игры, так и генерироваться случайным образом за пределами экрана. При этом после уничтожения монстра он вычеркивается из списка движущихся объектов. Параметры частоты и мест появления монстров требуют очень точной настройки, чтобы игра не стала либо слишком простой, либо слишком сложной.
Вот небольшой пример проверки съедания героя монстрами:
for( i = 0; i < Length(MonsterList); i ++ ) if( MonsterList[ i ].Type == KILLER && // проверка типа монстра MonsterList[ i ].Pos.X == Hero.Pos.X && // проверка совпадения координат MonsterList[ i ].Pos.Y == Hero.Pos.Y ) { // Герой погиб }Особо кодируется выход из лабиринта. Его расположение можно задать случайно, но рекомендуется более осторожно отнестись к его местоположению, чтобы он не очутился прямо около героя в начале игры. Около выхода обычно специально размещают более сильного монстра-“босса”.
Ключевым является главный объект “ГЕРОЙ”. Помимо координат его местонахождения он содержит ряд дополнительных характеристик. Это в первую очередь запас энергии или количество жизней, наличие и тип вооружения, запас боеприпасов, а также найденные предметы и очки. Герой передвигается с помощью стрелок или джойстика. Процесс реализации перемещения очевиден. К текущим координатам героя прибавляется соответствующее смещение и для новых координат производятся разнообразные проверки на предмет наличия помех (стен), проваливания в ямы, нахождения различных предметов и т.д. Если передвижение по выбранному направлению невозможно, то восстанавливаются старые координаты.
Достаточно сложным является процесс реализации стрельбы как героя, так и его противников. Для объектов, управляемых программой, прежде всего необходимо подбирать соответствующие значения периодичности стрельбы и точности выстрела. В играх, где после момента выстрела не существует паузы до момента поражения героя (то есть герой не может уворачиваться от выстрелов), дальнейший процесс обработки выстрела несложен. Без проверки всех событий игры рисуется траектория выстрела, проверяется поражение цели, и она либо поражается (вычеркивается из игры или понижается ее энергия), либо выстрел прошел мимо. После этого изображение на экране восстанавливается, и продолжается обычный ход событий. Если же герой может уворачиваться от летящих в него пуль и прочих предметов, то задача усложняется. После выстрела создается динамический объект пули, включаемый в список динамических объектов. Он характеризуется скоростью, направлением движения и типом (копье, лазерный луч и т.д.) Тип нужен для корректного определения размера поражения цели.
Сам алгоритм platforms & ladders-игр похож на алгоритмы из многих других типов игр. Попробуем его описать.
- Проинициализировать все начальные значения в игре, создать текущий уровень лабиринта.
- Опросить клавиатуру или джойстик. Если человек ничего не делает, то перейти к п.5.
- Если передвижение героя, то
- вычислить новые координаты;
- если передвижение вперед возможно, то передвинуть героя, проверить достижение цели и наличие в новой точке других объектов (ключ, платформа, монстр и т.д.) При наличии сделать необходимые действия.
- иначе восстановить старые координаты;
- Если герой выстрелил, то добавить объект “пуля” в список динамических объектов.
- Просканировать список динамических объектов. Для тех, у кого подошла периодичность
действия:
Для объектов типа платформа: вычислить новые координаты, переместиться;
Для объектов типа монстр : вычислить новые координаты, переместиться, проверить наличие жертвы в новой точке, при необходимости совершить нужное действие;
Для объектов типа пуля : переместиться в новую точку. Если она не пуста, то:
- если в ней поражаемая цель, то изменить характеристики цели (понизить запас энергии, вычеркнуть из списка объектов); вычеркнуть себя из списка динамических объектов.
- Перейти к п.2.
Конечно, современные platforms & ladders-игры во многом сложнее приведенного нами алгоритма. Они представляют собой, как правило, сложное сочетание лабиринтной идеологии с крутыми аркадными вставками, менеджментом, но основа их остается неизменной. Многие разновидности и новые версии известных игр являются, по сути, старыми играми с новыми картинками спрайтов и измененным количеством персонажей с различными характеристиками. Сложность этого типа игр сегодня заключается практически только в оптимальном подборе параметров, придумыванию хорошего сюжета и качественного дизайна.
Сегодня появляются новые игры этого жанра, например, DOOM. Качественным их отличием от себе подобных является увеличение числа измерений до трех. Правда, это не сильно меняет структуру программы. Хотя герой теперь имеет возможность перемещаться не дискретно - по квадратам, а непрерывно, то есть как и в реальной жизни, перемещаться в любую доступную точку помещения, но по сути ничего не меняется. Конечно, исчезает базовый массив, описывающий структуру лабиринта, а задача проверки столкновения героя со стенами ложится на программу, но принцип остается схожим. Теперь программа содержит только описания координат стен и их толщин и проверяет допустимость координат героя:
if (Hero.OldPos.X < Wall[ i ].X) and (Hero.NewPos.X Wall[ i ].X)
then
{ попытка пересечь стену ! }
Соответственно появляется по аналогии с списком динамических объектов и список статических объектов (PowerUp List). При этом на каждом шаге героя проверяется его близость к тому или иному предмету и при необходимости совершается соответствующее действие. Некоторые предметы надо специально брать, для чего служит специальная клавиша. Но в целом структура базового алгоритма не меняется. Введение третьего измерения по сути аналогично новым уровням игры, когда подъем наверх имитирует переход на другой уровень или вход в другой лабиринт в обычных играх этого типа. На самом деле создатели игр типа DOOM исповедуют оба подхода. Например, в игре Terminator:Rampage фирмы Bethesda Softworks с 3-Д графикой, практически идентичной Id Software, положение героя тоже дискретно, а расположение комнат и коридоров на каждом из уровней заложены в массив 100х100 элементов. Но на внешнем виде игры этот нюанс никак не сказывается.
Оценка сложности программирования: 5 из 10.