Проблема преследования в играх: снижение ресурсоемкости решения с помощью метода с предварительной оценкой карт

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ОМСКИЙ НАУЧНЫЙ ВЕСТНИК № 3 (93) 2010
УДК 004. 853
В. А. ГЕРАСИМОВ О. Н. КАНЕВА
Омский государственный технический университет
ПРОБЛЕМА ПРЕСЛЕДОВАНИЯ В ИГРАХ:
СНИЖЕНИЕ РЕСУРСОЕМКОСТИ РЕШЕНИЯ С ПОМОЩЬЮ МЕТОДА С ПРЕДВАРИТЕЛЬНОЙ ОЦЕНКОЙ КАРТ
В статье рассматривается проблема преследования в играх и существующие решения. Авторами предлагается способ решения, основанный на предварительной оценке игровых карт. Данный способ позволяет накапливать знания в процессе игр и использовать их при решении проблемы преследования, что позволяет снизить затраты на решение проблемы.
Ключевые слова: алгоритмы преследования, оценка карт, алгоритмы поиска пути, алгоритм А*.
Постановка задачи
Пусть существует некоторая игровая карта, представленная совокупностью проходимых и непроходимых ячеек. Для большей формализации представим карту как множество равных квадратных ячеек. Таким образом мы можем задать карту в виде следующей матрицы:
с00
с10
сп0
с01
с11
сп1
с0т
с1т
где с=0, если [г,/] ячейка проходима, и с= 1 в противном случае.
Отдельно пометим два участка карты как «вход» и «выход». При этом вход не должен совпадать с выходом. По карте перемещается игрок. Условимся, что задача игрока переместиться из участка, обозначенного как «вход», в участок, обозначенный «выходом». Дополнительно ограничим видимость карты игроком до определенного радиуса R. Кроме этого, по карте перемещается несколько неигровых персонажей (№^, задача которых заключается в преследовании игрока.
Решение проблемы
Прежде всего, приступая к решению данной проблемы, необходимо определить область знаний NPC. В общем случае достаточно ответить на вопрос: «знают» ли NPC местоположение игрока? В зависимости от наличия или отсутствия у неигровых персонажей данной информации будут применяться различные подходы к решению данной проблемы. Рассмотрим оба случая.
NPC «знают» местоположение игрока. Подобная ситуация в понятиях игрового искусственного интеллекта называется сква^методом [1]. Игрок ставится в неравное положение по отношению к неигровым персонажам, и тем самым повышается сложность игры. Проведенный предварительный анализ проблемы показал, что проблема преследования обычно решается двумя основными способами:
— использование алгоритмов поиска пути-
— комбинация алгоритмов поиска пути и алгоритмов преследования.
С точки зрения практической реализации, первый способ является самым простым. При изменении местоположения игрока пути до него просчитываются заново. Подобный подход имеет серьезные недостатки, связанные с большими временными затратами, а также с большим потреблением памяти. Если в качестве алгоритма поиска пути выбран широко распространенный алгоритм А* [2], временные затраты, в худшем случае, растут экспоненциально (при «правильной» эвристике — полиноминально), аналогично экспоненциально растут затраты памяти (рис. 1).
Данный подход был протестирован с помощью тестовой программы, реализующей генерацию карты и работу алгоритма А*. Функционирование тестовой программы заключалось в следующем:
— на первом этапе генерируется карта размером 400 на 240 (общее количество ячеек 96 000). Используемый метод генерации обеспечивает в среднем 42% непроходимых ячеек (на основе 1000 наблюдений) —
— игрок и преследующий его неигровой персонаж размещаются в ячейках [1,1] и [397,237] соответственно-
— при помощи алгоритма А* рассчитывается кратчайший путь от неигрового персонажа до игрока-
— алгоритм использует простую эвристику: оценивается близость просматриваемого узла по отношению к искомому (эвристическая оценка представляет собой сумму модулей разности координат между текущими положениями игрока и NPC) —
— пересчет пути происходит при перемещении игрока в соседнюю ячейку-
— перемещение происходит итерационно: одному перемещению игрока соответствует одно перемещение неигрового персонажа.
Были проведены 30 наблюдений на 30 различных картах. В ходе каждого наблюдения фиксировалось время, затраченное на расчет кратчайшего пути от неигрового персонажа до игрока в начальный момент
Ь
с
пт
1 Г Л & lt-1 = Я 7 Я 9 1Л11 ]? I.Т- 1Я17 1Я 1Ч5П?17?7. ?34 3'-- ?Р?7 7Я7^ ТЛ
Рис. 1. Результаты экспериментов при использовании А*
Рис. 2. Зависимость временных затрат от количества ячеек на карте
игрового времени. Результаты наблюдений приведены на рис. 2.
Среднее время tср «500 мс. При каждом перемещении игрока возникает необходимость пересчета путей. Минимальное количество пересчетов равняется количеству ячеек, входящих в кратчайший путь между входом и выходом. При дальнейшем увеличении размерности карты временные затраты будут расти экспоненциально (рис. 2).
Второй способ более сложный. Путь до игрока вычисляется с помощью алгоритмов поиска пути. Если расстояние между игроком и неигровым персонажем становится меньше Д, то используется более простой и менее ресурсоемкий алгоритм преследования (например, общий алгоритм преследования, описанный в [3]). Эффективность такого метода определяется, прежде всего, величиной радиуса видимости Д и размером карты. В [4] приводится пример использования комбинации алгоритма А* и общего алгоритма преследования. В общем случае это значит, что алгоритм А* выполняется до тех пор, пока игрок не попадает в область видимости неигрового персонажа. В пределах видимости преследование игрока осуществляется при помощи общего алгоритма преследования. Результаты проведенных экспериментов показали двукратное увеличение производительности по сравнение с применением лишь алгоритма А*.
NPC «не знают» местоположение игрока. Методы из данной группы добавляют в игру больший реализм. Данные методы требуют, чтобы неигровые персонажи были в состоянии предсказывать местоположение игрока. В простейшем случае они могут просто двигаться в случайных направлениях. Как только игрок попадает в область видимости не-
игрового персонажа, дальнейшее преследование осуществляется при помощи соответствующих алгоритмов. Таким образом, первоочередной задачей становится задача оценки вероятности появления игрока в той или иной ячейке карты.
Разработанный метод
К разработанному алгоритму на этапе проектирования были выдвинуты следующие требования:
— результатом его работы должна быть матрица весов, каждый элемент которой — вес конкретной ячейки игровой карты-
— алгоритм должен обеспечивать учет предыдущих игровых исходов, т. е. быть самообучающимся-
— первоначальный расчет должен проводиться с учетом положения входа и выхода и структуры карты.
Таким образом, в функционировании алгоритма можно выделить три этапа:
— этап инициализации-
— этап обучения-
— этап корректировок.
Этап инициализации. На данном этапе проводится инициализация матрицы весов. Предполагается, что до этого момента экспериментов не проводилось, т. е. система не располагает информацией о предыдущих наблюдениях. Для целей данного этапа используется алгоритм А*, применяемый для нахождения оптимального пути между входной и выходной вершинами (и в обратном направлении). Особенностью данного алгоритма является тот факт, что просматривается некоторая окрестность вокруг оптимального пути. Этой окрестности и предполагается присваивать первоначальные веса.
Этап обучения. Вычисления на данном этапе происходят в конце каждой игровой сессии. Основ-
ОМСКИЙ НАУЧНЫЙ ВЕСТНИК № 3 (93) 2010 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ОМСКИЙ НАУЧНЫЙ ВЕСТНИК № 3 (93) 2010
ные вычисления происходят в матрице весов А11, которая определяется следующим образом:
Ас
Ап
ak
anQ
Л Л
ankl
где k — это номер игровой сессии (эксперимента).
На элементы матрицы накладываются ограничения:
а// & gt- 0, I = 1, п и / = 1, т.
В ходе игровой сессии игрок покрывает некоторый путь Рк, содержащий 8 вершин из игрового поля. На я накладывается следующее ограничение:
0 & lt- в & lt- п ¦ т.
В конце игровой сессии происходит перерасчет значений в матрице Ак.
ak+i = а ik +ak ¦с, Ujj ~ak -ak с
I an acр с,
где с — дел олнительный 1с оэффициент корректировки и ау+ = 0, если ау — аср & lt- 0, а аССр — среднее значение веса в данном наблюдении, которое вычисляется по следующей формуле:
где с и d — это нижнее и верхнее значения весов в матрице (до нормирования) соответственно. Значения, а и Ь выбираются пользователем.
Применение данного метода возможно по следующему сценарию:
— до начала игровой сессии рассчитывается оценочная матрица-
— выбираются участки карты, появление игрока на которых наиболее вероятно-
— каждый №С «выбирает» себе участок-
— производится поиск путей до этих участков (например, при помощи упомянутого ранее алгоритма А*) —
— при попадании игрока в область видимости №С в ход вступают алгоритмы преследования-
— по завершению игровой сессии полученные результаты обрабатываются описанным методом оценки.
Применение подобного метода прежде всего позволяет сократить затраты на вычисление путей — отпадает необходимость пересчета путей каждый раз при перемещении игрока. По сути, при реализации такого метода №С «ищет» игрока, перемещаясь между ячейками с наибольшими весами.
Заключение
Описанный метод был реализован в компьютерной игре РасНдЫ [6]. На произвольных картах размерности 40 на 40 метод показал свою пригодность. Проведенные наблюдения показали, что на картах такого размера время, затраченное на расчет путей, было меньше примерно в 1,2 раза по сравнению с применение только А* (в случаях, когда NPC знают местоположение игрока). Ожидается, что с увеличением размерности карт выгода от применения метода предварительной оценки карт возрастет.
После вычисления новых весов производится сглаживание весов (по методу экспоненциального сглаживания) и вычисляется матрица прогноза 5с:
А1,
Ас — a + Sc
при k = 1, ¦(a-1) при k & gt- 1,
где, а — коэффициент сглаживания. При, а =1 предыдущие наблюдения полностью игнорируются, а при, а = 0 игнорируются текущие наблюдения. Основные достоинства метода экспоненциального сглаживания:
1) возможность учета весов исходной информации,
2) простота вычислительных операций,
3) гибкость описания различных динамик процессов.
Метод экспоненциального сглаживания дает возможность получить оценку параметров тренда, характеризующих не средний уровень процесса, а тенденцию, сложившуюся к моменту последнего наблюдения [5].
Таким образом, для получения прогноза на основе данного метода необходимо опытным путем подобрать два коэффициента — дополнительный коэффициент корректировки и коэффициент сглаживания.
Этап корректировок. В ходе работы алгоритма возникают ситуации, когда необходимо нормировать значения в матрице весов. Пусть веса должны находиться на отрезке [а- Ь]. Тогда нормированное значение элемента х может быть найдено по следующ ей формуле:
х = (х — с) ¦ + а
d — с
Библиографический список
1. Rabin, Steve. AI Game Programming Wisdom / Steve Rabin. — Charles River Media, 2002.
2. Рассел, С. Искусственный интеллект: современный подход / С. Рассел. -2-е изд.- пер. с англ. — М.: Издательский дом «Вильямс», 2006 — 1408 с.
3. Bourg, David, M. AI for Game Developers / D.M. Bourg, G. Seeman. — O'-Reilly, 2004.
4. Вешкуцев, Н. Д. Анализ алгоритмов преследования и поиска пути / Н. Д. Вешкурцев / / Информационные технологии и автоматизация управления: матер. межвуз. науч. -практ. конф. -Омск: Изд-во ОмГТУ, 2010. — С. 160 — 162.
5. Forex. ru [электронный ресурс] / Метод экспоненциального сглаживания. — Режим доступа: http: //www. forekc. ru/704/ index10. htm, свободный. — Загл. с экрана. — Яз. рус.
6. Paclight: The Game [электронный ресурс] -Режим доступа: http: //paclight. blogspot. com/, свободный. — Загл. с экрана. — Яз. анг.
ГЕРАСИМОВ Владимир Александрович, студент-магистрант кафедры «Автоматизированные системы обработки информации и управления», старший специалист-тестировщик компании Luxoft Professional. Адрес для переписки: e-mail: v.a. gerasimov@gmail. com
КАНЕВА Ольга Николаевна, кандидат физикоматематических наук, доцент кафедры «Автоматизированные системы обработки информации и управления».
Адрес для переписки: e-mail: okaneva@yandex. ru
Статья поступила в редакцию 31. 05. 2010 г.
© В. А. Герасимов, О. Н. Канева
a
a
a
a
k
a
nm
k
k
S

ПоказатьСвернуть
Заполнить форму текущей работой