A * Навигация по сетке

15

Итак, я делаю эту 2D-Java-игру сверху вниз в этой среде под названием Greenfoot, и я работаю над ИИ для парней, с которыми вы собираетесь сражаться. Я хочу, чтобы они могли реально перемещаться по всему миру, поэтому вскоре я понял, что, помимо всего прочего, мне понадобится поиск пути.

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

Я намерен использовать навигационную сетку по всем причинам, изложенным в этом посте на ai-blog.net . Однако проблема, с которой я столкнулся, заключается в том, что то, что A * считает самым коротким путем от центров / ребер многоугольника, не обязательно является самым коротким путем, если вы проходите через любую часть узла. Чтобы получить лучшее представление, вы можете увидеть вопрос, который я задал на stackoverflow .

Я получил хороший ответ относительно графика видимости. С тех пор я приобрел книгу ( Вычислительная геометрия: алгоритмы и приложения ) и углубился в эту тему, однако все еще поддерживаю навигационную сетку (см. « Управление сложностью » из заметок Амит о поиске пути ). (В качестве примечания, возможно, я мог бы использовать Theta * для преобразования нескольких путевых точек в одну прямую линию, если первая и последняя не закрыты. Или каждый раз, когда я возвращаюсь назад, проверяю путевую точку до последней, чтобы увидеть, могу ли я идти прямо из что к этому)

Поэтому в основном я хочу навигационную сетку, где, как только я проведу ее с помощью алгоритма воронки (например, от Digesting Duck ), я получу истинный кратчайший путь, а не тот, который является кратчайшим путем, следующим только от узла к узлу, но не самый короткий, учитывая, что вы можете пройти через несколько полигонов и пропустить узлы / ребра.

Да, и я также хочу знать, как вы предлагаете хранить информацию о полигонах. Для примера прототипа путевой точки, который я сделал, я просто использовал каждый узел в качестве объекта и сохранял список всех других узлов, на которые вы могли бы перейти с этого узла, я полагаю, что это не будет работать с полигонами? и как я могу сказать, если многоугольник открыт / проходим или это твердый объект? Как мне сохранить, какие узлы составляют многоугольник?

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

angrydust
источник
Я не уверен, но эти ссылки могут помочь: gamedev.stackexchange.com/questions/1327/… gamedev.stackexchange.com/questions/8087/… также был другой вопрос о поиске пути, который я не могу найти прямо сейчас , который получил награду и получил очень хороший ответ.
Ali1S232
Да, во второй ссылке вы видите мою главную проблему: алгоритм A * дает путь вокруг дна как самый короткий с использованием краевых средних точек, но путь вокруг вершины препятствия на самом деле самый короткий. Я хочу знать, как я могу получить A *, чтобы дать мне путь вокруг вершины, который я затем выпрямлю (например, с помощью алгоритма воронки), чтобы получить истинно кратчайший путь, где, как если бы он давал мне тот, что ниже даже если я выпрямлюсь, это все равно идет в обход.
angrydust
На самом деле, я только что прочитал статью в gamedev.stackexchange.com/questions/8087/… и, похоже, она работает, находя маршрут с помощью A *, затем вычисляя его истинную стоимость с помощью модифицированного алгоритма воронки, а затем находя другой маршрут и вычисляя его Истинная стоимость снова и посмотреть, если она немного короче, чем другой. Он повторяется, пока не узнает, что найден кратчайший маршрут. Это действительно решает мою проблему, однако, похоже, что это будет довольно медленно, так как вы повторяете как выпрямление, так и поиск пути, что будет довольно дорого.
angrydust
Хранение полигонов: сохраняйте только видимые полигоны - или связывайте тег с каждым полигоном (помните, что каждый полигон должен быть круговым списком вершин); Точно так же с узлами вы можете хранить идентификатор полигона, из которого они происходят, но мне не нужно говорить вам это: это элементарное хранилище данных. Наконец, почему вы заботитесь о самом коротком пути? Ваша игра может работать медленно, или у вас могут быть немного неправильные пути: выберите один. Получение истинного кратчайшего пути ТРЕБУЕТ полного поиска в ширину (по крайней мере, по графу узлов).
Джонатан Дикинсон
@JonathanDickinson Я знаю , что я не нужен путь , который будет 100% с точностью до последнего пикселя, и я знаю , что я могу использовать * для получения пути , которые будут в большем р допустима. Дело в том, чтобы обойти препятствие так ясно, как в моем предыдущем вопросе о переполнении стека или в gamedev.stackexchange.com/questions/8087/… просто слишком много. Я не могу позволить своему ИИ обойти препятствие!
angrydust

Ответы:

14

Я бы посоветовал, что даже если вы собираетесь написать весь свой собственный код, вы загружаете Recast и создаете пример приложения, поскольку оно имеет визуализации, которые показывают сгенерированную навигационную сетку, и это позволяет вам проверить поиск пути с простой точкой и нажать интерфейс. Вы можете многому научиться, просто играя с этим.

Как вы уже поняли, есть два шага для создания хорошо выглядящего пути - поиск пути A *, а затем последующая постобработка, которая включает в себя выпрямление пути (устранение любых поворотов, необязательных для избежания препятствий) и, возможно, также добавление кривых в поворотных точках.

Найти путь

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

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

Следующее простейшее решение - выполнить A * от края до края через сетку. Вам будет проще думать об этом, если вы представите, что вместо одного узла на полигон у вас есть один на ребро на полигон. Таким образом, ваш путь идет от начальной точки к ближайшему ребру, пересекается с внутренним краем соседнего многоугольника, а затем прямо со следующего ребра в том же многоугольнике и так далее. Это создает кратчайший путь чаще, а также имеет преимущество в том, что его можно обойти, если вы не хотите выполнять этап выпрямления пути.

Выправление пути

Алгоритм, используемый в Detour (навигационная библиотека, сопровождающая Recast), довольно прост. Вы должны заметить, что он будет выравнивать путь только в пределах полигонов, найденных во время поиска A *. Таким образом, если это не поможет найти самый трудный путь вокруг препятствия, вы не получите жесткий путь и после запуска этого алгоритма. На практике навигационные сетки, создаваемые с помощью преобразования, имеют тенденцию иметь один многоугольник, через который вы можете пройти при навигации по дроссельной точке (ближайшей точке между двумя препятствиями), и поэтому A * всегда будет создавать список узлов, которые расположены так близко к препятствию, как возможно. Если вы используете плитки в качестве навигационной сетки, этого не произойдет, и этот очень простой алгоритм будет вставлять ложные повороты.

Алгоритм выпрямления траектории Detour не достаточно сложен, потому что, когда он определяет, что ему нужно вставить поворот, он вставляет его в точку, где он в последний раз затягивал воронку влево (при повороте влево и наоборот) и затем снова начинает трассировку через узлы с этой точки.

Если вы хотите выровнять путь вне полигонов, которые составляют часть маршрута A *, все становится намного сложнее. Вам нужно будет реализовать процедуру приведения лучей, которая может проверить, могут ли две точки в вашей сетке видеть друг друга (в любом случае это должно быть у вас, чтобы вы могли увидеть, нужно ли вообще использовать A *). Вы делаете это, пересекая отрезок линии, образованный origin-> target, с соединительными ребрами многоугольника, содержащего начало координат, затем проверяя соединительные ребра многоугольника, который перемещает вас, и так далее. Если вы пересекаете не соединяющий край (я называю их граничными краями), то вы столкнулись с препятствием.

Затем вы можете выполнить этот тест на приведение лучей всякий раз, когда алгоритм воронки определяет, что ему нужно вставить поворот, чтобы увидеть, действительно ли он выполняется, но я думаю, что вам придется продолжать выполнять этот тест на каждом узле, пока вы не вставите поворот (в в какой момент вы можете вернуться к простому алгоритму воронки). Это будет дорого стоить, выпрямляя путь примерно O (n ^ 2).

Представляя навмешь

Вы можете представить свою сетку как массив классов полигонов. Класс многоугольника может быть таким же простым, как массив вершин и массив ссылок на соседний многоугольник для каждого ребра, если таковой имеется. Конечно, вы, вероятно, можете придумать способы сохранить это более компактно. Поскольку вершина обычно совместно используется несколькими полигонами, обычно иметь один большой массив вершин, а затем каждый индекс полигона сохраняет индексы в этом массиве. В зависимости от характеристик вашей сетки, у вас может быть среднее количество соединительных ребер, которое составляет не более 50% от числа ребер. В этом случае вы можете сохранить ссылку на другой многоугольник и индекс ребра, а не сохранять ссылку для каждого ребра. Также я рекомендую хранить индекс многоугольника в массиве многоугольников navmesh, а не использовать ссылку на класс.

U62
источник
Я только что кратко прочитал об этом, но я понимаю, что вы никогда не должны использовать квадрат расстояния (или не квадратный корень из него) для A *: теория.stanford.edu
~
Меня не очень волнует вопрос о том, как на самом деле идти по пути выпрямления, но меня беспокоит то, что вы говорите: «Вы должны заметить, что это будет только выпрямлять путь в пределах полигонов, найденных во время поиска A *». Таким образом, если это не поможет найти самый трудный путь вокруг препятствия, вы не сможете получить жесткий путь и после запуска этого алгоритма ».
angrydust
Я хочу иметь навигационную сетку, где A * всегда найдет путь, который после выпрямления является самым коротким, независимо от стоимости проезда через вершины / средние точки. Я ценю, что это можно сделать с помощью графика видимости, но я хочу использовать навигационную сетку, потому что она имеет много других преимуществ и потому, что сложность графика видимости может очень быстро возрасти
angrydust
@theguywholikeslinux вы можете использовать евклидово расстояние sqrt(x*x + y*y)- но не дешевле на узел x*x + y*y.
Джонатан Дикинсон
@JonathanDickinson Я знаю, отсюда и моя точка зрения.
angrydust