Адаптируйте алгоритм поиска путей * к очень большой карте с множеством различных разделов.

Question

Я посмотрел в HPA *. Проблема в том, что большие части моей карты будут либо пустыми, либо очень редкими, а некоторые части будут очень плотными.

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

В настоящее время 100 единиц могут пройти пустую сетку 100x100 за 5 мс, используя *. Тем не менее, мои карты будут, вероятно, 10000 х 10000.

Чтобы быть более точным c:

Я ищу способ использовать HPA *, но только в плотных областях. А в районах с редкими препятствиями просто идите по прямой (и вокруг препятствий). Я также хотел бы, чтобы юнит мог найти путь от разреженной области к плотной или наоборот, если им требуются отдельные алгоритмы.

Спасибо!

Answer 1

Я бы попытался изменить HPA * так, чтобы вместо поиска пути через путевые точки вокруг своего текущего кластера устройство находило путь через путевые точки вокруг края подсетки 9x9 кластеров по центру на своем текущем кластере.

По мере движения юнита подсетка 9x9 будет двигаться до того, как юнит доберется до одной из путевых точек по краю. Затем он найдет путь, используя новые точки пути, которые находятся дальше, и ему фактически никогда не придется проходить через точку.