Блог

Я реализовал базовую сетку на основе * pathfindinder в Java. Я хотел бы создать навигационный навигатор на основе сетки / полигонов, но проблема, с которой я столкнулся, заключается в следующем:

Если бы я нашел оранжевый маршрут, я мог бы использовать что-то вроде алгоритма воронки, чтобы выпрямить его, чтобы получить желаемый маршрут (синий). Однако, если программа вычислит стоимость каждого из маршрутов, красного и оранжевого, то будет указано, что красный маршрут дешевле. Как мне запрограммировать свой алгоритм A * и / или создать свои сетки, чтобы этого не произошло.

Глава 15 в «Вычислительная геометрия: алгоритмы и приложения» описывает и решает именно эту проблему: свободное пространство может быть описано трапециевидной картой, но пути, найденные с помощью карты, не обязательно самые короткие. Рекомендуемое представление (также обсуждаемое в алгоритмах планирования Лавалле (раздел 6.2.4)) представляет собой так называемый граф видимости, который имеет ребра, соединяющие вершины препятствий.

Псевдокод и рисунки доступны на главной странице книги, а предварительный просмотр Google также содержит части главы.

Извините, я не могу помочь с вашим вопросом напрямую, но мы портировали pathfinder на основе полигонов на haxe, и он может компилироваться на Java (пока пробовался только с swing, но скоро может попробовать slick2d) и может быть интегрирован в проект Java с учетом некоторых исследований. Он называется hxDaedalus и находится на github и может быть интересной отправной точкой.