Базовый поиск пути с обходом препятствий в непрерывном 2D-пространстве

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

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

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

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

Дополнительную информацию можно найти на веб-сайте "Управление поведением автономных персонажей".

С уважением

Гийом

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

Возможно, вы могли бы использовать алгоритм Pledge

Всякий раз, когда ваше существо, движущееся в направлении вектора 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*, хотя в этом может не быть необходимости, если ваша среда обладает достаточной структурой.

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

Вот ссылка

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

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