Ситуационная осведомленность в поиске пути

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

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

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

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

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

Способ справиться с такой ситуацией оптимально, используя простой A *, состоит в расширении пространства поиска. То есть, представьте, что существует отдельная копия подземелья для каждой комбинации предметов, которые ваш персонаж может нести.

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

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

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

Например, предположим, что ваш темница имеет десять дверей и пять ключей. Тогда будет 2 * 10 + 5 = 25 значимых местоположений и 2 ^ 5 = 32 возможных комбинации элементов, в общей сложности 25 * 32 = 800 узлов в полном пространстве поиска. Это очень скромное число, особенно учитывая, что большая часть пространства поиска, вероятно, будет недоступна.

С точки зрения реального мира: если вы направлялись из А в В и обнаружили на своем пути дверь D, которая была заперта, вы бы поняли, что должны найти ключ D. Поэтому, если ваш ИИ так же неосведомлен, как и типичный человек. , это будет включать поиск ключа, который представляет собой набор крошечных шагов поиска пути сам по себе. С другой стороны, вы, возможно, хотите, чтобы ваш AI знать, даже прежде, чем попытаться путем, что есть запертая дверь на этом маршрут, и в этом случае он, вероятно, также знает, где найти ключ.

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

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

Если вы хотите перейти к точке, которая попадает в отдельную зону, вы сначала ищете карту более высокого уровня, чтобы найти путь. (На этом уровне можно использовать * или любой другой алгоритм кратчайшего пути.) Как только вы найдете путь, карта более высокого уровня также должна предоставить информацию о том, какую дверь вам нужно использовать, чтобы попасть из вашей текущей зоны в другую зону. Теперь в локальной зоне вы можете использовать AI на уровне земли, чтобы перейти к этой двери. Как только дверь достигнута, ваш персонаж может пройти через эту дверь / портал. Теперь он находится в зоне B. Если это целевая зона, он может использовать навигацию на уровне земли, чтобы перейти к клавише. Если это не так, то вам нужно повторять первый шаг, пока не достигнете целевой зоны.

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

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

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

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

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

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

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

Легко доказать, что такая система будет неоптимальным. Где бы вы начать дополнительный путь от? Если с самого начала, то вы зря потратили свое время замышляет оригинальный путь к двери. Если с конца, то размещение ключа возле начала означает, что путь проходит карту дважды, когда этого будет достаточно. Если вы попытаетесь рассчитать оптимальные точки слияния для путей к двери и из нее и к исходному пути, это даст оптимальный результат, но будет ресурсоемким из-за количества перестановок и сложности формирования эвристики для упрощения поиска. Если вы добавите несколько ключей в задачу, то возникнет проблема Traveling Salesman, которую нелегко решить.

Что бы я попытался, если можно ослабить критерий «кратчайшего пути», это:

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

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

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

if (nodestoCheck.notempty())
    newNode = nodeToCheck.first;
    if (notpassed(newNode.pos, newNode.items))
        if (room(newNode).containItem)
            add NewNode + room(NewNode).items 
        else
            do normal A* algorithm for new Node

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

Почему бы вам просто не использовать обычную A * и моделировать запертые двери как непроходимые регионы; как только вы поднимаете ключ (ходите по плитке ключа?), это превращает эту запертую дверь в проходимую область.

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

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