Представьте себе автомобильное движение, в котором сущности не могут включить ни копейки. Скажем, ради обсуждения, что при скорости они могут разворачиваться на 90 градусов в секунду. Это во многих случаях изменит оптимальный путь и, следовательно, поиск пути. Это может даже сделать «обычные» пути совершенно невозможными для прохождения.
Существуют ли какие-либо алгоритмы поиска пути или алгоритмы планирования движения, которые могут помнить об этом, или есть простые способы адаптации популярных?
path-finding
car
Веккар Э.
источник
источник
Ответы:
Добро пожаловать в удивительный мир неголономного планирования движений. Я рекомендую делать это, используя планировщик пути с решетчатой сеткой . Другие альтернативы включают кинодинамический RRT и оптимизацию траектории . К неголономным системам относятся автомобили, лодки, велосипеды или что-то еще, где транспортное средство не может двигаться в любом направлении, в котором оно хочет. Планирование этих систем намного сложнее, чем голономных, и до 2000 года находилось на грани научных исследований. В настоящее время существует множество алгоритмов на выбор, из которых работают достойно.
Вот как это работает.
государственный
Конфигурация вашего автомобиля q на самом деле является трехмерным состоянием, содержащим положение x, y автомобиля и его ориентацию t . Узлы в вашем алгоритме A * на самом деле являются трехмерными векторами.
действия
Так что с краями?
Это немного сложнее, потому что ваш автомобиль может выбрать бесконечное количество способов поворота колеса. Таким образом, мы можем сделать это доступное для решетки сетки планировщика, ограничивая количество действий , автомобиль может принять для дискретного множества, A . Для простоты предположим, что автомобиль не ускоряется, а может мгновенно менять скорость. В нашем случае A может быть следующим:
Теперь мы можем создать дискретный набор действий, которые автомобиль может предпринять в любое время. Например, жесткое правое нажатие при полном газе в течение 0,5 секунды будет выглядеть так:
Установка автомобиля на задний ход и задний ход будет выглядеть так:
И ваш список действий будет выглядеть так:
Вам также нужен способ определения того, как действие, выполненное на узле, приводит к созданию нового узла. Это называется прямой динамикой системы.
Дискретные ячейки сетки
Теперь, чтобы построить решетчатую сетку, все, что нам нужно сделать, это хешировать состояния автомобиля в отдельные ячейки сетки. Это превращает их в отдельные узлы, за которыми может следовать A *. Это очень важно, потому что в противном случае у A * не было бы никакой возможности узнать, являются ли два состояния автомобиля фактически одинаковыми, чтобы сравнить их. Хэширование целочисленных значений ячеек сетки делает это тривиальным.
Теперь мы можем создать план A *, где GridCells - это узлы, Actions - это ребра между узлами, а Start и Goal выражены в терминах GridCells. Эвристика между двумя GridCell - это расстояние в x и y плюс угловое расстояние в тэте.
По пути
Теперь, когда у нас есть путь с точки зрения GridCells и действий между ними, мы можем написать последователь пути для автомобиля. Поскольку ячейки сетки являются дискретными, автомобиль будет прыгать между ячейками. Поэтому нам придется сгладить движение автомобиля по дорожке. Если в вашей игре используется физический движок, это можно сделать, написав контроллер рулевого управления, который пытается удерживать автомобиль как можно ближе к траектории. В противном случае вы можете анимировать путь, используя кривые Безье или просто усредняя ближайшие точки в пути.
источник
Большинство алгоритмов поиска пути работают на произвольном графе без ограничения геометрии.
Так что вам нужно добавить ориентацию автомобиля к каждому исследуемому узлу и ограничить, какие узлы действительно подключены.
источник
Мои мысли, не проверял их!
Вы также должны быть в состоянии сделать это без необходимости сначала завершать путь, следовательно: обработка поворотов во время A *, что, вероятно, будет намного лучше оптимизировано, но это также может оказаться проблематичным и сбойным, я действительно не знаю и, к сожалению, я нет времени, чтобы проверить это сам.
источник
Если ваш агент полностью контролирует машину, сделайте это наоборот. Сначала соедините линию от начала до конца, затем выясните, с какой скоростью вы можете перемещаться в каждом повороте, аналогично ответу Денниса.
Не рисуйте кривые Безье из неподвижных точек. Чтобы минимизировать потерю скорости, вам нужно переместить всю линию вокруг, поэтому начните с вставки дополнительных узлов на более или менее равномерном расстоянии, а затем двигайтесь для минимизации энергии или аналогичных стратегий. Для получения более подробной информации вам нужно взглянуть на генерацию искусственной линии в гоночных играх (предпочтительно сим или полусим).
Как только у вас будет запущена система линий AI, запустите поиск A * и для каждого пути продвиньтесь хотя бы на один угол вперед, затем вычислите линию AI, которая даст вам оценку времени. Это будет ваша функция стоимости.
источник