How to become an author
Search
Write a publication
Pull to refresh

Поиск пути среди круглых препятствий

Reading time9 min
Views14K
Programming*Game development*Algorithms*
Translation
Original author: Amit Patel

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


Алгоритм поиска пути 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, написанную Томасом Янгом. В этой главе рассматривается отсечение узлов, но не для кругов, а для многоугольников.

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


Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 46: ↑46 and ↓0+46
Comments15
1749
Karma
6
Rating
@PatientZero

Переводчик-фрилансер

Send message

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr