Главная » Документация » Алгоритмы, применяемые в играх

RSS

Алгоритмы, применяемые в играх

Алгоритмы и игрыОчень интересной темой в компьютерных играх является, в принципе, сам процесс их создания. Это вам скажет практически любой программист. У одного из победителей Борландского конкурса программ был такой девиз: «при создании игры наслаждаешься дважды: когда пишешь программу и когда играешь с ней».

Вообще, по видимому, вряд ли найдется такой программист, который хоть раз в жизни не пытался создать компьютерную игру. У кого-то это получалось, у кого-то нет, но как писать игру, или по крайней мере, как надо было сделать Civilization, чтобы она стала в сто раз интереснее, сможет посоветовать практически любой человек, знающий, что такое Тетрис. В самом деле, игр в компьютерном мире огромное количество, и каждый месяц появляются все новые и новые, но бестселлерами из них становятся только единицы.

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

Поэтому представляет особый интерес анализ коммерческого успеха тех или иных игр с точки зрения сложности как алгоритмов, заложенных в их основу, так и их программирования. Вообще степень сложности программирования игр считается самой высокой. Это объясняется рядом причин, о которых мы скажем ниже. При оценке игр следует принимать во внимание такой факт. Практически все фирмы, занимающиеся разработкой компьютерных игр, имеют готовые библиотеки по таким направлениям, как поддержка быстрой графики, анимация, создание и подключение к программе музыки и т.п. Очевидно, имеются и тщательно охраняемые разработки по поддержке трехмерной графики для создания имитаторов или игр типа DOOM, а также готовые макеты для быстрого создания игр различных жанров. Мы не будем учитывать эти разработки при анализе сложности игр; интерес представляют лишь достаточно оригинальные разработки.

Игры класса Аrcade – семейство «Платформы и лестницы»

Игры типа ArcadeИгры класса Аrcade охватывают огромную область, имеющую лишь один объединяющий признак, – высокие требования к спинному мозгу. Поэтому практически невозможно описать и проанализировать один алгоритм на всех. В самом деле, что общего между PipeDream и Принцами Персии? Поэтому здесь можно выделить, например, одну большую группу, в которой главный герой перемещается по бесчисленным лабиринтам замков или космических кораблей, дерется на мечах или стреляет из бластера в тучи мерзких существ, выскакивающих из всех дыр и дверей, перепрыгивает ямы и ловушки и подбирает различные полезные или вредные предметы, которые могут пригодиться в дальнейшем или просто приносят очки. Конечная цель здесь бывает различной в игровом смысле – или спасти принцессу, или Вселенную, или найти Волшебную чашу, но внутри игры конечной целью является, как правило, нахождение хорошо спрятанного объекта. Эта группа имеет название «Платформы и лестницы»

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

Итак, рассмотрим возможные структуры данных в типичных platforms & ladders- играх. Во-первых, это сам лабиринт. Он представляется трехмерным массивом (LxNxM). Первое измерение – это список из L уровней, отличающихся друг от друга конфигурацией лабиринтов и их сложностью. Второе и третье измерения описывают двумерный массив размером NхM, определяющий конкретную структуру L-го лабиринта. В реальности параметры M и N могут определять как длину и ширину при виде сверху, так длину и высоту при виде сбоку.

Конкретный элемент массива определяет наличие в месте (i,j) стены и прочих персонажей игры. Для визуализации лабиринта используется специальная таблица связей значений элементов этого массива с кодами спрайтов, служащих для отображения этого элемента на экране. Экран представляет собой прямоугольную матрицу, каждый элемент которой соответствует некоторому элементу игрового массива со сдвигом от начала в зависимости от местоположения героя. Как правило, на экране присутствует не весь лабиринт, а только его маленькая часть. Хотя это может показаться удивительным, но «ВСЕ» игры этого жанра построены именно так.

Хотя герой вроде бы может передвигаться в стороны на 1-2 пиксела, а квадраты изображения имеют размеры не менее 20 пикселов, но здесь нет ошибки. Дело в том, что спрайт героя на экране может быть привязан к точным координатам, но перемещение его по внутреннему массиву программы происходит по дискретным координатам. Если герой смещен относительно подъемника на 5 пикселов, то попытка подняться вверх либо ни к чему не приведет, либо поставит героя «ТОЧНО» в центр лестницы (ее новых позиций в массиве). Вы можете убедиться в этом самостоятельно. Этот принцип является основополагающим и фундаментальным для большинства компьютерных игр, таких как военные, RPG и многих других. Мы еще встретимся с этой идеей в дальнейшем.

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

1
2
3
4
for I := CurrentScreen.Left to CurrentScreen.Right do
  for J := CurrentScreen.Top to CurrentScreen.Bottom do
    DrawScreenCell(I-CurrentScreen.Left,J-CurrentScreen.Right,
                   SpriteNum[Labir[GameLevel,I,J]]);

Где:

CurrentScreen.Left – позиция текущего левого отображаемого на экран элемента массива
CurrentScreen.Right – позиция текущего правого отображаемого на экран элемент массива
CurrentScreen.Top – позиция текущего верхнего отображаемого на экран элемента массива
CurrentScreen.Bottom – позиция текущего нижнего отображаемого на экран элемента массива
SpriteNum – массив, элементами которого являются номера спрайтов, а индексами – значения элементов массива, описывающего лабиринт.

Процедура DrawScreenCell получает номера ячейки (I,J) в координатах элементов экрана и рисует соответствующий спрайт. Например, если массив с координатами (50,32) имеет значение 5, что соответствует стене, то в таблице SpriteNum пятым элементом может быть значение 12. По значению 12 процедура DrawScreenCell в позиции экрана (50*CELL_WIDTH,32*CELL_HEIGHT) выведет прямоугольник стены. Вообще таблица SpriteNum нужна только для экономии места, потому что многим элементам лабиринта соответствуют одни и те же изображения. Например, стенам простым и фальшивым (см.ниже).

Координаты экрана, наложенные на массив (CurrentScreen.Left, Top, Right, Bottom) перемещаются вместе с героем при каждом его шаге, либо при его приближении к границам экрана.

Для свободного элемента пространства обычно выбирается значение 0. Стены могут принимать значения подчас из достаточно широкого диапазона, например, обычные и скользкие поверхности, причем это отличие отдельных частей может быть только внутренним, а на экране игрок не обнаружит разницы, пока герой не встанет на такую поверхность. Это достигается элементарными проверками типа

1
2
3
4
if Labir[GameLevel,Hero.Pos.X,Hero.Pos.Y] = SLIDE_FLOOR then
begin
{ скольжение героя }
end;

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

Каждый конкретный код стены напрямую привязывается к его изображению на экране. Некоторые диапазоны значений соответствуют одному изображению, некоторые значения индивидуальны. Например, наклонный пол записан в ячейках игрового поля (5,5),(6,6),(7,7). На экране каждый из этих элементов отображается в виде наклонного участка.

Аркады

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

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

Двери и ключи или рычаги для их открытия программируются схожим образом. Точка массива со значением «дверь» кодируется двумя значениями. Первое из них соответствует положению «дверь закрыта», второе – «дверь открыта». В исходном состоянии игры некоторые из дверей открыты, некоторые закрыты. Состояние «открытости» может как отображаться на экране, так и быть неотличимым от «закрытости». Когда герой оказывается в точке массива со значением «дверь», то производит проверка ее открытости или наличия у героя «ключа» для этой двери.

1
2
3
4
5
if (Labir[GameLevel, Hero.Pos.X, Hero.Pos.Y]=CLOSED_DOOR) and
   (Hero.Have(KEY_FOR_CLOSED_DOOR)) then
begin
{ Открыть дверь }
end;

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

1
2
3
4
5
// Если герой нажал на кнопку, то перевести ее в другое положение ...
Labir[ GameLevel, Button.X, Button.Y ]:= PUSH_DOWN;
// и открыть соответствующую дверь:
 
Labir[ GameLevel, Button.Door.X, Button.Door.Y ]:= OPENED_DOOR;

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

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

1
2
3
4
5
6
7
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, то исходный текст будет выглядеть примерно так:

1
2
3
4
5
const LIFE_PROB = (50*50 / 5);
{ количество свободного пространства на 1 жизнь }
for i:= 0 to 50 do
  for j:= 0 to 50 do
    if (random(LIFE_PROB)= 0 ) then Labir[GameLevel, i, j]:=LIFE_VALUE;

Конечно, в реальности жизней может получиться 3 или 6, но в среднем при большом числе повторов игры их будет 5. При случайном распределении стен следует использовать вероятности появления в одной точке от 0.4 до 0.6. При этом при значении 0.4 лабиринт будет слишком пустым, а при 0.6 – невозможным для прохода. Значение около 0.55 близко к оптимальному. Пример заполнения лабиринта случайными стенами:

1
2
3
4
for x := 1 to N do
  for y := 1 to M do
    if random(100) < 55 then Labir[ GameLevel, x, y ]:=WALL
     else Labir[ GameLevel, x, y ]:= EMPTY;

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

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

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

Страницы : 1 2 3 4 5 6 7