Как я могу сделать финиш A * быстрее, когда пункт назначения непроходим?

31

Я делаю простую 2D-игру на основе тайлов, в которой используется алгоритм поиска пути A * («Звезда»). У меня все работает правильно, но у меня проблемы с производительностью поиска. Проще говоря, когда я щелкаю непроходимую плитку, алгоритм, очевидно, проходит по всей карте, чтобы найти маршрут к непроходимой плитке, даже если я стою рядом с ней.

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

user2499946
источник
2
Знаете ли вы, какие плитки непроходимы, или вы просто знаете это в результате алгоритма AStar?
user000user
Как вы храните свой навигационный график?
Анко
Если вы храните пройденные узлы в списках, вы можете использовать двоичные кучи для повышения скорости.
ChrisC
Если это просто слишком медленно, я могу предложить ряд оптимизаций - или вы вообще пытаетесь избежать поисков?
Стивен
1
Этот вопрос, вероятно, был бы лучше подходит для компьютерных наук .
Рафаэль

Ответы:

45

Некоторые идеи об избежании поисков, которые приводят к ошибочным путям в целом:

ID острова

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

Ограничить верхнюю границу

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

Если вы обнаружите, что это занимает слишком много времени, тогда полезны следующие методы:

Сделайте это асинхронным и ограничить итерации

Пусть поиск запускается в отдельном потоке или немного в каждом кадре, чтобы игра не застыла в ожидании поиска. Отобразите анимацию персонажа, царапающего голову или топающего ноги, или чего-либо подходящего в ожидании окончания поиска. Чтобы сделать это эффективно, я бы сохранил состояние поиска как отдельный объект и учел бы существование нескольких состояний. Когда запрашивается путь, возьмите объект свободного состояния и добавьте его в очередь активных объектов состояния. В своем обновлении поиска пути вытяните активный элемент из передней части очереди и запускайте A *, пока не будет завершено либо A., либо B. Выполнено некоторое ограничение итераций. Если завершено, поместите объект состояния обратно в список свободных объектов состояния. Если он еще не завершен, поместите его в конец «активных поисков» и переходите к следующему.

Выберите правильные структуры данных

Убедитесь, что вы используете правильные структуры данных. Вот как работает мой StateObject. Все мои узлы предварительно выделены для конечного числа - скажем, 1024 или 2048 - по соображениям производительности. Я использую пул узлов, который ускоряет распределение узлов, и это также позволяет мне хранить индексы вместо указателей в моих структурах данных, которые являются u16s (или u8, если у меня есть максимум 255 узлов, что я делаю в некоторых играх). Для поиска пути я использую приоритетную очередь для открытого списка, сохраняя указатели на объекты Node. Он реализован в виде двоичной кучи, и я сортирую значения с плавающей запятой в виде целых чисел, поскольку они всегда положительны, а моя платформа имеет медленные сравнения с плавающей запятой. Я использую хеш-таблицу для своей закрытой карты, чтобы отслеживать узлы, которые я посетил. Он сохраняет NodeID, а не Nodes, чтобы сэкономить на размерах кэша.

Кеш что можешь

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

Другие области, которые вы можете исследовать: используйте двусторонний поиск пути для поиска с любого конца. Я не сделал этого, но, как другие заметили, это может помочь, но не без предостережений. Другая вещь в моем списке, чтобы попробовать это иерархический поиск пути или поиск пути кластеризации. Существует интересное описание в документации HavokAI Здесь описания их кластерную концепцию, которая отличается от HPA * реализации описанного здесь .

Удачи, и дайте нам знать, что вы найдете.

Стивен
источник
Если есть разные агенты с разными правилами, но их не слишком много, это все равно можно довольно эффективно обобщить, используя вектор идентификаторов, по одному на класс агента.
MSalters
4
+1 За признание того, что проблема, скорее всего, в зарешеченных областях (а не просто в непроходимых тайлах), и что эту проблему можно решить проще с помощью ранних расчетов времени загрузки.
Слипп Д. Томпсон
Заполните заливку или BFS каждой области.
волчий рассвет
Идентификаторы острова не должны быть статичными. Существует простой алгоритм, который подойдет в случае необходимости объединения двух отдельных островов, но впоследствии он не сможет разделить остров. На страницах с 8 по 20 на этих слайдах описан
kasperd
@kasperd, конечно, ничто не мешает пересчитать идентификаторы островов, объединить их во время выполнения. Дело в том, что идентификаторы островов позволяют быстро проверить, существует ли путь между двумя узлами, не выполняя поиск в астар.
Стивен
26

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

Способы смягчения этого:

  • Если вы априори знаете, что узел недоступен (например, у него нет соседей или он помечен UnPassable), вернитесь No Pathбез вызова AStar.

  • Ограничение количества узлов AStar будет расширяться до завершения. Проверьте открытый набор. Если это когда-нибудь станет слишком большим, прекратите и вернитесь No Path. Однако это ограничит полноту Астара; поэтому он может планировать только пути максимальной длины.

  • Ограничьте время, которое Астар занимает, чтобы найти путь. Если время истекло, выйдите и вернитесь No Path. Это ограничивает полноту, как предыдущая стратегия, но масштабируется со скоростью компьютера. Обратите внимание, что для многих игр это нежелательно, поскольку игроки с более быстрыми или медленными компьютерами будут по-разному воспринимать игру.

mklingen
источник
13
Я хотел бы отметить, что изменение механики вашей игры в зависимости от скорости процессора (да, поиск маршрута - игровая механика) может оказаться плохой идеей, потому что это может сделать игру довольно непредсказуемой, а в некоторых случаях даже неиграбельной на компьютерах через 10 лет. Поэтому я бы рекомендовал ограничить A * ограничением открытого набора, а не временем процессора.
Филипп
@Philipp. Изменен ответ, чтобы отразить это.
mklingen
1
Обратите внимание, что вы можете определить (достаточно эффективно, O (узлов)) для данного графа максимальное расстояние между двумя узлами. Это самая длинная проблема пути , и она дает вам правильную верхнюю границу для количества проверяемых узлов.
MSalters
2
@MSalters Как ты это делаешь в O (n)? И что такое «достаточно эффективно»? Если это только для пар узлов, разве вы не просто дублируете работу?
Стивен
Согласно Wikipedia, самая длинная проблема пути - NP-сложная, к сожалению.
Дести
21
  1. Выполните двойной поиск A * с целевого узла в обратном направлении и в одно и то же время в одном и том же цикле и прервите оба поиска, как только один из них будет найден неразрешимым

Если у цели есть только 6 плиток, доступных вокруг нее, а у источника есть 1002 плитки, поиск останавливается на 6 (двойных) итерациях.

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

Стефан Хоккенхалл
источник
2
Внедрение двунаправленного поиска типа «звезда» - это нечто большее, чем подразумевается в вашем утверждении, включая проверку того, что эвристика остается допустимой в этих обстоятельствах. (Ссылки: homepages.dcc.ufmg.br/~chaimo/public/ENIA11.pdf )
Питер Гиркенс,
4
@StephaneHockenhull: внедрив Двунаправленный A- * на карту местности с асимметричными затратами, я заверяю вас, что игнорирование академического бла-бла приведет к неправильному выбору пути и неверным расчетам стоимости.
Питер Гиркенс
1
@MooingDuck: общее количество узлов не изменяется, и каждый узел будет посещаться только один раз, поэтому наихудший случай разбиения карты ровно пополам идентичен однонаправленному A- *.
Питер Гиркенс
1
@PieterGeerkens: В классическом A * только половина узлов достижима и, следовательно, посещена. Если карта разделена ровно пополам, то при поиске в двух направлениях вы касаетесь (почти) каждого узла. Определенно крайний случай, хотя
Mooing Duck
1
@MooingDuck: я неправильно говорил; наихудшие случаи - это разные графики, но они ведут себя одинаково - наихудший случай для однонаправленного - это полностью изолированный целевой узел, требующий посещения всех узлов.
Питер Гиркенс
12

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

ClassicThunder
источник
6
Это хорошо. Группируя плитки по «регионам» и сначала проверяя, может ли область, в которой находится ваша плитка, быть подключена к области, в которой находится другая плитка, вы можете отбрасывать негативы гораздо быстрее.
Конерак
2
Правильно - обычно подпадает под HPA *
Стивен
@ Steven Спасибо, я был уверен, что не первый, кто задумался о таком подходе, но не знал, как он называется. Облегчает использование преимуществ существующих исследований.
ClassicThunder,
3

Используйте несколько алгоритмов с разными характеристиками

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

«Недостаток», который вы обнаруживаете в A *, заключается в том, что он не знает о топологии. У вас может быть двумерный мир, но он этого не знает. Насколько он знает, в дальнем углу вашего мира находится лестница, которая доставляет его прямо под мир к месту назначения.

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

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

Этот график имеет недостаток: он не находит оптимальный путь. Он просто находит в путь. Однако теперь он показал вам, что A * может найти оптимальный путь.

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

Корт Аммон - Восстановить Монику
источник
У меня есть основания полагать, что алгоритмы, подобные тем, что используются для Карт Google, работают аналогичным образом (хотя и более продвинутым).
Корт Аммон - Восстановить Монику
Неправильно. A * очень хорошо знает топологию, выбирая допустимую эвристику.
MSalters
Что касается Google, на моей предыдущей работе мы проанализировали производительность Карт Google и обнаружили, что это не могло быть *. Мы считаем, что они используют ArcFlags или другие подобные алгоритмы, которые основаны на предварительной обработке карт.
MSalters
@MSalters: это интересная тонкая линия для рисования. Я утверждаю, что A * не знает о топологии, потому что это касается только ближайших соседей. Я бы сказал, что более справедливо сказать, что алгоритм, генерирующий допустимую эвристику, знает топологию, а не сам A *. Рассмотрим случай, когда есть алмаз. A * немного пойдет по одному пути, прежде чем отступить, чтобы попробовать другую сторону алмаза. Невозможно уведомить A * о том, что единственный «выход» из этой ветви - через уже посещенный узел (сохранение вычислений) с эвристикой.
Cort Ammon - Восстановить Монику
1
Не могу говорить за Google Maps, но Bing Map использует параллельную двунаправленную звезду с ориентирами и неравенством треугольников (ALT) с предварительно вычисленными расстояниями от (и до) небольшого числа ориентиров и каждого узла.
Питер Гиркенс
2

Еще несколько идей в дополнение к ответам выше:

  1. Кэшируйте результаты поиска A *. Сохраните данные пути из ячейки A в ячейку B и, если возможно, используйте повторно. Это более применимо к статическим картам, и вам придется больше работать с динамическими картами.

  2. Кэшируйте соседей каждой ячейки. Реализация * должна расширять каждый узел и добавлять его соседей в открытый набор для поиска. Если эти соседи вычисляются каждый раз, а не кешируются, это может значительно замедлить поиск. И если вы уже сделали это, используйте приоритетную очередь для A *.

user55564
источник
1

Если ваша карта статична, вы можете просто иметь каждый отдельный раздел с собственным кодом и проверить это перед запуском A *. Это можно сделать при создании карты или даже закодировать на карте.

У непроходимых плиток должен быть флажок, и при переходе к такой плитке вы можете отказаться от запуска A * или выбрать рядом с ней плитку, которая является достижимой.

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

Madmenyo
источник
Это именно то, что я предлагал с идентификатором области в моем ответе.
Стивен
Вы также можете уменьшить количество используемого ЦП / времени, если ваша карта динамическая, но не часто меняется. Т.е. вы можете пересчитать идентификаторы области всякий раз, когда запертая дверь разблокирована или заблокирована. Так как это обычно происходит в ответ на действия игрока, вы, по крайней мере, исключаете заблокированные области темницы.
Uliwitness
1

Как я могу сделать так, чтобы A * быстрее пришел к выводу, что узел непроходим?

Профилируйте свою Node.IsPassable()функцию, выясняйте самые медленные части, ускоряйте их.

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

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

когда я щелкаю непроходимую плитку, алгоритм, по-видимому, проходит по всей карте, чтобы найти маршрут к непроходимой плитке

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

Если вы имеете в виду, что само место назначения проходимо, но окружено непроходимыми плитками, так что пути нет, то для A * нормально проверить всю карту. Как еще он узнает, что пути нет?

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

Superbest
источник
0

Делайте поиск пути назад.

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

AAAAAAAAAAAA
источник
Это еще медленнее, если число недоступных плиток превышает число доступных
Mooing Duck
1
@MooingDuck подключены недостижимые плитки вы имеете в виду. Это решение, которое работает практически с любым разумным дизайном карты, и его очень легко реализовать. Я не собираюсь предлагать что-то более изощренное без лучшего знания точной проблемы, например, как реализация A * может быть настолько медленной, что посещение всех плиток на самом деле является проблемой.
аааааааааааа
0

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

лор
источник
Дело было в том, чтобы быть быстрее, чем обычный A *.
Геккель
0

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

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

Это должен быть ранний выход из алгоритма:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');
Кромстер говорит, что поддерживает Монику
источник
0

Чтобы проверить самое длинное расстояние на графике между двумя узлами:

(при условии, что все ребра имеют одинаковый вес)

  1. Запустите BFS из любой вершины v.
  2. Используйте результаты, чтобы выбрать самую дальнюю вершину v, мы назовем ее d.
  3. Запустите BFS из u.
  4. Найдите самую дальнюю вершину u, мы ее назовем w.
  5. Расстояние между uи wявляется самым длинным расстоянием на графике.

Доказательство:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)
  • Допустим, расстояние между yи xбольше!
  • Тогда согласно этому D2 + R < D3
  • затем D2 < R + D3
  • Тогда расстояние между vи xбольше, чем vи u?
  • Тогда uбы не было выбрано на первом этапе.

Кредит проф. Шломи Рубинштейн

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

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


A * не очень полезен для простой игры на основе 2d плиток, потому что, если я правильно понимаю, если предположить, что существа движутся в 4 направлениях, BFS достигнет тех же результатов. Даже если существа могут двигаться в 8 направлениях, ленивая BFS, которая предпочитает узлы ближе к цели, все равно достигнет тех же результатов. A * - это модификация Dijkstra, которая намного дороже в вычислительном отношении, чем использование BFS.

BFS = O (| V |) предположительно O (| V | + | E |), но не совсем в случае отображения сверху вниз. A * = O (| V | log | V |)

Если у нас есть карта с 32 x 32 тайлами, BFS будет стоить не более 1024, а истинный A * может стоить вам колоссальных 10000. Это разница между 0,5 и 5 секундами, возможно, больше, если принять во внимание кэш. Поэтому убедитесь, что ваш A * ведет себя как ленивый BFS, который предпочитает плитки, которые находятся ближе к желаемой цели.

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

Так что да, BFS> A * во многих случаях, когда речь идет о плитках.

wolfdawn
источник
Я не уверен, что понимаю эту часть: «Если у нас есть карта только с 32 x 32 тайлами, BFS будет стоить не более 1024, а настоящая A * может стоить вам огромных 10000». Можете ли вы объяснить, как вы пришли к 10k? номер пожалуйста?
Кромстер говорит, что поддерживает Монику
Что именно вы подразумеваете под «ленивой BFS, которая предпочитает узлы ближе к цели»? Вы имеете в виду Dijkstra, обычный BFS или один с эвристикой (хорошо, что вы воссоздали A * здесь, или как вы выбираете следующий лучший узел из открытого набора)? Это log|V|в А * сложности 's действительно происходит от поддержания этого открытого набора, или размера полосы, и для сетки карты это крайне мало - о журнале (SQRT (| V |)) с помощью нотации. Журнал | V | отображается только в гипер-связанных графах. Это пример, где наивное применение сложности наихудшего случая дает неверное заключение.
congusbongus
@congusbongus Это именно то, что я имею в виду. Не используйте
ванильную
@KromStern Предполагая, что вы используете ванильную реализацию A * для игры на основе тайлов, вы получаете сложность V * logV, V - количество плиток, для сетки 32 на 32 - 1024. logV, что примерно равно числу бит нужно представить 1024, то есть 10. Таким образом, вы в конечном итоге бежите без необходимости. Конечно, если вы специализируете реализацию на использовании того факта, что вы работаете на сетке тайлов, вы преодолеете это ограничение, которое я и имел в виду
wolfdawn