Поиск путей на основе полигонов

#java #polygon #mesh #path-finding #a-star

#java #полигон #сетка #поиск путей #a-star

Вопрос:

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

базовая карта полигонов с возможными маршрутами

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

Ответ №1:

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

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

Комментарии:

1. Спасибо! Я посмотрю, смогу ли я получить копию, это выглядит очень интересно.

Ответ №2:

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