100% предотвращение столкновений

Я абсолютный новичок в разработке игр, и все, что я знаю о предотвращении / разрешении столкновений, я узнал об этом на этом сайте или через него на прошлой неделе ... поэтому не стесняйтесь поправлять меня, если я спрашиваю здесь основанный на неправильных предположениях / недоразумениях. Я старался изо всех сил, чтобы быть ясным, но это сказало, предмет все еще является новым для меня.

Транспортные средства

В моей игре у меня есть машины, которые двигаются автономно. Они размещены в трехмерном пространстве, и их движение определяется рядом переменных, которые различны для каждого транспортного средства. В первую очередь интерес представляют:

• Только движение вперед .
• Скорости , которая может изменяться от мин и макс, но чей мин это не (даже близко к) нулю.
• Радиус рулевого управления , который зависит от скорости (чем выше скорость, тем больше радиус)
• Два максимальных ускорения (для уменьшения и увеличения скорости)

Цель

Моя цель - реализовать своего рода ИИ, который будет на 100% точнее предотвращать столкновения (т.е. я буду уверен, что машины никогда не столкнутся).

дизайн

• Хотя я бы больше предпочел идею иметь ИИ «на борту» (т. Е. У каждого транспортного средства, имеющего собственный «ИИ предотвращения столкновений», в конечном итоге запрашивать и / или отправлять сообщения другим транспортным средствам), я также могу реализовать ИИ ЦА в центральный уровень (диспетчеризация команд на транспортные средства).
• В большинстве случаев транспортному средству просто придется держаться подальше друг от друга в любом направлении, но при определенных обстоятельствах ему придется избегать столкновения и двигаться к одной и той же цели.

Что я нашел до сих пор и где я застрял

Среди множества ссылок, которые я нашел в других вопросах на этом сайте, я обнаружил, что они особенно полезны:

1. Столкновение мячей у бассейна
2. Предотвращение столкновений без выравнивания
3. Queuing

Хотя эти три ссылки «открыли мне глаза» во многих отношениях, мне не сразу понятно, как использовать эту информацию в моем случае. В частности, статья № 2 только «пытается» предотвратить столкновение (но столкновения случаются время от времени). В то время как статья № 3 должна иногда останавливать транспортные средства, чтобы предотвратить столкновения.

Я также заметил, что алгоритмы предотвращения столкновений, связанные выше, используют «мгновенную проекцию» линейной скорости, чтобы проверить, находится ли что-то на пути транспортного средства. Мне было интересно, достаточно ли этого в моем случае, или мне пришлось проецировать свою позицию более реалистичным образом (например: если я на 60 ° поверну на 90 ° вправо, я должен рассчитать свою позицию для остальной части 30 ° кривой, а затем предполагая линейное движение).

Наконец, я особенно боюсь тупиков . Другими словами: хотя плотность транспортных средств в мире будет довольно низкой, я обеспокоен тем, что, учитывая определенное количество транспортных средств, сходящихся к одной и той же точке, как только они поймут, что находятся на пути столкновения, любые маневры уклонения будут невозможны как это привело бы транспортное средство на пути столкновения с некоторыми другими.

Вопрос

Как я могу достичь своей "цели"? Подробное объяснение, конечно, очень ценится, но ссылки на внешние ресурсы также очень помогли бы (я уверен, что я не первый с этой проблемой, но, возможно, я использовал неправильные ключевые слова для поиска в Интернете? )

Заранее спасибо за вашу помощь!

Вы смотрели в алгоритмы стекаются ? Когда я смотрю на ваше описание, это то, что приходит мне в голову. Для этого есть много статей, вот одна, которая мне нравится . Вероятно, вы не будете использовать все аспекты стека, например сплоченность. Большинство аспектов будет полезно для того, что вы пытаетесь сделать, например, выравнивание и разделение, оба из которых помогут избежать столкновений. В конечном итоге вы получите нечто иное, чем стая, но это должно помочь вам начать.

Удачи!

Вот подход: у каждого транспортного средства есть короткий спроецированный путь, где транспортное средство в конце замедляется и входит в петлю, эти пути могут не перекрываться. Всякий раз, когда транспортное средство подходит к точке, где оно настроено на замедление, вы пытаетесь создать новый путь, который не перекрывает ни один из существующих. Если это не представляется возможным, транспортное средство продолжает движение по заданному пути и периодически повторяет поиск нового пути.

Этот метод может быть улучшен для обеспечения более плотного трафика, позволяя путям, ведущим к петлям, перекрывать друг друга и петли, где можно определить, что это не вызовет коллизию.

Есть метод в каждом транспортном средстве, где он выполняет радиальный поиск вокруг себя, если в этом радиусе есть другие транспортные средства, отодвиньтесь таким образом, который вам нравится: 1) Двигайтесь в противоположном векторе, 2) замедлитесь, 3) ускорить и т. д.

Вы можете даже делать комбинации: если вектор другого транспортного средства не прямо или прямо позади: отойдите; иначе, если это прямо: замедлиться; остальное: ускорение.

Моя цель - реализовать своего рода ИИ, который будет на 100% точнее избегать столкновений (т.е. я буду уверен, что машины никогда не столкнутся).

Если бы это было возможно, это было бы введено во все самолеты мира к настоящему времени.

Я предлагаю ослабить «автономный» аспект и иметь функцию, которая разрешает предсказанные столкновения между 2 (или более) транспортными средствами. Это может быть так же наивно, как выбирать случайные новые направления для поездки и видеть, решает ли это проблему, но важно то, что функция возвращается только тогда, когда достигнуто соглашение, которое подходит для обоих транспортных средств.

Я также предлагаю, чтобы любое транспортное средство, которое, по прогнозам, столкнулось в ближайшем будущем, уменьшило бы свою скорость, сохраняя при этом то же расстояние упреждения - это даст вашим транспортным средствам больше возможностей избегать столкновений, как в реальной жизни.

Мне кажется, что симуляция толпы может быть темой, наиболее соответствующей тому, чего вы пытаетесь достичь. У группы GAMMA в UNC есть большой объем работы по этому вопросу, который, возможно, стоит рассмотреть. Их описание:

Толпа и мультиагентное моделирование - это процесс моделирования большого количества людей, существ или других персонажей, каждый из которых взаимодействует в одной среде. Ожидается, что эти участники будут двигаться к своим целям, взаимодействовать с окружающей средой и реагировать друг на друга. Моделирование толпы имеет множество применений, включая улучшение архитектурного планирования, улучшение учебных сред и виртуальных реалий, а также управление искусственно-интеллектуальными (ИИ) персонажами в играх и фильмах. Наша группа работала над многими проблемами в моделировании толпы, включая быстрое, гарантированное, предотвращение столкновений, планирование траектории и движения в реальном времени, массовые потоки и направленное поведение.

http://gamma.cs.unc.edu/research/crowds/

Я не думаю, что существует метод 100% избегания, но если ваши транспортные средства обладают полной информацией о мире, вы можете заключить каждое транспортное средство в коробку, длина которой зависит от его скорости, и выполнить проверку столкновения на этих коробках. Если действительно есть столкновение, держитесь подальше, с силой, зависящей от неизбежности удара (или площади столкновения между двумя коробками), и медленного Доу (но сохраняйте вашу коробку одинаковой длины во время операции уклонения).

Очевидно, что это не сработает, если транспортные средства не обладают полной информацией, но в этом случае ничто не гарантирует 100% предотвращения (кроме, как уже говорилось, параллельного движения)

некоторые методы, описанные здесь , вероятно, будут полезны, в частности, этот: Поведение рулевого управления по предотвращению столкновения

С уважением