Как найти путь через препятствие?

Как лучше всего представить следующую ситуацию - агент ( @) должен добраться до цели ( $). Путь заблокирован рвом ( ~~~). Доступны грабли (или другие устройства, например, ботинки для прогулки по воде), которые позволят пересечь препятствие.

.....~~~...   . ground
...=.~~~...   = rake
.....~~~.$.   ~ water
.@...~~~...   @ agent
.....~~~...   $ goal

Как правильно найти путь от @до, $если нет сразу доступного пути? Должен ли мой путь иметь не только стоимость, но и предпосылки?

UPD : Проблема в том, что цель недоступна, а рейк - это лишь один из множества возможных объектов на карте. Тогда возникает вопрос: «Как заставить агента понять, что ему нужны грабли?»

ai path-finding zzandy
источник

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

Джоккинг

Ответы:

Я думаю о стеке целей, поиск пути должен быть аннотирован :

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

zzandy
источник

+1 Я сделал нечто похожее с моей игрой и написал небольшой пост об этом некоторое время назад под заголовком «Задачи юнитов и поиск пути» .

MichaelHouse

@ byte66 не обрабатывает особый случай, когда есть путь без использования rake, но использование rake приводит к более короткому пути

Ali1S232

@ Гаджет, ты прав. Думаю, для этого понадобится другой подход.

zzandy

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

MichaelHouse

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

Ali1S232
источник

+1 Сделайте ваши грабли односторонним соединением с водой, также как и вода-земля, будучи односторонним соединением.

Лоран Кувиду

У меня нет четкого понимания, как связать геометрический поиск и поиск функций. Как перейти от no path from @ to $к goto rake, bring it to water, place it, goto $.

zzandy

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

Ali1S232

Но что, если вы можете нести устройство? Я думал, что он имел в виду (и, следовательно, мой ответ.)

kaoD

Да, я имею в виду, что устройство можно (и нужно) носить с собой. @kaoD, ваш ответ не включает шаг, когда агент понимает, что ему нужны грабли.

zzandy

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

Однако я могу представить себе реальное, хардкорное решение. Добавьте другое измерение в вашу сетку поиска пути. Таким образом, в случае 2D-карты вы делаете сетку для поиска пути 3D. В этом простом примере это новое измерение будет иметь только глубину два, но в реальной игре оно быстро увеличится.

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

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

Нахождение пути - это обычный A * в измерениях x и y, означающий, что каждая ячейка сетки имеет доступ к своим соседям. В измерении z, однако, A * не допускается распространение.

Кроме того, где грабли. Грабли объект действует как отверстие между z = 0 и z = 1 в сетке поиска пути.

Это означает, что A * будет заполнять заливку в z = 0, попадать в воду и заканчиваться без вариантов - тогда он будет распространяться до z = 1 через грабли, и в z = 1 (где вода проходима) найти свой путь к цели. В результате NPC без колебаний перемещается к рейку, а затем перемещается по кратчайшему пути к цели.

Джоар Якобссон
источник

В моем примере я воспринимал грабли больше как «ботинки для ходьбы по воде», имея в виду объект, который, если он у вас есть, позволяет вам путешествовать по водным плиткам. Если грабли должны быть фактически «построены» как кусок местности и покрывают ограниченное количество плиток, которых может быть или не быть достаточно, чтобы достичь через воду, проблема является более сложной. Мое решение допускает одноразовые предметы, хотя, если вы сделаете движение в z = 1, автоматически снова опуститесь до z = 0.

Джоар Якобссон