AI автомобиля в изменчивом мире на примере Ex Machina Докладчик Антон Савин, ведущий программист Targem Studio,

Pathfinding Pathtracking Бой Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин AI автомобиля основные компоненты

Pathfinding Двумерная карта проходимости Практически везде, где есть ландшафт Waypoints Геометрически сложные пространства Ориентированная карта проходимости Казалось, может нам помочь Учитывать скорость при поиске пути Слишком сложно по времени Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Взаимодействие с физическим движком Положением и скоростью машины управляет физический движок. Управлять машиной можно лишь нажатием на газ, тормоз и крутя руль. Объезд препятствий Не все препятствия можно объехать, просто найдя подходящий путь. Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин Pathtracking сложности

Общий алгоритм: while( не доехали ) { ехать к текущей точке();//(1) if( близко к текущей точке ) притормозить();//(2) if( доехали до текущей точки )//(3) { if( текущая точка – последняя ) break; else ++текущая точка; } Замечание: Точки пути должны быть как можно дальше друг от друга, т.е путь надо спрямлять. Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин Pathtracking алгоритм

Повернуть руль в сторону точки, удерживать машину на заданном курсе Ex Machina: простой подход – желаемый угол поворота колес пропорционален углу между направлением «вперед» для машины и направлением до точки пути. Может начаться «вихляние». Если машина развернута задом к точке и скорость мала, то можно развернуться «по трем точкам» со сдачей назад. Пути для улучшения: PID-регуляторы (учитывается не только само отклонение, но также интеграл отклонения за некоторый период времени и производная отклонения) Pathtracking ехать в сторону очередной точки (1) Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Чем больше угол поворота к следующей точке и скорость машины, тем сильнее надо притормаживать и тем раньше надо начать торможение. Если угол поворота невелик, можно совсем не тормозить. Точное значение силы трения на всем пути неизвестно, так как оно зависит от типа ландшафта, от угла наклона и т.п. Считаем, что коэффициент трения не меньше некоторого минимума. Pathtracking притормозить (2) Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Pathtracking доехали до текущей точки (3) Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Препятствия: статические, динамические Статические: деревья, строения Динамические: другие машины, обломки Нужен единый механизм объезда препятствий Почему бы не искать пути так, чтобы препятствия не надо было объезжать? Можно ли препятствия врисовать в карту проходимости? Модификация алгоритма Flocking: считаем для машины вектор steering force (SF) и дальнейшее движение осуществляем, исходя из него. Pathtracking объезд препятствий Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

В простейшем случае (когда нет препятствий) SF равен силе притяжения к очередной точке пути. Pathtracking объезд препятствий Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Препятствия впереди по ходу движения ищем с помощью прямоугольника шириной чуть больше машины и длиной, пропорциональной скорости машины. Сила отталкивания от препятствия направлена под 90° к скорости машины, в сторону от центра препятствия. Pathtracking объезд препятствий Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Существует еще один тип препятствий: стоящие между машиной и точкой пути. Ищем их с помощью соответствующего прямоугольника. Сила отталкивания от таких препятствий перпендикулярна к направлению до точки пути, в сторону от центра препятствия Если любое препятствие близко, то аннулируем силу притяжения к точке пути. Новый тип препятствий позволяет объезжать выпуклые препятствия любого размера. Pathtracking объезд препятствий Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Одно и то же препятствие может выступать в обоих ролях одновременно. Pathtracking объезд препятствий Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

Pathtracking объезд препятствий Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин

На самом деле все вышеперечисленные алгоритмы в Ex Machina работают в 3D. То есть вместо прямоугольников – боксы, препятствия – выпуклые многоугольники или сферы. Алгоритм работает для любых выпуклых объектов, однако на практике применяются только боксы и сферы, т.к. вычислительно сложно определять пересечения. Алгоритм работает не всегда. Например, для его работы требуется, чтобы расстояния между препятствиями были больше ширины машины, иначе машина может никогда их не объехать Тема: AI автомобиля в изменчивом мире на примере Ex Machina Докладчик: Антон Савин PathtrackingPathtracking дополнительные замечания

Спасибо за внимание! Вопросы? Антон Савин,