Реализовать алгоритм траектории звездочки (A *) на большой карте, низкая производительность

Question

Я использую эту звезду (A *) Pathfinder.java для вычисления & генерировать свой маршрут в приложении для Android-карт. https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java

Размер карты велик, размеры около 8000x8000, когда я использую звездочку Pathfinder.java рассчитать маршрут от одной до другой точки на карте.

Звездный Pathfinder вычисляет 1 на 1 и используется на большой карте (8000x8000), скорость выполнения/вычисления довольно низкая/медленная (неэффективная). Я попытался увеличить расчет до 100 на 100, он работает нормально, но маршрут маршрута не является гладким по кривой.

Есть ли способ улучшить эффективность расчета маршрута с помощью алгоритма A-звезды или любого другого решения для решения проблемы? Мне нужна помощь в решении этой проблемы.

Answer 1

Реализация: Если вы ищете обзор кода, разместите рабочий код на CodeReview.StackExchange.com. Вероятно, они могут дать вам советы по оптимизации.

Алгоритм: Вот несколько соображений с алгоритмической точки зрения.

Прежде всего, взгляните на свою эвристику. Если эвристические оценки слишком малы, A * вырождается до алгоритма Дикстры. Если эвристические оценки слишком высоки, A * вырождается в жадный лучший первый поиск. A * с допустимой эвристикой находится где-то посередине: он создает оптимальный путь, но поддержание оптимальности требует дополнительного времени вычисления. Если вы готовы пожертвовать оптимальностью, вы можете выбрать эвристику, которая иногда переоценивает расстояние до цели. Таким образом, пути не гарантируются как оптимальные, но жадность алгоритма может сократить время выполнения.

Кроме того, если мир статичен (то есть макет известен a priori), вы можете предварительно вычислить много информации, чтобы ускорить поиск. Для выполнения этой задачи существует несколько алгоритмов. Swamps - это подход, который предварительно вычисляет области, которые обычно искажаются без необходимости (то есть болота). Если вы не путешествуете в болото или выходите из него, регионы не нужно искать во время работы. Ускорение, связанное с болотами, сильно зависит от топографии в мире; более обманчивые карты (т. е. те, которые ведут к поиску болот) могут принести много пользы.

Другим подходом является использование иерархического подхода к поиску путей, такого как HPA*. Это может значительно увеличить производительность на карте размером с ваш (8000x8000, yikes). HPA * работает, группируя регионы в связанные локальные кластеры и вычисляя затраты на пересечение границ кластера a priori. Затем поиск выполняется на нескольких уровнях: высокоуровневое усилие фокусирует поиск, используя заранее рассчитанные затраты, а низкоуровневое усилие определяет точный путь, который будет использоваться.

Кроме того, существуют алгоритмы для уменьшения числа узлов, исследованных A *, используя характеристики среды во время выполнения. Например, Jump Point Search (JPS) использует тот факт, что сетчатые графы (например, тот, который вы используете) часто демонстрируют симметрии. Если движение в вашем мире имеет постоянные затраты, JPS может «пропустить» множество узлов в поиске и сократить время поиска на значительную сумму. Я видел, что он сократил время поиска A * на 24x, другие видели более 30-кратное улучшение.

Последнее замечание: из того, что я могу сказать, вы используете пути L1 (т. Е. 4-кардинальные направления).У вас может быть много шансов получить путем предварительной обработки путей между путевыми точками и использования дифференциальной эвристики. См. this article для демонстрации и обсуждения реализации JavaScript here.

Дополнительные ссылки:

• Great visualizations of JPS in action
• More info for JPS
• Variations of A*
• Amit's A* Pages: the best A* resource I know
• How to speed up A* blog post