Существует ли алгоритм поиска пути, который также подходит для реальных 3D-сред, например. реальные здания с несколькими лестницами и т. д. Библиотека C++ или открытая реализация были бы великолепны ;-) Одним из решений, которое я видел, была Djikstra, но мне интересно, есть ли что-то более оптимальное. Обычный A * не будет работать лучше, чем Djikstra, поскольку эвристика расстояния не работает должным образом (положение на один этаж выше пункта назначения). Еще одно решение, над которым я сейчас думаю, — это отображение трехмерной среды на двумерном графике. Так что, если есть какая-то доступная реализация/библиотека С++, это тоже будет полезно.
Поиск пути в реальных трехмерных средах (например, зданиях)
comment
Если у вас нет большого количества лестниц, A* может работать очень хорошо, поскольку ваша эвристика для точек на разных уровнях представляет собой сумму расстояний до ближайших лестниц плюс расстояние по вертикали.
- person biziclop schedule 16.04.2012
comment
@biziclop: Это очень хорошая идея, и она намного проще, чем любое преобразование графа. я попробую
- person Martin schedule 16.04.2012
comment
Я считаю, что поиск пути подвержен принципу «разделяй и властвуй». Итак, вы можете попробовать использовать A * на 2-х уровнях и алгоритм Дейкстры, чтобы связать их вместе.
- person comingstorm schedule 16.04.2012
Ответы (2)
Если путь должен учитывать способность преодолевать препятствия (т. е. движение — это движение некоторой сущности с известным объемом в пространстве), то я бы рекомендовал изучить литературу по планированию движения роботов. Понятие конфигурационного пространства позволяет вам обрабатывать изменения позы, чтобы справляться с препятствиями. См. классический учебник Жан-Клода Латомба.
Для более простых сценариев вы, вероятно, можете обойтись алгоритмами планирования пути, используемыми в компьютерных играх от первого лица, которые похожи на Dijkstra, A* (пример)
person
killogre
schedule
16.04.2012
Для алгоритма аппроксимации вы можете легко сопоставить 3d с 1d кривой и пройти октодерево с кодом Грея. Таким образом, вы можете изменить порядок каждого пути. Я не знаю, есть ли гарантия оптимального решения, но оно должно быть лучше любого эвристического метода.
person
Gigamegs
schedule
16.04.2012
Звучит интересно, но я не совсем понимаю вашу идею. Для каждого пути начало, очевидно, различно. Итак, вы предлагаете сначала построить октодерево для каждого запуска или как мне сформулировать критерий сортировки для дерева? (Должен признаться, я не очень хорошо знаком с октодеревьями...)
- person Martin; 18.04.2012
Кроме того, поскольку у меня нет узлов для каждого направления (представьте себе коридор с несколькими узлами), дерево будет в значительной степени разреженным, если это разумно для октодеревьев.
- person Martin; 18.04.2012
