Алгоритмы поиска пути?

24

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

Какие алгоритмы поиска пути используются в играх всех типов? (В любом случае, из всех типов, в которых движутся персонажи) Дейкстра часто используется? Я бы подумал, что нет, поскольку на самом деле он не отслеживает шаги, которые нужно предпринять, чтобы добраться куда-то, верно? Если я правильно понимаю, это только определяет, какой объект является ближайшим. Я не собираюсь ничего кодировать; просто проведу какое-то исследование, хотя, если вы вставите псевдокод или что-то еще, это будет хорошо (я понимаю Java и C ++). Я в основном ищу быстрый обзор поиска пути в целом.

Я знаю, что A * подобен алгоритму для использования в 2D играх. Это здорово и все, но как насчет 2D-игр, которые не основаны на сетке? Такие вещи, как Эпоха Империй или Пробуждение Линка. Там нет отдельных квадратных мест для навигации, так что они делают?

Что делают 3D-игры? Я читал эту штуку http://www.ai-blog.net/archives/000152.html , которая, как я слышал, является большим авторитетом в этом вопросе, но на самом деле она не объясняет, КАК после установки сеток, поиск пути сделан. ЕСЛИ А * это то, что они используют, то как это происходит в трехмерной среде? И как именно работают сплайны для скругления углов?

Pojo
источник
2
Я думаю, что этот вопрос слишком открыт для формата вопросов и ответов SE. FAQ
Джон Макдональд
1
Игры, о которых вы упоминали, должны разбивать карту на узлы для A *, так или иначе. Этот процесс разбивки не должен включать сетки квадратов, и есть много способов сделать это. Проверьте этот vid youtube.com/watch?v=nGC_kBCoHYc , хорошая игра делает это так, чтобы игроки не могли сказать, что они на самом деле делает за кадром.
XiaoChuan Yu
1
Здесь много вопросов, поэтому я не могу написать ответ, но отмечу, что Дейкстра возвращает путь, и большинство алгоритмов поиска путей являются многоцелевыми. Вы преобразуете свой мир, 2D или 3D, в связанный граф и запускаете на нем алгоритм поиска пути.
Грегори Эйвери-Вейр
Просто для справки: я ответил на вопрос в переполнении стека .
Джулиан,
1
Разрешите мне разглагольствовать. Этот вопрос получил 4 отзыва на SO, по сравнению с 4 близкими голосами здесь на GDSE. Я не могу не чувствовать, что модераторы на этом сайте чрезмерно агрессивны. Конечно, я вижу, как вопрос идет вразрез с руководящими принципами, указанными в FAQ, но, цитируя, эти руководящие принципы существуют для предотвращения diminishing the usefulness of our site. Этот вопрос был одобрен уже 3 раза, что является доказательством того, что он был полезен для некоторых пользователей. Так что я не могу не чувствовать, что голосование за его закрытие и риск возможного удаления намного более контрпродуктивны.
Дэвид Гувея

Ответы:

62

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


Часть 1 - Алгоритмы поиска пути

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

  • Примитивные методы, которые не «смотрят в будущее» и делают один шаг за раз:

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

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

  • Методы, которые смотрят вперед, чтобы найти весь путь сразу:

    • Поиск в ширину - Простой обход графика, посещая каждый слой потомков, останавливайтесь, когда путь найден. Если график невзвешенный (то есть расстояние между каждым смежным узлом всегда одинаково), он находит кратчайший путь, хотя и не слишком эффективно. Для взвешенных графов он может не возвращать кратчайший путь, но всегда найдет его, если он существует.

    • Поиск в глубину - еще один способ пройти по графику, но вместо того, чтобы разбирать его по слоям, алгоритм сначала пытается найти его глубоко. Этот метод может иметь проблемы, если глубина поиска не ограничена, особенно при использовании рекурсивной реализации, что может привести к переполнению стека, поэтому обычно безопаснее реализовать его итеративно с использованием стека.

    • Поиск в первую очередь - аналогично поиску в ширину, но использует эвристику, которая сначала выбирает наиболее перспективного соседа. Возвращенный путь может быть не самым коротким, но он выполняется быстрее, чем поиск в ширину. A * - это тип Best First Search.

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

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

  • Кроме того, существуют варианты A * (или оптимизация поиска пути в целом), которые делают его более быстрым или более приспособленным к определенным обстоятельствам, таким как (см. Связанный ответ и полный список на cstheory.SE ):

    • LPA * - аналогичен A *, но может быстрее пересчитать лучший путь, если сделать небольшое изменение в графике
    • D * Lite - основанный на LPA *, он делает то же самое, но предполагает, что «начальная точка» - это единица, движущаяся к финишу во время изменения графика
    • HPA * (иерархический) - использует несколько слоев на разных уровнях абстракции для ускорения поиска. Например, слой более высокого уровня может просто соединять комнаты, тогда как слой более низкого уровня заботится о том, чтобы избегать препятствий.
    • IDA * (Итеративное углубление) - уменьшает использование памяти по сравнению с обычным A *, используя итеративное углубление.
    • SMA * (Упрощенная ограниченная память) - использует только доступную память для выполнения поиска.
    • Jump Point Search - Кредиты Эрику в комментариях за упоминание об этом! Ускоряет поиск путей на сеточных картах с равномерной стоимостью ( ссылка ).

Часть 2 - Представление пространства поиска

И наконец, чтобы ответить на этот вопрос:

Я знаю, что A * подобен алгоритму для использования в 2D играх. Это здорово и все, но как насчет 2D-игр, которые не основаны на сетке?

Два больших заблуждения здесь! По факту:

  1. A * не волнует, является ли игра 2D или 3D, и одинаково подходит для обоих случаев.
  2. A * работает в любом графическом представлении, поэтому ему все равно, является ли мир сеткой или нет.

Так что, если миру не нужно быть сеткой, какими еще способами вы можете его представить? Вот краткий обзор способов разделения мирового пространства для поиска путей, и большинство из них работают как для 2D, так и для 3D:

  • Прямоугольная сетка - Разделение мира на регулярную сетку квадратов, где каждая ячейка в сетке является одним узлом на графике, а связь между двумя свободными узлами является ребром.

    введите описание изображения здесь

  • Quadtree - еще один способ разделить пространство, но вместо разделения на сетку ячеек обычного размера, разделить на четыре, а затем рекурсивно разделить каждый из них на четыре снова. Добавление третьего измерения делает его октреем .

    введите описание изображения здесь

  • Выпуклые многоугольники - Разделение зоны прохождения на сетку из взаимосвязанных выпуклых многоугольников. Каждый многоугольник становится узлом, а общие ребра являются ребрами графа. Например, это могут быть треугольники, а иногда даже сетка, созданная художником при создании активов уровня. Часто упоминается как навигационная сетка . Смотрите эту ссылку . Вот очень популярный набор инструментов для построения сетки навигации: Recast .

    введите описание изображения здесь

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

    введите описание изображения здесь

Дэвид Гувея
источник
1
Две ссылки: 1) Микко Мононен выполнил работу по поиску пути в Killzone 3 , и у него есть очень хороший блог, где он документирует процесс разработки Recast (генератор navmesh) и Detour (инструментарий поиска пути), оба под лицензией MIT и используются, например, в королевствах Амалур: расплата . 2) Поиск точек перехода , я думаю, является одним из крупнейших недавних разработок в области поиска путей на основе сетки.
Эрик