Перейти к содержимому

some blog name

  • записей
    15
  • комментарий
    41
  • просмотров
    17 256

Поиск пути

Doob

947 просмотров

Когда я узнал о JPS, у меня возникла идея упростить A*. Можно выкинуть волновую рекурсию, которая используется во всех алгоритмах поиска пути. Для этого, берем все узлы, которые являются препятствиями, помечаем соседние свободные узлы и строим путь. Из самого описания выходит, что данный алгоритм подойдет не для всех типов графов, но ботам на регулярной сетке в самый раз.

Проблема данного алгоритма в том, что препятствий может быть очень много, а на пути между стартом и финишем очень мало. Фактически это алгоритм Дейкстры без рекурсии, прямой переход в самое последнее возможное состояние. Потребление памяти меньше чем у Дейкстры и А*, т. к. отмечается только финальный фронт.

Чтобы оптимизировать, будем отмечать только те граничные узлы, которые находятся ближе к стартовой и финишной точке. Получаем JPS, только избыточней, но лучше чем A* по потреблению памяти. Остается построить путь поиском в ширину из доступных оптимальных путей.

 

Вот сравнение по потреблению памяти при обходе препятствий:

 

A* хранит данные о свободных клетках, полученных на данной эвристике. В эти данные входят координаты точки, расстояние до цели, количество предыдущих шагов.

273CA7D.png

 

 

Jump Point Search хранит точки перехода на пути от старта к финишу, хранятся только координаты точек и по выбору: координаты соседних переходов или расстояние до финиша.

tCU50u1.png

 

 

При удалении рекурсии надо хранить координаты граничных точек, а все вычисления производить только при построении пути.

6c9TkOw.png

 

 

Если найти способ не хранить все доступные граничные точки, то алгоритм без рекурсии вполне годится для практического применения.

JPS в большинстве применений превосходит A*, он быстрее, потребляет меньше памяти. Но не годится для открытых пространств, если регион поиска искусственно не ограничить, он будет вечно искать оптимальный путь, т. к. его преимущество оборачивается недостатком. Возможно эту проблему уже решили, но никакой информации об этом я не нашел.

  • Нравится 1


0 комментариев


Рекомендуемые комментарии

Нет комментариев для отображения

Гость
Добавить комментарий...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...