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

Question

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

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

Answer 1

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

Как правило, вам может понадобиться использовать более мощные методы планирования движения, такие как вероятностные дорожные карты (PRM) или Быстрое исследование случайных деревьев (RRT). В этих областях очень много академической работы.

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

Answer 2

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

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

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

Answer 3

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