Поиск путей на произвольных непрямоугольных телах

Question

У меня есть различные объекты, поверхности которых 3D и не прямоугольные, такие как сферы, пирамиды и различные другие объекты, представленные сетками. Сетка не состоит из многоугольников одинакового размера и распределения по поверхности объекта, равно как и не все полу/симметричные объекты, такие как идеальные формы цилиндров, сфер и конусов.

Таким образом, как я буду заниматься разработкой или доработкой алгоритма поиска пути, который бы взял произвольные ячейки и сгенерированные узлы, которые могли бы обернуться вокруг себя любым количеством способов?

Answer 1

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

В целом вам может потребоваться использовать более мощные методы планирования движения, такие как probabilistic roadmaps (PRM) или Rapidly-exploring Random Trees (RRT). В этих областях довольно много академической работы.

В качестве вступительного слова вы можете просмотреть обзорный документ, например this one (PDF).

Answer 2

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

Answer 3

Я понимаю, что вы, вероятно, не рассказываете нам большую картину здесь и пытаетесь сварить вашу проблему до 3d сцены => направленный граф => ??? => pathfind, но считаете ли вы, что это подходит с другого направления?

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

В любом случае, вы можете найти this link, полезный для ваших исследований.