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

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

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

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

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

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

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

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

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

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

Найти путь

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

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

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

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

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

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

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

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

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

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