Поиск путей обхода препятствий в играх – классическая задача, с которой приходится сталкиваться всем разработчикам компьютерных игр. Существует ряд широко известных алгоритмов разной степени эффективности. Все они в той или иной степени анализируют взаимное расположение препятствия и игрока, и по результатам принимается то или иное решение по перемещению. Я попытался использовать для решения задачи обхода препятствий обученную нейронную сеть. Своим опытом реализации этого подхода в среде 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 секунд видео). Вряд ли в реальной игре это будет считаться хорошим результатом, так что тут явно есть место для улучшений алгоритма.
Заключение
В целом, задачу удалось решить. Насколько эффективно данное решение – вопрос открытый, и требуются дополнительные исследования. Например, неизвестно, как модель поведёт себя при появлении динамических препятствий (других движущихся объектов). Другой проблемой является отсутствие датчиков столкновения, направленных назад, что приводит с сложностям при обходе комплексных препятствий.
Очевидным дальнейшим развитием идеи нейросетевого алгоритма обхода препятствий мне видится во внедрении обучения. Для этого следует ввести оценку результата принятого решения, и при следующих друг за другом коррекций без существенного изменения положения объекта, оценка должна ухудшаться. По достижении некоторого значения модель должна переходить в режим обучения и, допустим, случайным образом менять принятые решения, чтобы найти выход.
Другой особенностью модели мне представляется вариативность первоначального обучения. Это даёт возможность, к примеру, иметь несколько вариантов поведений для разных моделей без необходимости программирования каждой из них в отдельности. Другими словами, если у нас есть, допустим, тяжёлый танк и лёгкий разведчик, манера избегания препятствий у них может существенно различаться. Для достижения этого эффекта мы используем один и тот же перцептрон, но обученный на разных выборках.
