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

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

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

31 голос | спросил user2499946 1 Jpm1000000pmThu, 01 Jan 2015 17:30:00 +030015 2015, 17:30:00

12 ответов


44

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

Идентификатор острова

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

Верхняя граница лимита

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

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

Сделать его асинхронным и amp; Предельные итерации

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

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

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

Кэш Что вы можете

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

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

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

ответил Steven 1 Jpm1000000pmThu, 01 Jan 2015 20:10:35 +030015 2015, 20:10:35
26

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

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

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

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

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

ответил mklingen 1 Jpm1000000pmThu, 01 Jan 2015 18:44:03 +030015 2015, 18:44:03
21
  1. Запустите двойной поиск A * с целевого узла в обратном направлении, а также в то же время в том же цикле , и прервите оба поиска, как только один окажется неразрешим

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

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

ответил Stephane Hockenhull 1 Jpm1000000pmThu, 01 Jan 2015 19:46:07 +030015 2015, 19:46:07
12

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

ответил ClassicThunder 2 Jam1000000amFri, 02 Jan 2015 09:22:08 +030015 2015, 09:22:08
3

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

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

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

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

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

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

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

ответил Cort Ammon 3 Jam1000000amSat, 03 Jan 2015 02:34:11 +030015 2015, 02:34:11
2

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

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

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

ответил user55564 2 Jam1000000amFri, 02 Jan 2015 04:46:39 +030015 2015, 04:46:39
1

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

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

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

ответил Madmenyo 2 Jam1000000amFri, 02 Jan 2015 01:40:54 +030015 2015, 01:40:54
1
  

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

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

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

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

  

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

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

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

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

ответил Superbest 2 Jam1000000amFri, 02 Jan 2015 08:51:51 +030015 2015, 08:51:51
0

Отслеживание пути назад.

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

ответил aaaaaaaaaaaa 2 Jpm1000000pmFri, 02 Jan 2015 14:52:06 +030015 2015, 14:52:06
0

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

ответил ent 3 Jpm1000000pmSat, 03 Jan 2015 23:49:37 +030015 2015, 23:49:37
0
  

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

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

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

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');
ответил Kromster 4 Jam1000000amSun, 04 Jan 2015 00:54:42 +030015 2015, 00:54:42
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 * может стоить вам колоссальных 10 000. В этом разница между 0,5 и 5 секундами, возможно, больше, если учитывать учетную запись. Поэтому убедитесь, что ваш A * ведет себя как ленивый BFS, который предпочитает плитки, которые ближе к желаемой цели.

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

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

ответил wolfdawn 3 Jpm1000000pmSat, 03 Jan 2015 17:46:15 +030015 2015, 17:46:15

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132