Теория и практика создания компьютерных игр
Просматривая в печатных изданиях колонки новостей о выходе новых игрушек не только Там (за границами бывшего СССР), но и в России, на Украине, невольно задаешься вопросом: "А где же наши белорусские игры???". Может быть, сказывается нехватка материала по соответствующей тематике?
Данный цикл статей посвящен в первую очередь тем, кто занимается созданием игр и тем, кому просто интересно, что внутри этой игры и как это работает. В статьях я попытаюсь обобщить наиболее интересный и полезный материал о программировании игр, собранный мной из различных источников, который во многом может помочь не только новичкам, но и профессионалам.
Материал сосредоточен не на конкретной реализации алгоритмов с помощью определенного языка программирования, а именно на подробном описании алгоритма с примерами и иллюстрациями. Изучив и разобравшись, как работает алгоритм, каждый из вас сможет без труда реализовать его на своем любимом языке программирования, будь то СИ, Pascal или какой-нибудь другой.
ЧАСТЬ 1.
Алгоритмы обхода препятствий в играх (Pathfinding)
Задача нахождения пути между двумя произвольными точками A и B на игровой карте с произвольно расположенными препятствиями (либо с динамически изменяемыми) характерна для такого популярного жанра игр, как стратегии. Однако эта задача может возникать как подзадача в других различных жанрах (RPG, Adventure, логических играх). В стратегиях, выбрав группу юнитов и дав им задание проследовать к логову врага, мы хотим видеть, как наши воины без особых проблем, огибая препятствия, дойдут до
цели. За то, насколько хорошо и зрелищно им это удастся, как раз и отвечает алгоритм нахождения пути (по-английски PATHFINDING). Чем эффективней он сделан, тем больше юнитов без "особых тормозов" смогут передвигаться по карте и находить путь к цели, не застревая в каждой точке игрового поля.
волновой алгоритм
Этот алгоритм нахождения пути между двумя произвольными точками A и B позаимствован из электроники, там он применяется при разводке печатных плат. Однако с небольшими изменениями он с успехом может использоваться и в играх, в которых необходима не скорость работы алгоритма, а сам факт нахождения именно кратчайшего пути между двумя точками.
Зачем нужен именно кратчайший путь? Дело в том, что в некоторых играх (в основном это Turn Based Strategies, например, UFO 1-3) от длины маршрута будут зависеть затраченные на перемещение игрового персонажа единицы времени (на один ход игроку дaется определенное количество условных единиц времени). Следовательно, чем оптимальней будет найденный маршрут, тем быстрее игровой персонаж доберется до цели. Работу этого алгоритма вы также наверняка наблюдали в такой игре, как Colour Lines и ее многочисленных клонах. В Colour Lines мы передвигаем шарики из одной точки в другую. Нам важен лишь сам факт возможности или невозможности перемещения шарика, но и в этой игре будет приятнее смотреться, если шарик направится куда надо, а не будет загадочными зигзагами перемещаться по полю.
Итак рассмотрим вкратце работу волнового алгоритма. Предположим, у нас в игре есть игровое поле (обычно заданное в виде массива, элементы которого обозначают предметы, препятствия, игрока, противников и т.п. подробнее об этом в последующих статьях).
Массив игрового поля: Game_Map[Map_Y][Map_X], где
Map_Y размер игрового поля по вертикали, считая с нулевого элемента (если Map_Y=9, то размер будет 10 элементов от 0 до 9);
Map_X размер игрового поля по горизонтали;
Каждый элемент игрового поля имеет множество свойств, однако нас интересует только одно свойство — проходимость или непроходимость элемента массива (клетки). Создавая игровое поле, каждый сам решает, как выделить проходимые или непроходимые элементы. Например, можно считать, что элементы игрового поля со значениями от 0 до 63 непроходимы, а остальные от 64 до 255 проходимы,
(это в случае, если значения элементов игрового поля лежат в диапазоне от 0 до 255). Далее, имеется некоторая стартовая точка, где находится персонаж вашей игры, и конечная точка, которую ему необходимо достигнуть:
Start_X, Start_Y соответственно X и Y координаты стартовой точки A;
End_X, End_Y соответственно X и Y координаты финишной точки B;
Примем условие, что ходить персонаж может только по четырем направлениям: вперед (вверх), назад (вниз), влево, вправо. Нужно переместить героя от места старта к финишу за наименьшее количество ходов, если перемещение, заданное начальной точкой A и конечной B, вообще возможно.
Алгоритм нахождения кратчайшего маршрута между точками A и B довольно прост:
1. создаем рабочий массив Temp_Map[Map_Y][Map_X] равный по размеру массиву игрового поля Game_Map[Map_Y][Map_X].
2. каждому элементу нашего рабочего массива Temp_Map[i_y][i_x], где
i_y от 0 до Map_Y;
i_x от 0 до Map_X;
присваиваем некоторые значения, которые зависят от свойств элементов игрового поля Game_Map[i_y][i_x] по следующим правилам:
а) если поле Game_Map[i_y][i_x]непроходимо, то Temp_Map[i_y][i_x]=255;
б) если поле Game_Map[i_y][i_x]проходимо, то Temp_Map[i_y][i_x]=254;
в) если поле Game_Map[i_y][i_x] является конечной финишной позицией перемещения персонажа, то
Temp_Map[i_y][i_x]=0;
г) если поле Game_Map[i_y][i_x] является стартовой позицией перемещения персонажа, то
Temp_Map[i_y][i_x]=253;
3. "распространяем волну". Для этого вначале вводим переменную:
W_c — счетчик распространения волны.
Также вводим константу:
W_s — которую устанавливаем равной максимальному значению распространения волны.
Присваиваем начальное значение переменной W_c=0
4.0 теперь построчно просматриваем наш рабочий массив Temp_Map[i_y][i_x], организуя два вложенных цикла: по индексу массива i_y от 0 до Map_Y, по индексу массива i_x от 0 до Map_X.
4.1 если Temp_Map[i_y][i_x] равен W_c, то просматриваем соседние элементы массива: Temp_Map[i_y+1][i_x], Temp_Map[i_y-1][i_x], Temp_Map[i_y][i_x+1], Temp_Map[i_y][i_x-1] по следующему правилу:
а) — если Temp_Map[i_y+1][i_x] = 253, то переходим к пункту 5;
— если Temp_Map[i_y+1][i_x] = 254, то выполняем присваивание
Temp_Map[i_y+1][i_x] = W_c+1;
— во всех остальных случаях Temp_Map[i_y+1][i_x] остается без изменений;
б) аналогично поступаем с Temp_Map[i_y-1][i_x]
в) аналогично поступаем с Temp_Map[i_y][i_x+1]
г) аналогично поступаем с Temp_Map[i_y][i_x-1]
4.2 по завершению построчного просмотра всего массива увеличиваем W_c на 1
(W_c=W_c+1)
4.3 если W_c>W_s, то считается, что маршрут не найден. Осуществляется выход из программы.
4.4 переходим к пункту 4.0
5. этап построения маршрута для перемещения персонажа.
5.1 присваиваем переменным path_y и path_x значения координат стартовой позиции (точки A)
5.2 с четырех сторон от позиции Temp_Map[path_y][path_x] ищем элемент с наименьшим значением (т.е. просматриваем Temp_Map[path_y+1][path_x], Temp_Map[path_y-1][path_x], Temp_Map[path_y][path_x+1], Temp_Map[path_y][path_x-1]).
5.3 координаты этого элемента заносим в переменные path_y1, path_x1
5.4 совершаем перемещение персонажа по игровому полю из позиции
(path_y,path_x) в позицию (path_y1,path_x1)
5.5 если Temp_Map[path_y1][path_x1] = 0, то переходим к пункту 6
5.6 присваиваем переменные: path_y=path_y1; path_x=path_x1;
5.7 переходим к пункту 5.2
6. Ура! Персонаж прошел от стартовой до финишной позиции по кратчайшему пути!
Для тех, кто не совсем понял принцип работы данного алгоритма, приведу небольшие комментарии.
пункт 1.
на СИ, чтобы создать массив Temp_Map, пишем что-нибудь типа
int Temp_Map[Map_Y][Map_X].
В принципе, если игровое поле Game_Map имеет большие размеры, то можно выделять некоторое "окно", в которое попадают стартовая и финишная точка, и вести работу лишь с этой частью поля, для того чтобы ограничить вычисления.
пункт 2.
Желательно чтобы рабочий массив Temp_Map был изначально заполнен числом 254, тогда, проходясь по элементам массива игрового поля Game_Map, определяем только непроходимые клетки и соответственно заполняем их числом 255 в нашем рабочем массиве Temp_Map. В конце цикла заносим в массив стартовую и финишную позиции (A и B) благо они у нас известны: Temp_Map[Start_Y][Start_X]=253;
Temp_Map[End_Y][End_X]=0);
Чтобы задать свойства элементов игрового поля Game_Map, можно в каждом элементе выделить бит, отвечающий за проходимость/непроходимость данной клетки, или просто разделить элементы на группы: от 0 до 63 непроходимы, старше — проходимы.
пункт 3.
переменная W_s служит для того, чтобы программа не зациклилась в случае, если между стартом и финишем лежит непреодолимое препятствие и маршрута не существует. Ее величина подбирается экспериментально (например, может зависеть от свойств перемещаемого персонажа). Однако величина W_s в данном
описании алгоритма не может превышать 253, так как стартовая точка имеет такое же значение.
пункт 4.
На ассемблере можно не организовывать два вложенных цикла, так как массив в памяти хранится как непрерывная цепочка байт, следующих друг за другом. Еще одно важное дополнение: можно не просматривать весь массив в поисках элемента равного W_c, а просто заносить в дополнительный массив координаты точек, входящих в последнюю волну, тогда пункт 4.1 сведется к просмотру только этих
точек, что существенно поднимет быстродействие. Кроме того, в пункте 4.1 адреса соседних элементов можно не вычислять по сложным формулам, а задать числовыми смещениями. Например, для карты размером 64x64 элемента смещение соседних клеток будет (-1,+1,-64,+64).
пункт 5.
Чтобы наш персонаж смог ходить по диагонали, в этом пункте необходимо в первую очередь просмотреть четыре соседние диагональных элемента.
К достоинствам волнового алгоритма можно отнести:
1. простота реализации алгоритма;
2. практически идеальный короткий путь между точками;
К недостаткам волнового алгоритма можно отнести:
1. невысокая скорость нахождения маршрута;
2. необходимость во временном массиве размером во всю игровую карту;
В качестве улучшенного варианта данного алгоритма можно попробовать так называемую "двойную волну", когда распространение волны начинается со стартовой и финишной точки одновременно. Тогда маршрут будет состоять из двух частей:
1. от старта до точки пересечения волн;
2. от точки пересечения волн до финишной точки;
Реализация алгоритма "ДВОЙНОЙ ВОЛНЫ":
Пункты 1 и 2 без изменений.
3. "распространяем волну". Для этого вначале вводим две переменных:
W_c1 — счетчик распространения волны от стартовой точки;
W_c2 — счетчик распространения волны от финишной точки;
Также вводим константу:
W_s — которую устанавливаем равной максимальному значению распространения волны.
Присваиваем начальное значение переменным W_c1=253; W_c2=0;
4.0 теперь построчно просматриваем наш рабочий массив Temp_Map[i_y][i_x], организуя два вложенных цикла: по индексу массива i_y от 0 до Map_Y, по индексу массива i_x от 0 до Map_X.
4.1.0 если Temp_Map[i_y][i_x] равен W_c1, то просматриваем соседние элементы массива: Temp_Map[i_y+1][i_x], Temp_Map[i_y-1][i_x], Temp_Map[i_y][i_x+1], Temp_Map[i_y][i_x-1] по следующему правилу:
а) — если Temp_Map[i_y+1][i_x] = W_c2, то переходим к пункту 5;
— если Temp_Map[i_y+1][i_x] = 254, то выполняем присваивание
Temp_Map[i_y+1][i_x] = W_c1-1;
— во всех остальных случаях Temp_Map[i_y+1][i_x] остается без изменений;
б) аналогично поступаем с Temp_Map[i_y-1][i_x]
в) аналогично поступаем с Temp_Map[i_y][i_x+1]
г) аналогично поступаем с Temp_Map[i_y][i_x-1]
4.1.1 если Temp_Map[i_y][i_x] равен W_c2, то просматриваем соседние элементы массива: Temp_Map[i_y+1][i_x], Temp_Map[i_y-1][i_x], Temp_Map[i_y][i_x+1], Temp_Map[i_y][i_x-1] по следующему правилу:
а) — если Temp_Map[i_y+1][i_x] = W_c1, то переходим к пункту 5;
— если Temp_Map[i_y+1][i_x] = 254, то выполняем присваивание
Temp_Map[i_y+1][i_x] = W_c2+1;
— во всех остальных случаях Temp_Map[i_y+1][i_x] остается без изменений;
б) аналогично поступаем с Temp_Map[i_y-1][i_x]
в) аналогично поступаем с Temp_Map[i_y][i_x+1]
г) аналогично поступаем с Temp_Map[i_y][i_x-1]
4.2 по завершению построчного просмотра всего массива уменьшаем W_c1 на 1 и увеличиваем W_c2 на 1
(W_c1=W_c1-1; W_c2=W_c2+1)
4.3 если W_c2>W_s, то считается, что маршрут не найден. Осуществляется выход из программы.
4.4 переходим к пункту 4.0
5. этап построения маршрута для перемещения персонажа.
5.1
ЕслиTemp_Map[i_y][i_x](координаты из пункта 4)= W_c1, то A1_x=i_x; A1_y=i_y; с четырех сторон от позиции Temp_Map[A1_y][A1_x] (Temp_Map[A1_y+1][A1_x], Temp_Map[A1_y-1][A1_x], Temp_Map[A1_y][A1_x+1], Temp_Map[A1_y][A1_x-1]) ищем элемент равный W_c2 и присваиваем его координаты переменным B1_x; B1_y;
Иначе (Temp_Map[i_y][i_x]=W_c2), то B1_x=i_x; B1_y=i_y; с четырех сторон от позиции Temp_Map[B1_y][B1_x], (Temp_Map[B1_y+1][B1_x], Temp_Map[B1_y-1][B1_x], Temp_Map[B1_y][B1_x+1], Temp_Map[B1_y][B1_x-1]) ищем элемент равный W_c1 и присваиваем его координаты переменным A1_x; A1_y;
5.2 Строим маршрут из двух отрезков, занося координаты в дополнительный массив:
1. от точки A1 до А, находя наибольшее значение вокруг точки A1 (Temp_Map[A1_y+1][A1_x], Temp_Map[A1_y-1][A1_x], Temp_Map[A1_y][A1_x+1], Temp_Map[A1_y][A1_x-1])
2. от точки B1 до B, находя наименьшее значение вокруг точки B1 (Temp_Map[B1_y+1][B1_x], Temp_Map[B1_y-1][B1_x], Temp_Map[B1_y][B1_x+1], Temp_Map[B1_y][B1_x-1])
5.3 Перемещаем персонажа по координатам из дополнительного массива от стартовой до финишной точки;
6. Ура! Персонаж прошел от стартовой до финишной позиции по кратчайшему пути!
На этот раз все.
В последующих статьях будут рассмотрены другие, более быстрые алгоритмы нахождения пути, которые с успехом могут быть использованы в real-time стратегиях.
Подготовлено с использованием материала статьи В.С. Медноногова из электронного журнала ZX-Format.
Максим Жириков