Поиск пути на неровной поверхности планеты

16

Мой вопрос: каков наилучший подход к поиску пути на неровной поверхности планеты?


Исходная информация

Я создал планету из карт смещения 6 спроектированных сфер. Плоскости первоначально сформировали куб, прежде чем проецироваться в форму сферы.

введите описание изображения здесь

Мне интересно, можно ли использовать каждую «грань проецируемой сферой куба» в качестве сетки и использовать простой алгоритм A *, чтобы найти наилучший возможный маршрут, я также хотел бы, чтобы высота смещения учитывалась, чтобы путь избегал подъема. горы и т. д. (я полагаю, это будет эвристика в алгоритме A *) Еще одно соображение заключается в том, что я достиг планетарного движения , используя физический двигатель Unity3d, применяя гравитацию к центру планеты. Будет ли мое предлагаемое решение требовать, чтобы движение агентов контролировалось независимо от гравитационной физики.

Чтобы лучше сформулировать мой вопрос, это мое нынешнее планетарное тело:

введите описание изображения здесь

Гай Евгений
источник
2
Возможно, вас заинтересует это видео из Planetary Annihilation. Похоже, они делают то же, что и вы, окружая мир кубом и находя путь вокруг него. Это не совсем ответ, но вы можете видеть, что они используют A * вместе с некоторыми другими стратегиями для оптимизации поиска пути вокруг сферы. Поиск пути начинается в 24:30 .
MichaelHouse
@ Byte56 Спасибо за эту ссылку действительно интересный подход к стоимости, не могу дождаться, чтобы увидеть эту игру, когда она будет закончена!
Гай Евгений

Ответы:

12

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

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

По сути, мы хотим отобразить переход от красного к синему, чтобы он был таким же на сфере, как и на кубе.

введите описание изображения здесь

Поскольку A * часто получает соседей к своему текущему узлу, вы можете легко создать набор функций для получения соседних узлов. Так , например, getXPlus(), getXMinus(), getZPlus()и так далее. Эти функции возьмут текущий узел и вернут узел в направлении, указанном в имени функции.

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

Вы захотите отобразить поверхность вашего куба в 2D систему координат. Как бы вы ни делали, это зависит от вас, им не нужно выстраиваться в линию, просто присвойте каждому пространству сетки уникальную координату X, Y.

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

Например, получение здесь координаты XPlus изменит координаты X и Y, потому что мы перемещаемся в новое пространство сетки на новой грани. Зеленая линия представляет грань между двумя гранями.

введите описание изображения здесь

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

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

Все это в конечном итоге должно быть удалено, чтобы вы даже не знали об этом.

MichaelHouse
источник
Приветствия за ответ. Я думаю, что я борюсь с тем, чтобы каждая плоскость была изолированной сеткой. Будете ли вы предлагать какие-либо предложения (или дальнейшее чтение) о том, как справляться со швами, я предполагаю, что мне придется математически развернуть мой «куб», объединить все сетки и рассчитать путь, используя этот набор данных?
Гай Евгений
На самом деле нужно беспокоиться только о краях. Это легко решается с помощью функции-оболочки (оборачивая ваш куб в функцию-обертку, которая оборачивает ваш мир ...). Вы можете абстрагировать куб в плоскую поверхность, которая оборачивается. Создайте функции для получения соседнего пространства сетки, getXPlus () получит сетку в направлении XPlus, не имеет значения, находится ли она на границе между гранями, функция просто переключит грани и вернет соответствующую информацию сетки.
MichaelHouse
Единственная неточность при поиске пути на сложенном кубе состоит в том, что вершины перекошены и, следовательно, ребра имеют разную длину. Вполне возможно, что в результирующих путях заметного различия не будет, иначе вы просто могли бы принять во внимание длину.
Данияр
1
Здесь важно понять, что A * не обязательно действует на плоскости; он работает на графике. Хотя внутри каждой грани куба узлы расположены и связаны в сетке, есть также соединения узлов по краям куба.
jmegaffin
1
@ Byte56 Спасибо за отличный ответ, я начал реализовывать решение, но столкнулся с некоторым препятствием. Может быть, я неправильно понял. Я разместил вопрос в stackoverflow, так как чувствовал, что это скорее математическая проблема / программирование stackoverflow.com/questions/16089074/…
Caius Eugene