Основное нахождение пути с обходом препятствий в непрерывном двумерном пространстве

Question

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

Это двумерная среда (вид сверху), и каждый объект имеет ограничивающий прямоугольник для обнаружения столкновений. Нет сетки, и я не ищу A * решение.

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

Любые рекомендации о том, как это реализовать (или ссылки на учебники)?

Answer 1

В продолжение сказанного Гийомом об обходе препятствий, техника, которая будет вам полезна, это антигравитационное движение . Вы рассматриваете локальные препятствия как точечные источники антигравитации, а пункт назначения - как гравитацию, а ваш компьютерный персонаж будет скользить (как мыло!) Вокруг препятствий, чтобы добраться до пункта назначения.

Answer 2

Вы можете объединить два алгоритма рулевого управления:

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

Предотвращение препятствий : вы предвидите будущее автомобиля, используя поле, длина которого равна постоянному времени, умноженному на текущую скорость автомобиля. Любое препятствие, которое пересекает это поле, является потенциальной угрозой столкновения. Ближайшая такая угроза выбрана для избежания. Чтобы избежать препятствия, поперечное рулевое усилие прикладывается напротив центра препятствия. Кроме того, применяется сила торможения (замедления). Эти силы меняются в зависимости от срочности (расстояние от кончика коробки до точки потенциального столкновения). Рулевое управление изменяется линейно, торможение изменяется квадратично.

Вы можете найти больше на сайте " Поведение рулевого управления для автономных персонажей "

привет

Гийом

PS: это предполагает, что вы используете метод точки / скорости / ускорения для движения объекта.

Answer 3

Может быть, вы могли бы использовать алгоритм залога

Answer 4

Всякий раз, когда ваше существо, путешествующее в направлении вектора v, сталкивается со стеной, направление которой представлено вектором w, направление, которое вам нужно "скользить", определяется вектором, который является проекцией v на w. Это можно найти с помощью

  v . w
--------- w
 |w|*|w|

, где . - это векторное произведение , а |w| - это величина вектора w (= sqrt(w . w)). Если w является единичным вектором, это становится просто

(v . w) w

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

Если вместо этого вы хотите, чтобы ваше существо всегда путешествовало на полной скорости, вам нужен только знак v . w - вы всегда будете путешествовать либо в направлении стены (w), либо в противоположном направлении (-w).

Проблема, с которой вы столкнетесь, - это когда ваше существо врезается в стену. В этом случае ваш спроецированный вектор будет (0, 0), и вам понадобится другой метод, чтобы решить, в какую сторону (w или -w) идти. Обычный подход здесь - это A *, хотя это может быть ненужным, если ваша среда обладает достаточной структурой.

Answer 5

Я опубликовал алгоритм поиска пути в C # некоторое время назад

Вот ссылка

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

(текст на испанском языке, но вы можете скачать приложение по ссылке вверху)