Может ли кто-нибудь предложить статьи или алгоритмы вычисления кратчайших путей в евклидовых пространствах с невыпуклым многоугольником в качестве препятствий?
path-finding
aneuryzm
источник
источник
Ответы:
Самый простой подход - превратить невыпуклые многоугольники в несколько выпуклых, а затем выполнить обычное выпуклое столкновение и поиск пути (через A * или D * или что-либо еще). Первый процесс часто называют триангуляцией в вычислительной геометрии, и есть несколько распространенных способов сделать это.
источник
Возможно, это не точный ответ на ваш вопрос, но я могу предложить вам подход к этому вопросу.
На самом деле ваша проблема - это две проблемы вместе взятые.
И вторая проблема встроена в первую. Я могу рекомендовать сначала понять слепой поиск. Вот очень простая презентация: слепой поиск
Если вы читаете документ для построения пространства состояний, вам нужно будет сгенерировать точки состояний, и они должны быть законными, то есть эти состояния могут находиться на вашем кратчайшем пути, чтобы они не сталкивались с какими-либо объектами в вашем пространстве. Отныне вы можете продолжать использовать алгоритмы евклидовых столкновений. После построения пространства состояний и дерева поиска, ограниченного коллизиями, вы можете выбрать любой из алгоритмов кратчайшего пути или один из ваших собственных или модифицированных гибридных.
источник