Поиск путей обхода препятствий в играх – классическая задача, с которой приходится сталкиваться всем разработчикам компьютерных игр. Существует ряд широко известных алгоритмов разной степени эффективности. Все они в той или иной степени анализируют взаимное расположение препятствия и игрока, и по результатам принимается то или иное решение по перемещению. Я попытался использовать для решения задачи обхода препятствий обученную нейронную сеть. Своим опытом реализации этого подхода в среде Unity3D я хочу поделиться в этой небольшой статье.
Концепция
В качестве игрового пространства используется ландшафт на основе стандартного Terrain. Столкновения с поверхностью в рамках данной статьи не рассматриваются. Каждая модель снабжена набором коллайдеров, по возможности точно описывающих геометрию препятствий. У модели, которая должна осуществлять обход препятствий, имеются в наличии четыре
датчика столкновений (на скриншоте расположение и дистанция действия датчиков обозначены бирюзовыми линиями). По сути датчиками являются рэйкасты, каждый из которых передаёт в алгоритм анализа расстояние до объекта-столкновения. Расстояние меняется от 0 (объект расположен максимально близко) до 1 (нет столкновения, данное направление свободно от препятствий).
В целом, работа алгоритма обхода препятствий выглядит следующим образом:
- На четыре входа обученной нейросети подаются четыре значения от датчиков столкновения
- Рассчитывается состояние нейросети. На выходе получаем три значения:
a. Сила поворота модели против часовой стрелки (принимает значение от 0 до 1)
b. Сила поворота модели по часовой стрелке (принимает значение от 0 до 1)
c. Тормозящее ускорение (принимает значение от 0 до 1) - К модели прилагаются усилия с соответствующими коэффициентами.
Реализация
Честно говоря, я понятия не имел, получится ли из этой затеи хоть что-нибудь. Первом делом, я реализовал в Unity класс neuroNet. Не буду подробно останавливаться на коде классе, поскольку он представляет собой классический многослойный перцептрон. По ходу дела сразу же возник вопрос в количестве слоёв сети. Сколько их требуется, чтобы с одной стороны обеспечить нужную ёмкость, а с другой – приемлемую скорость расчётов? После череды экспериментов, я остановился на двенадцати слоях (три базовых состояния на четыре входа).
Далее потребовалось реализовать процесс обучения нейронной сети. Для этого пришлось создавать отдельное приложение, где использовался тот же самый класс neuroNet. И теперь во весь рост встала проблема данных для обучения. Первоначально я хотел использовать значения, полученные непосредственно от игрового приложения. Для этого я организовал логирование данных от датчиков, чтобы в дальнейшем для каждого набора значений четырёх датчиков указывать программе обучения правильные значения выходов. Но, посмотрев на получившийся результат, я впал в уныние. Дело в том, что мало для каждого набора четырёх значений датчиков указать адекватное значение, нужно, чтобы эти значения были непротиворечивыми. Это очень важно для успешного обучения нейросети. К тому же не было никакой гарантии, что получившаяся выборка представляла все возможные ситуации.
Альтернативным решением оказалась вручную составленная таблица базовых вариантов значений датчиков и выходов. За базовые варианты были приняты значения: 0.01 – препятствие близко, 0.5 – препятствие на полпути, 1 – направление свободно. Это позволило сократить объём обучающей выборки.
Датчик 1 |
Датчик 2 |
Датчик 3 |
Датчик 4 |
Поворот по часовой | Поворот против часовой | Торможение |
|---|---|---|---|---|---|---|
| 0,01 | 0,01 | 0,01 | 0,01 | 0,01 | 0,01 | 0,01 |
| 0,01 | 0,01 | 0,01 | 0,5 | 0,01 | 0,01 | 0,01 |
| 0,01 | 0,01 | 0,01 | 0,999 | 0,01 | 0,01 | 0,01 |
| 0,01 | 0,01 | 0,5 | 0,01 | 0,999 | 0,01 | 0,01 |
| 0,01 | 0,01 | 0,5 | 0,5 | 0,999 | 0,01 | 0,01 |
| 0,01 | 0,01 | 0,5 | 0,999 | 0,999 | 0,01 | 0,5 |
| 0,01 | 0,01 | 0,999 | 0,01 | 0,999 | 0,01 | 0,5 |
| 0,01 | 0,01 | 0,999 | 0,5 | 0,999 | 0,01 | 0,999 |
| 0,01 | 0,01 | 0,999 | 0,999 | 0,999 | 0,01 | 0,999 |
В таблице приведён небольшой фрагмент обучающей выборки (всего в таблице 81-а строка). Конечным результатом работы программы обучения была таблица весовых коэффициентов, которая сохранялась в отдельный файл.
Результаты
В предвкушении потирая руки, я организовал загрузку коэффициентов в демонстрационную игру и запустил процесс. Но, как оказалось, я сделал для дела явно недостаточно. Со старта тестируемая модель вертелась, утыкалась во все препятствия подряд, как слепой котёнок. В общем, результат оказался очень даже так себе. Пришлось углубиться в исследование проблемы. Источник беспомощного поведения был обнаружен довольно быстро. При в общем-то верных реакциях нейросети на показания датчиков, передаваемые управляющие воздействия оказались слишком сильными.
Решив эту проблему, я столкнулся с новой трудностью – дистанция рэйкаста датчиков. При большой дистанции обнаружения помехи модель совершала преждевременные маневры, которые выливались в значительные искажения маршрута (а то и в непредвиденные столкновения в, казалось бы, уже пройденные препятствия). Маленькая дистанция приводила к одному – беспомощному «утыканию» модели во все препятствия при явном недостатке времени на реагирование.
Чем больше я возился с моделью демонстрационной игры, пытаясь научить её избегать препятствия, тем больше мне казалось, что я не программирую, а пытаюсь научить ребёнка ходить. И это было необычное ощущение! Тем радостнее было видеть, что мои старания приносят ощутимые плоды. В конце концов, несчастный кораблик-ховер, паривший над поверхностью, начал довольно уверенно огибать возникающие на маршруте строения. Настоящие испытания для алгоритма начались, когда я сознательно пытался загнать модель в тупик. Здесь потребовалось менять логику работы с тормозящим ускорением, вносить некоторые поправки в обучающую выборку. Давайте посмотрим на практических примерах, что же получилось в результате.
1. Простой обход одного препятствия
Как видим, затруднений обход не вызвал.
2. Два препятствия (вариант 1)
Модель легко нашла проход между двумя строениями. Лёгкая задача.
3. Два препятствия (вариант 2)
Здания стоят ближе, но модель находит проход.
4. Два препятствия (вариант 3)
Вариант сложнее, но всё ещё решаем.
5. Три препятствия
Задача оказалась решена довольно быстро.
6. Тупик
Тут у модели возникли проблемы. На первых 30 секундах видео показано, что модель беспомощно барахтается в простой конфигурации зданий. Проблема тут скорее всего кроется не столько в нейросетевой модели, сколько в основном алгоритме движения по маршруту — он настойчиво пытается вернуть корабль на курс, несмотря на отчаянные попытки избежать столкновения.
После нескольких неудачных прогонов данной ситуации с разными параметрами, удалось получить положительный результат. С тридцатой секунды видео можно наблюдать, как модель с увеличенной дистанцией датчиков и с более мощным тормозным усилием выбирается из тупика. Для этого ей понадобилось почти пять минут времени (я вырезал эти мучения и оставил только последние 30 секунд видео). Вряд ли в реальной игре это будет считаться хорошим результатом, так что тут явно есть место для улучшений алгоритма.
Заключение
В целом, задачу удалось решить. Насколько эффективно данное решение – вопрос открытый, и требуются дополнительные исследования. Например, неизвестно, как модель поведёт себя при появлении динамических препятствий (других движущихся объектов). Другой проблемой является отсутствие датчиков столкновения, направленных назад, что приводит с сложностям при обходе комплексных препятствий.
Очевидным дальнейшим развитием идеи нейросетевого алгоритма обхода препятствий мне видится во внедрении обучения. Для этого следует ввести оценку результата принятого решения, и при следующих друг за другом коррекций без существенного изменения положения объекта, оценка должна ухудшаться. По достижении некоторого значения модель должна переходить в режим обучения и, допустим, случайным образом менять принятые решения, чтобы найти выход.
Другой особенностью модели мне представляется вариативность первоначального обучения. Это даёт возможность, к примеру, иметь несколько вариантов поведений для разных моделей без необходимости программирования каждой из них в отдельности. Другими словами, если у нас есть, допустим, тяжёлый танк и лёгкий разведчик, манера избегания препятствий у них может существенно различаться. Для достижения этого эффекта мы используем один и тот же перцептрон, но обученный на разных выборках.