Алгоритм маршрутизации для непрерывного пространства поиска?
В настоящее время я делаю RTS-игру в единстве, и мне нужен способ рассчитать кратчайший путь между двумя точками на непрерывной 2-мерной плоскости, где есть определенные препятствия.
У меня есть начальная позиция, конечная позиция и функция, которая может проверить, является ли позиция действительной. Мне нужен алгоритм, который возвращает последовательность точек для перемещения, чтобы добраться до места назначения.
Большинство известных мне алгоритмов маршрутизации, таких как A* и IDA*, требуют дискретного пространства поиска. Я сам разделил бы плоскость на сетку, но боюсь, что это приведет к появлению зигзагообразных паттернов, которые выглядят действительно неестественно при движении по диагонали. Есть ли способ облегчить эту проблему или другой алгоритм маршрутизации, который я могу использовать? Ему даже не нужно искать абсолютный кратчайший путь, просто путь, который имеет смысл.
1 ответ
Один из подходов может состоять в том, чтобы дискретизировать пространство поиска, рассматривая только точки, представляющие интерес для планирования - точки на границах препятствий, например только углы ограничивающих прямоугольников, и затем использовать любой из известных вам алгоритмов.
Другим вариантом будет вычисление на сетке, а затем сглаживание лучшего пути, найденного на сетке.
Вы можете создать зигзагообразный путь, а затем использовать Pure Pursuit, чтобы сгладить его.