15.05.2019 09:05
PatientZero 13 6800 Источник

Навигация по лесу


Алгоритм поиска пути A* — это мощный инструмент для быстрой генерации оптимальных путей. Обычно A* демонстрируют при навигации по картам из сеток, но он может использоваться не только для сеток! Он может работать с любыми графами. Можно использовать A* для поиска пути в мире круглых препятствий.


В оригинале статьи все изображения интерактивны.

Как один алгоритм решает обе эти задачи? Давайте начнём с краткого описания того, как работает A*.

Алгоритм A*


Алгоритм A* находит оптимальный путь из начальной в конечную точку, избегая по дороге препятствия. Он реализует это, постепенно расширяя множество частичных путей. Каждый частичный путь — это серия шагов от начальной точки до какой-то промежуточной точки на дороге к цели. В процессе работы A* частичные пути становятся всё ближе конечной точке. Алгоритм прекращает работу тогда, когда находит полный путь, который лучше оставшихся вариантов, и это можно доказать.

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

Когда A* начинает работу, очередь с приоритетами содержит всего один частичный путь: начальную точку. Алгоритм многократно удаляет из очереди с приоритетами наиболее многообещающий путь, то есть путь с наименьшей приблизительной длиной. Если этот путь завершается в конечной точке, то алгоритм выполнил задачу — очередь с приоритетами гарантирует, что никакой другой путь не может быть лучше. В противном случае, начиная с конца частичного пути, который он удалил из очереди, A* генерирует ещё несколько новых путей, делая единичные шаги во всех возможных направлениях. Он помещает эти новые пути снова в очередь с приоритетами и начинает процесс заново.

Граф


A* работает с графом: набором узлов, соединённых рёбрами. В мире на основе сетки каждый узел обозначает отдельную ячейку сетки, а каждое ребро — соединение с соседними ячейками к северу, югу, востоку или западу.

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

Путь через граф — это серия узлов, соединённых рёбрами:


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

Далее мы исследуем простой способ преобразования леса с препятствиями в граф: сгенерируем все возможные рёбра перехода и огибающие рёбра.


Генерация рёбер перехода


Рёбра перехода между парой кругов — это отрезки прямых, которые едва касаются обоих кругов; такие отрезки называются касательными к двум точкам, и для каждой пары кругов существует четыре таких касательных. Касательные к двум точкам, пересекающиеся между кругами, называются внутренними касательными к двум точкам, а проходящие снаружи — внешними.

Внутренние касательные к двум точкам


В прошлом поиск внутренних касательных был важен для вычисления длины ремня, соединяющего два шкива разного размера, поэтому задача создания внутренних касательных к двум точкам называется задачей ремней. Для нахождения внутренних касательных к двум точкам нужно вычислить угол $\theta$ на показанном ниже чертеже.


Как оказалось, для кругов с центрами $A$ и $B$ и радиусами $r_A$ и $r_B$, центры которых находятся на расстоянии $d$:

$\theta = \arccos{{r_A+r_B}\over{d}}$


Определив $\theta$, мы можем легко найти точки $C$, $D$, $E$ и $F$.

Внешние касательные к двум точкам


При построении внешних касательных (это задача шкивов) используется похожая техника.


Для внешних касательных мы можем найти $\theta$ следующим образом:

$\theta = \arccos{{\lvert r_A - r_B \rvert} \over d}$


Не важно, какой из кругов больше, A или B, но как видно из рисунка, $\theta$ откладывается на стороне A, ближней к B, но на стороне B, дальней от A.

Линия видимости


Взятые вместе, внутренние и внешние касательные к двум точкам между двумя кругами образуют рёбра перехода между кругами. Но что если одно или несколько рёбер перехода закрывает третий круг?


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

Для вычисления расстояния от точки $C$ до отрезка прямой $\overline{AB}$ воспользуемся следующим способом:

Во-первых, вычислим $u$ — часть расстояния вдоль отрезка $\overline{AB}$, в которой перпендикуляр пересекает точку $C$:

$u = {(C - A) \cdot (B-A) \over (B-A)\cdot(B-A)}$


Затем вычисляем позицию $E$ на $\overline{AB}$:

$E = A + \mathrm{clamp}(u, 0, 1) * (B - A)$




Расстояние $d$ от $C$ до отрезка $\overline{AB}$ — это расстояние от $C$ до $E$:

$d = \|E - C\|$


Так как $d < r$, круг перекрывает линию видимости из $A$ в $B$, и ребро необходимо отбросить. Если $d \ge r$, то линия видимости из $A$ в $B$ существует, и ребро следует оставить.

Генерация огибающих рёбер


Узлы графа соединяют ребро перехода с огибающим ребром. В предыдущих разделах мы сгенерировали рёбра перехода. Для генерации огибающих рёбер мы начнём с конечной точки ребра перехода, обойдём круг и закончим в конечной точке другого ребра перехода.


Для нахождения множества огибающих рёбер круга сначала найдём все касающиеся круга рёбра перехода. Затем создадим огибающие рёбра между всеми конечными точками рёбер перехода на круге.

Соединяем всё вместе


Сгенерировав рёбра перехода, огибающие рёбра и узлы, а затем отбросив все перекрытые рёбра перехода, мы можем создать граф и запустить поиск пути с помощью алгоритма A*.


Усовершенствования


Рассмотренная нами процедура генерации графа достаточно хорошо работает для объяснения алгоритма, но во многих аспектах может быть улучшена. Такие улучшения позволят алгоритму тратить меньше ресурсов процессора и памяти, а также обрабатывать больше ситуаций. Давайте рассмотрим некоторые из ситуаций.

Препятствия, которые касаются друг друга


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

Касательные к двум точкам


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

$\theta = \arccos{{r_A+r_B}\over{d}}$


и формулы для внешних касательных:

$\theta = \arccos{{\lvert r_A - r_B \rvert} \over d}$


Когда два круга касаются друг друга или пересекаются, то между ними нет внутренних касательных. В таком случае ${r_A+r_B}\over d$ больше единицы. Так как значение арккосинуса за пределами области определения $[-1, 1]$ не определено, перед нахождением арккосинуса важно выполнять проверку пересечения кругов.

Аналогично этому, если один круг полностью расположен в другом, то между ними не будет внешних касательных. В таком случае ${r_A - r_B} \over d$ находится вне интервала $[-1, 1]$, то есть не имеет арккосинуса.


Линия видимости ребра перехода


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

Вспомним вычисление $u$ — части расстояния вдоль ребра перехода, на котором перпендикуляр к точке касается ребра. Если касание кругов не допускается, то значение $u$ находится вне интервала $[0,1]$, то есть круг не может касаться ребра, потому что для этого ему нужно было бы касаться одной из конечных точек ребра. Это невозможно, потому что конечные точки ребра уже являются касательными к другим кругам.

Однако если мы допустим возможность наложения кругов, то значения $u$ вне интервала $[0,1]$ смогут перекрывать линию видимости вдоль ребра. Это соответствует случаям, когда круг находится за концом ребра перехода, но перекрывает конечную точку или касается её. Чтобы отслеживать такие случаи математически, мы ограничим $u$ интервалом $[0,1]$:

$E = A + clamp(u, 0, 1) * (B - A)$


Линия видимости огибающего ребра


Когда препятствия могут касаться друг друга или пересекаться, огибающие рёбра могут быть заблокированы препятствиями так же, как и рёбра перехода. Рассмотрим огибающее ребро с рисунка ниже. Если огибающего ребра касается другое препятствие, то ребро блокируется и должно быть отброшено.


Чтобы определить, заблокировано ли огибающее ребро другим препятствием, воспользуемся следующим методом для определения точек, в которых пересекаются два круга. Если круги имеют центры в точках $A$ и $B$ и радиусы $r_A$ и $r_B$, где $d$ — расстояние между $A$ и $B$, то нам для начала нужно проверить несколько случаев. Если круги не касаются друг друга (то есть $d > r_A + r_B$),
находятся один внутри другого ($d < |r_A - r_B|$) или совпадают ($d = 0$ и $r_A = r_B$), то круги не могут влиять на огибающие рёбра друг друга.

Если не одно из этих условий не соблюдается, то круги пересекаются в двух точках; если круги касаются друг друга, то эти две точки совпадают. Рассмотрим радикальную ось, соединяющую точки пересечения; она перпендикулярна прямой, соединяющей $A$ и $B$, в какой-то точке $C$. Мы можем вычислить расстояние $a$ от $A$ до $C$ следующим образом:

$a = {r_A^2 - r_B^2 + d^2 \over 2d }$


Найдя $a$, мы можем найти угол $\theta$:

$\theta = \arccos {a \over r_A}$


Если $\theta$ равен нулю, то круги касаются в точке $C$. В противном случае существует две точки пересечения, соответствующие положительному и отрицательному $\theta$.


Далее определим, находится ли какая-нибудь из точек пересечения между начальной и конечной точками огибающего ребра. Если это так, то препятствие блокирует огибающее ребро, и мы должны отбросить это ребро. Заметьте, что нам не нужно рассматривать случай, когда огибающее ребро целиком находится внутри препятствия, потому что отсечение по линии видимости для рёбер перехода уже отбросило это ребро.

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

Переменный радиус актора и расширение Минковского


При вычислении навигации круглого объекта в мире круглых препятствий можно учесть наблюдения, упрощающих решение задачи. Во-первых, можно упростить работу, заметив, что движение круга радиусом r по лесу аналогично движению точки через тот же лес с единственным изменением: радиус каждого препятствия увеличивается на r. Это чрезвычайно простой случай применения суммы Минковского. Если радиус актора больше нуля, то перед началом мы просто увеличиваем размер препятствий.

Отложенная генерация рёбер


В общем случае граф для леса из $n$ препятствий содержит $O(n^2)$ рёбер перехода, но так как каждое из них нужно проверить на линию видимости с $n$ препятствиями, то общее время генерации графа равно $O(n^3)$. Кроме того, пары рёбер перехода могут приводить к созданию огибающих рёбер, и каждое из них нужно проверить с каждым препятствием на линию видимости. Однако из-за высокой эффективности алгоритма A* обычно для создания оптимального пути он просматривает только часть этого большого графа.

Мы можем сэкономить время, генерируя небольшие части графа на лету в процессе выполнения алгоритма A*, а не делая всю работу заранее. Если A* найдёт путь быстро, то мы сгенерируем только малую часть графа. Мы реализуем это, переместив генерацию рёбер в функцию neighbors().

Существует несколько случаев. В начале алгоритма нам нужны соседи начальной точки. Это рёбра перехода от начальной точки к левому и правому ребру каждого препятствия.

Следующий случай — когда A* только что добрался до точки $p$ на ребре препятствия $C$ вдоль ребра перехода: neighbors() должна вернуть огибающие рёбра, ведущие из $p$. Для этого мы определим, какие рёбра перехода выходят из препятствия, вычислив касательные к двум точкам между $C$ и всеми остальными препятствиями, отбросив все те, которые не находятся на линии видимости. Затем найдём все огибающие рёбра, соединяющие $p$ с этими рёбрами перехода, отбросив те, которые блокированы другими препятствиями. Возвращаем все эти огибающие рёбра,, сохраняя рёбра перехода для возврата в последующем вызове neighbors().

Последний случай — когда A* обошёл огибающее ребро вдоль препятствия $C$ и ему нужно покинуть $C$ по ребру перехода. Так как предыдущий этап вычислил и сохранил все рёбра перехода, можно просто найти и возвратить правильное множество рёбер.

Отсекаем заострённые огибающие рёбра


Огибающие рёбра соединяют рёбра перехода, касающиеся одного круга, но оказывается, что многие из таких огибающих рёбер не подходят для использования в оптимальном пути. Мы можем ускорить алгоритм, устранив их.

Оптимальный путь через лес препятствий всегда состоит из перемежающихся рёбер перехода и огибающих рёбер. Допустим мы входим в узел $A$ и решаем, как из него выйти:


Вход через $A$ означает, что мы движемся по часовой стрелке ($\circlearrowright$). Мы должны выйти через узел, который позволяет нам продолжать двигаться по часовой стрелке ($\circlearrowright$), то есть мы можем выйти только через узел $B$ или $D$. Если выйти через $C$, то создастся перегиб ($\curlywedge$) пути, что никогда не будет оптимальным. Нам нужно отфильтровывать такие заострённые рёбра.

Для начала заметим, что A* и так обрабатывает каждое неориентированное ребро $P \longleftrightarrow Q$ как два ориентированных ребра, $P \longrightarrow Q$ и $Q \longrightarrow P$. Мы можем воспользоваться этим, пометив рёбра и узлы ориентацией.

  1. Узлы $P$ становятся узлами с ориентацией — по часовой ($P\circlearrowright$) или против часовой ($P\circlearrowleft$) стрелки.
  2. Неориентированные рёбра перехода $P \longleftrightarrow Q$ становятся ориентированными рёбрами $P,p \longrightarrow Q,\hat{q}$ и $Q,q \longrightarrow P,\hat{p}$, где $p$ и $q$ — это ориентации, а $\hat{x}$ означает направление, противоположное $x$.
  3. Неориентированные огибающие рёбра $P \longleftrightarrow Q$ становятся ориентированными рёбрами $P\circlearrowright \longrightarrow Q\circlearrowright$ и $P\circlearrowleft \longrightarrow Q\circlearrowleft$. Именно здесь происходит фильтрация: мы не включаем $P\circlearrowright \longrightarrow Q\circlearrowleft$ и $P\circlearrowleft \longrightarrow Q\circlearrowright$, потому что смена направления создаёт перегибы ($\curlywedge$).

В нашей схеме узел $A$ превратится в два узла, $A\circlearrowright$ и $A\circlearrowleft$, он имеет входящее ребро перехода $\longrightarrow A\circlearrowright$ и исходящее ребро перехода $A\circlearrowleft \longrightarrow$. Если мы попали на путь через $A\circlearrowright$, то должны выйти через узел $\circlearrowright$, который будет или ребром перехода $B\circlearrowright \longrightarrow$ (через огибающее ребро $A\circlearrowright \longrightarrow B\circlearrowright$), или ребро перехода $D\circlearrowright \longrightarrow$ (через огибающее ребро $A\circlearrowright \longrightarrow D\circlearrowright$). Мы не можем выйти через $C\circlearrowleft \longrightarrow$, потому что так изменится направление поворота, и мы отфильтровали огибающее ребро $A\circlearrowright \longrightarrow C\circlearrowleft$.

Отфильтровав из графа эти заострённые огибающие рёбра, мы повысили эффективность алгоритма.

Отсечение пересекающих рёбер


Можно отсекать частичные пути, последние рёбра перехода которых пересекают предпоследнее ребро перехода.

Многоугольные препятствия


См. Game Programming Gems 2, Chapter 3.10, Optimizing Points-of-Visibility Pathfinding, написанную Томасом Янгом. В этой главе рассматривается отсечение узлов, но не для кругов, а для многоугольников.

Справочные материалы


Комментарии (13)


  1. SidMeier
    15.05.2019 12:38
    #20155512

    А что мешает сгенерировать сетку и проверить её узлы на перекрытие объектами?
    Кроме того в подобных реализациях есть проблема движения «по стеночке». Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё.


    1. BigBeaver
      16.05.2019 01:35
      #20158852

      А что мешает сгенерировать сетку
      Расход памяти?
      Довольно часто бывает что оптимальнее обойти кучку препятствий
      Можете привести пример, когда это не будет частным случаем алгоритма из статьи?


      1. SidMeier
        16.05.2019 08:46
        #20159308

        qiao.github.io/PathFinding.js/visual
        там есть возможность посмотреть примеры поиска используя разные алгоритмы:

        trace
        image


        1. BigBeaver
          16.05.2019 12:08
          #20160352

          Так вы привели тот же самый алгоритм (А*). А зачем вы привели trace, для меня загадка.

          проблема в том, что все точки графа привязаны к препятствиям и нет свободных точек.
          А в чем проблема-то? Не трудно доказать, что любой кратчайший путь будет касаться хотя бы одного из препятствий. У вас на сетке он (А*) точно также идет по стеночке (еще и не кратчайшим путем). При этом решение из сабжа позволяет работать с бесконечной точностью без роста накладных расходов.

          Я, может, туплю, но имхо, за динамическую генерацию сетки вы будете расплачиваться качеством найденного пути. За размер ячеек вы тоже будете расплачиваться. И все равно расход ресурсов у вас будет выше на хоть сколько-то вменяемых размерах данных. В том числе потому, что вы будете генерировать по целой пачке ячеек на пустые линии без препятствий.


    1. Cerberuser
      16.05.2019 06:41
      #20159064

      Довольно часто бывает что оптимальнее обойти кучку препятствий, чем строить маршрут через неё

      Имеете в виду, что может быть выгоднее сгенерировать неоптимальный по длине путь "в обход", чем долго возиться с большим количеством шагов на оптимальном пути "между препятствиями"?


  1. samodum
    15.05.2019 15:08
    #20156400

    Очень круто


  1. OsipovRoman
    15.05.2019 17:26
    #20157222

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


  1. AVI-crak
    15.05.2019 17:31
    #20157246

    Прошло почти 20 лет, а алгоритмы обхода препятствий реализованные в трассировщике спектра — так и не смогли повторить, скопировать, или украсть. А между прочим, там всё это есть…


    1. Zenitchik
      15.05.2019 17:44
      #20157320
      +1

      Ссылочку можно?


      1. findoff
        16.05.2019 00:57
        #20158788

        Предполагаю что речь об этом, но насчет не смогли ли, не уверен.
        Сам не использовал, а по картинкам, вроде бы ничего революционного.


        1. AVI-crak
          16.05.2019 05:28
          #20158988

          А я использую.
          После составления правил трассировки — остаётся только дождаться результата. Намного приятнее ручной разводки. Причём если вы попробуете найти автоматическую разводку с современных пакетах до 1000$ — то подобного качества не обнаружится.
          В более дорогих есть, и там используется та-же спектра.


  1. abar
    16.05.2019 01:06
    #20158822

    Хороший перевод, вспомнил, что-то подобное смотрел в диздоке (или журнале разработчиков?) Left For Dead'а. Там как раз выводили алгоритмы что бы зомби бежали за игроками при этом красиво огибая препятствия и не сильно друг в друга врезаясь. Надо поискать, должно же быть полезно даже теперь…


  1. santa324
    16.05.2019 11:55
    #20160280

    Интересно! Я так понимаю что строится фактически аналог графа видимости в полигоне с дырками, только для круглых препятствий. Думаю, в статье не помешало бы упоминание этого и сравнение с ним.