Алгоритм поиска пути Jump Point Search

Этот алгоритм является улучшенным алгоритмом поиска пути A*. JPS ускоряет поиск пути, “перепрыгивая” многие места, которые должны быть просмотрены.  В отличие от подобных алгоритмов JPS не требует предварительной обработки и дополнительных затрат памяти. Данный алгоритм представлен в 2011 году, а в 2012 получил высокие отклики. Что из себя представляет данный алгоритм и его реализацию можно прочитать дальше в статье.



Терминология и обозначения


Алгоритм работает на неориентированном графе единой стоимости. Каждое поле карты имеет <= 8 соседей, которые могут быть проходимы или же нет. Каждый шаг по направлению (по вертикали или по горизонтали) имеет стоимость 1; шаг по диагонали имеет стоимость √2. Движения через препятствия запрещены. Обозначение  относится к одному из восьми направлений движения (вверх, вниз, влево и т.д.).
  • Запись y = x + kd означает, что точка y может быть достигнута через k шагов из x в направлении d. Когда d – движение по диагонали, перемещение делится на два перемещения по прямой d1 и d2.
  • Путь p = (n0, n1, …, nk) – упорядоченное перемещение по точкам без циклов из точки n0 до точки nk.
  • Обозначение p \ x означает, что точка x не встречается на пути p.
  • Обозначение len(p) означает длину или стоимость пути p.
  • Обозначение dist(x, y) означает длину или стоимость пути между точками x и y.


Jump points


“Прыжковые точки” позволяют ускорить алгоритм поиска пути, рассматривая только “необходимые” точки. Такие точки могут быть описаны двумя простыми правилами выбора соседей при рекурсивном поиске: одно правило для прямолинейного движения и другое – для диагонального. В обоих случаях необходимо доказать, что исключая из набора ближайших соседей вокруг точки, найдётся оптимальный путь из предка текущей точки до каждого из соседей, и этот путь не будет содержать в себе посещенную точку. Рассмотрим случай 1, который отражает основную идею:

Случай 1: Отсечённый сосед



Х – текущая рассматриваемая точка. Стрелка указывает направление движения. И там и там можно сразу отсечь соседей, выделенных серым, т.к. туда можно попасть по оптимальному пути из p(x), никогда не проходя через x.

Будем ссылаться на множество точек, которые остаются после отсечения настоящих соседей текущей точки. Они отмечены белыми на рисунке. В идеале, мы хотим учитывать только настоящих соседей во время просмотра. Тем не менее, в некоторых случаях, наличие препятствий может означать, что мы должны также рассмотреть небольшой набор до K дополнительных точек (0 ≤ K ≤ 2). Мы говорим, что это точки вынужденных соседей текущей позиции.

Случай 2: Принуждённый сосед

Х – текущая рассматриваемая точка. Стрелка указывает направление движения. Обратите внимание, что, когда х находится рядом с препятствием, выделенные соседи не могут быть отсечены, любой альтернативный оптимальный путь от p(х) в каждом из этих узлов, блокируется.

Эти случаи применяются следующим образом: вместо создания “вынужденных” и “естественных” соседей мы рекурсивно отсекаем список соседей вокруг каждой точки. Таким образом наша цель заключается в ликвидации “симметрии”, рекурсивно “перепрыгивая” через все точки, в которые можно попасть по оптимальному пути, который не проходил через текущую позицию. Рекурсия останавливается при попадании на препятствие или нашли так называемую “прыжковую точку-преемник” (jump point successor). Прыжковые точки интересны тем, что они имеют соседей, которые не могут быть достигнуты альтернативным путём: оптимальный путь должен идти через текущую точку. Таким образом g(y) = g(x) + dist(x; y) – стоимость перемещения.

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

Рассмотрим пример:



Здесь добавляется точка x для рассмотрения, предком которой является p(x); направление движение от p(x) к x является прямолинейное перемещение вправо.

(Левая картинка): Рекурсивно применяем правило отсечки и получаем у в качестве преемника прыжковой точки х. Эта точка интересна тем, что есть сосед z, в который можно попасть по оптимальному пути только через y. Промежуточные точки не генерируются и не рассматриваются.

(Правая картинка): Рекурсивно принимаем диагональные правила отсечки. Обратите внимание, что перед каждым следующим диагональным шагом необходимо рекурсивно пройтись по прямым линиям (выделены пунктиром). Только если обе “прямые” рекурсии не могут определить точку следующего прыжка, то перемещаемся дальше по диагонали. Точка w – вынужденный сосед х, создаётся как обычный.

Правила отсечения соседа


Далее опишем, каким образом отсекать множество точек, непосредственно примыкающих к некоторой точке х. Цель заключается в нахождении таких соседей, т.е. neighbours(x), до любых n точек которых нельзя достичь цель оптимально. Мы добиваемся этого путём сравнения двух путей: p, который начинается точкой p(x), посещает x и заканчивается c n и другим путём p’, который так же начинается с p(x), посещает x и заканчивается n, но не содержат х. Кроме того, каждая точка, содержащаяся в p или p’, должна относиться к neighbours(x).

Есть два случая, в зависимости от того, какой переход к х происходит из p(x): прямой ход или диагональный. Стоит учесть, что если x является началом p(x), то p(x) пусто и отсечение не происходит.

Прямые переходы:

Отсекаются любые точки , которые удовлетворяют следующему утверждению:
(1)
а
Здесь p(x) = 4 и мы отсекаем всех соседей кроме n = 5

Диагональные переходы:

Здесь отличия в том, что путь, который исключает х, должен быть строго доминирующим:

(2)
б
Здесь p(x) = 6 и отсекаются все соседи, кроме n = 2, n = 3 и n = 5.

Предполагая, что neighbours(x) не содержат препятствий, будем ссылаться на точки, которые остаются после прямой или диагональной отсечки (при необходимости), как естественные соседи x. Они соответствуют не серым точкам на а и б рисунках. Когда neighbours(x) содержат препятствия, нельзя отсечь всех не естественных соседей. В этом случае такой сосед считается принуждённым (искусственным).

Определение 1.

Точка  является принуждённой, если



в
На примере в показан прямой переход, где n = 3 — принуждённый.

г
На примере г показан пример диагонального перемещения; здесь n=1 – принуждённый сосед.

Описание алгоритма


Введём определение:

Определение 2.

Точка y является точкой прыжка точки х, в направлении d, если y минимизирует значение k так, что y = x + kd, и выполняется одно из следующих условий:
  1. Точка y – точка назначения.
  2. У точки y есть хотя бы один сосед, который является принуждённым по определению 1.
  3. d – движение по диагонали и существует точка z = y + kidi,  которая лежит в kшагах в направлении di ∈ {d1, d2}, таких что z – точка прыжка из y при условии 1 или 2.



Этот рисунок показывает пример точки прыжка, которая определена условием 3. Здесь мы начинаем в точке х и заканчиваем движение по диагонали, пока не наткнёмся на точку у. Из у в точку z можно попасть с kiшагами по горизонтали. Таким образом, z является преемником точки для прыжка x (по условию 2), а это в свою очередь определяет y как преемник для прыжка точки x.

Алгоритм 1. Определение преемника.

Зададим: х – текущая точка, s – начало, g – цель



Алгоритм 1 показывает как искать преемника для текущей точки. Сначала обрезается множество соседей, непосредственно примыкающих к текущей точке х (строка 2). Тогда вместо добавления каждого соседа n в множество successors (преемников) для x, попробуем “перепрыгнуть” к точке, которая находится дальше, но которая лежит относительно направлению x к n (строки 3-5). Например, если ребро (x; n) представляет собой движение по прямой вправо от x, то смотрим точку прыжка непосредственно справа от x. Если находится такая точка, то она добавляется в набор преемников вместо n. Если до точки прыжка дойти не получается, то ничего не добавляется. Процесс продолжается до тех пор, пока все соседи не закончатся, и затем алгоритм вернёт список всех преемников для х (строка 6).

Алгоритм 2. Функция прыжка.

Зададим: х – точка отчёта, d – направление, s – начало, g – цель



Для того, чтобы найти отдельных преемников для точки прыжка, воспользуемся алгоритмом 2. Он требует точки отчёта x, направление движения d, а так же начальную точку s и целевую точку g. Алгоритм пытается установить, имеет ли x точку для прыжка среди преемников, перемещаясь по направлению d (строка 1) и проверяет, удовлетворяет ли точка n Определению 2. В этом случае, n обозначается точкой прыжка и возвращается (строки 5, 7 и 11). Если n не является точкой прыжка, алгоритм рекурсивно повторяется и двигается снова в направлении d, но в этот раз n – новая точка отчёта (строка 12). Рекурсия прекращается, когда встречается препятствие и никакие дальнейшие действия не могут быть предприняты (строка 3). Стоит обратить внимание, что перед каждым диагональным шагом алгоритм должен обнаружить точки прыжка по прямым направлениям (строки 9-11). Эта проверка соответствует третьему условию Определения 2 и имеет важное значение для сохранения оптимальности алгоритма.

Ссылки


Описание алгоритма в оригинале: harablog.wordpress.com/2011/09/07/jump-point-search
Реализация на js: qiao.github.com/PathFinding.js/visual (выбрать Jump Point Search и расставить стенки)
Сам код на js: github.com/qiao/PathFinding.js/blob/master/src/finders/JumpPointFinder.js
Benchmark: github.com/Yonaba/Jumper-Benchmark
Подробный визуализатор: zerowidth.com/2013/05/05/jump-point-search-explained.html
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 37
  • –32
    Я не понимаю*.
    Но попробую разобраться на досуге. Применение найдется.
    • +45
      Держите нас в курсе.
    • –15
      Алгоритм работает на неориентированном графе единой стоимости.
      Неверно: у графа не бывает ни направлений, ни, тем более, диагоналей. Данный алгоритм работает на лабиринтах.
      • +11
        Лолшто? Вот вам ориентированный граф, а что такое «лабиринт»? Всё то, что описывает статья может быть описано как граф, а препятствия — это переходы с бесконечно большим весом, вот и всё.
        • +3
          По крайней мере не очень понятно, как согласуется выражение «единой стоимости» с тем фактом, что вес ортоганальных и диагоняльных переходов разный.
          • +5
            Всё то, что описывает статья может быть описано как граф

            Но не всякий граф может быть обработан алгоритмом Jump Point Search. Попробуйте найти естественных и принужденных соседей на вот этом фрагменте графа:

            Алгоритм Jump Point Search применим к графам, порожденным регулярными структурами — например, раскрашенной квадратной сеткой. Только для квадратных сеток существуют такие понятия, как «прямой переход» и «диагональный переход». Только для сеток существует такое понятие, как координаты, которые активно используются функциями step и direction. Поэтому я и утверждаю, что понятие «граф» — слишком широкое для данной статьи.

            PS С математической точки зрения, лабиринт — неориентированный граф, порожденный раскрашенной регулярной геометрической фигурой, при этом его вершины соответствуют внутренним областям фигуры, а ребра представляют собой отношения смежности областей.
            Соглашусь с любым более точным определением, мне самому его объясняли «на пальцах».
        • +2
          Спаибо за статью, интересная и много ссылок полезных для тех кто не вкурсе как оно там ищет пути. Кстати говоря, js реализация показывает разные роуты в зависимости от выбранного алгоритма, это означает что одни алгоритмы точнее других или же что существует несколько равнозначных путей?
          • 0
            не заметил статистику зеленым внизу слева :) зачастую Jump Point Search быстрее чем Best First Search в два раза :) здорово!
            • 0
              роуты конечно разные, остальные алгоритмы не всегда находят лучший путь в итоге.
              это алгоритм очень хорошо ищет и часто в разы меньше операций делает.
              • 0
                Вот что в разы быстрее я заметил, а что лучше ищет пока что не подобрал ситуацию при которой остальные алгоритмы выбирают не самый короткий путь. Если кто найдет повесте плиз скрин :) Любопытная штука эти алгоритмы поиска пути!
                • +5
                  image

                  image
                  • 0
                    а тогда сравнение некорректное, работающий алгоритм с медленным неработающим :)
                    • +2
                      почему некорректное то? и почему алгоритм не работающий?

                      путь найден, пусть и не самый оптимальный.
                      • 0
                        Потому что BFS не ищет оптимального пути вообще, он ищет любый.

                        Сравнивайте JPS с A*, они оба ищут оптимальные пути.
                        • 0
                          BFS ищет оптимальный в случае невзвешенного графа, ну либо когда вес всех рёбер одинаков. Не путайте с DFS.
                        • 0
                          Видимо, дело в том, что BFS вообще не умеет в классической реализации учитывать стоимость пути, а у нас здесь есть диагональные переходы, которые BFS может оценивать как 2 перехода стоимостью 1, либо 1 переход стоимостью 1. Нужно смотреть исходники.
                        • 0
                          Вот вам пример, хоть и разница не большая, но она есть

                          глянуть
                          image
                          image


                • +1
                  Наглядный пример. Очень быстрый поиск. Надо попробовать
                  • +1
                    Авторы словно черпали вдохновение из геометрического смысла эвристик для оценки расстояния в A*. Приятный результат.
                    • 0
                      Я так понял, в вашем алгоритме необходимо знать координаты цели? Т.е. применить его в случае, когда неизвестно, где ближайший сосед находится, не получится?
                      • 0
                        Ну для таких случаев обычно волновой поиск или алгоритм Дийкстры применяют. По ссылке есть примеры, как они работают.
                        Приведенный же в статье алгоритм можно применять в контексте игр, когда юниту задают конечную точку пути или когда надо вычислить поле, доступное для хода. На JS с астаром у меня это жрало местами оочень много процессора, что аж подвисало на секунду\другую. Надо попробовать этот алгоритм.
                      • 0
                        Алгоритм работает на неориентированном графе единой стоимости. Каждое поле карты имеет <= 8 соседей, которые могут быть проходимы или же нет.


                        Извините, если что-то не понял, до 8 связей это ограничение алгоритма или примера?
                        • +2
                          Откройте тетрадь в клеточку и посчитайте количество клеток вокруг любой клетки.
                          • +1
                            человек же не про тетрадь спрашивает а про графы. Можно ли адаптировать алгоритм под граф с 6ю связями?
                            • +2
                              Спасибо за содержательный ответ!

                              У автора в аннонсе есть важный момент:

                              Pathfinding is the problem of navigating from one place to another. My research in this area is primarily focused on single-agent pathfinding problems where the world is represented as a static 2-dimensional grid.


                              Т.е. алгоритм разменивает возможность А* не делать предположения о структуре графа на уменьшение потребления памяти. Значит, сфера применения этого алгоритма значительно уже, чем у А*.

                              Это и был ответ на мой вопрос выше, и, как мне кажется, это следует более явно подчеркнуть в статье, потому что предложение про неориентированный граф единой стоимости сбивает с толку.
                          • +1
                            Спасибо за описание алгоритма!
                            У меня некое непонимание терминологии возникло: «граф единой стоимости» означает, что все веса равны? Но чуть ниже: «Каждый шаг по направлению (по вертикали или по горизонтали) имеет стоимость 1; шаг по диагонали имеет стоимость √2».
                            • +1
                              Все верно. Длина (вес) шага по диагонали равна длине гипотенузы прямоугольного треугольника с катетами единичной длины.
                              • +1
                                Является ли переход по диагонали ребром графа?
                                Является ли граф с разным весом ребер «графом единой стоимости»?
                                Дайте, пожалуйста, определение графа единой стоимости (гугл, к сожалению, молчит)
                                • 0
                                  Да, пожалуй с «все верно» я поторопился, вопросы действительно есть.
                                  Пожалуй, не буду пытаться объяснить мое понимание данной ситуации, лучше дождаться пояснения автора статьи.
                                  • 0
                                    В принципе, насколько я понял алгоритм, пока переход по диагонали стоит больше 1 и меньше 2 все должно работать нормально. Просто хотел уточнить терминологию :)
                                  • 0
                                    Думаю речь о стоимости/проходимости клеток. А диагональные переходы имеют не стоимость, а коэффициент, чтобы приблизить карту к реальности. Т.е. данный алгоритм не позволяет искать путь в местности, которая содержит поля вперемешку с болотами. Потому как путь напрямую будет дольше, чем обходя болота.
                              • 0
                                «Данный алгоритм представлен в 2011 году, а в 2012 получил высокие отклики.»
                                Вопрос к хабранароду. Бота для стрелялки можно на таком реализовать? и на сколько это будет эффективно по сравнению с теми же нейросетями?
                                • 0
                                  Нейросети к ботам для стрелялки никакого отношения не имеют вообще. Алгоритм поиска, о котором тут идет речь, — одна маленькая и не факт, что всегда нужная деталь для бота — зависит от стрелялки.

                                  Вам нужны алгоритмы управления.
                                  • 0
                                    Со стрелялкой поторопился, уж больно много она в себя включает. Возьмем к примеру простое передвижение персонажа. Нейросеть по принципу обучения «Туда не ходи, сюда ходи» должна довольно не плохо работать, я не прав? Другое дело что при такой реализации все сводится к кропотливому обучению, либо же к хитро придуманному алгоритму автоматического обучения. В данной же статье описан метод, по которому имея только «маску» карты, мы сможем найти оптимальные пути передвижения.
                                    • 0
                                      Не правы, нет, в вопросах «куда ходить» — это либо алгоритм поиска, либо алгоритм управления типа reinforcement learning. Второй особенно хорош тем, что является одновременно и алгоритмом поиска, и алгоритмом управления, и самообучающимся алгоритмом.
                                      • 0
                                        Использовать нейронные сети на данный момент в игровом ИИ — это попытка охотиться на орла с ножом. В том смысле, что нейронные сети требуют обучения, и при этом при малейшем изменении исходных данных или изменения каких-либо игровых коэффициентов — полного переобучения. Учитывая при этом очень низкую скорость обучения НС до приемлемых результатов — фактически это становится невозможным.
                                        Если уж так хочется поиграть с «научным» ИИ в играх — попробуйте посмотреть в сторону генетических алгоритмов. По крайней мере, они могут помочь выработать оптимальную стратегию поведения и заложить ее в программу бота в зависимости от разных наборов входных данных. Но, опять же, для обучения этих ботов для «стрелялки» придется слишком много раз проводить игровые сессии, так что этот путь оптимален скорее для детерминированных игр вроде нард :)
                                        На практике же в игровом ИИ используются обычные портянки с кучей if-ов, case-ов и т.д., поскольку на данный момент только они способны адекватно отвечать требованиям к скорости работы.
                                  • +2
                                    Правильно я понимаю, что ключевое условие для алгоритма: единая стоимость графа? В случае, если оно не соблюдается — в общем случае — все равно применимым остается А*?

                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.