Поиск пути с замком и ключом?

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

Эта головоломка похожа на темницу в стиле Зельды, как на картинке:

Чтобы добраться до цели, вы должны победить Босса, для чего нужно пройти через яму, для чего нужно собрать Перо, для чего нужно собрать Ключ.

Зельдские подземелья имеют тенденцию быть линейными. Однако мне нужно решить проблему в общем случае. Так:

• Для цели может потребоваться один из набора ключей. Так что, возможно, вам нужно получить либо красный ключ, либо синий ключ. Или может быть длинная незапертая дверь!
• Там может быть несколько дверей и ключей в своем роде. Например, на карте может быть несколько красных ключей, и один из них даст доступ ко всем красным дверям.
• Цель может быть недоступна, потому что правильные ключи находятся за запертыми дверями

Как мне выполнить поиск пути на такой карте? Как будет выглядеть график поиска?

Примечание: последний пункт об обнаружении недоступных целей важен; A *, например, крайне неэффективен, если цель недоступна. Я хотел бы иметь дело с этим эффективно.

Предположим, что ИИ знает, где все на карте.

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

Этот ответ получил много положительных откликов с тех пор, как он появился первым и содержит демоверсию, но для гораздо более оптимизированного и специализированного решения вы также должны прочитать ответ «Делать это намного быстрее» /gamedev/ / а / 150155/2624

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

Для начала, думая о поиске пути, помните, что иерархия простых алгоритмов поиска пути:

• Поиск в ширину примерно так же прост, как вы можете получить.
• Алгоритм Джикстры похож на поиск в ширину, но с разными «расстояниями» между состояниями
• A * - это Джикстра, где у вас есть «общее чувство правильного направления», доступное как эвристика.

В нашем случае простое кодирование «состояния» в качестве «местоположения + инвентарь» и «расстояний» в качестве «перемещения или использования предмета» позволяет нам использовать Djikstra или A * для решения нашей проблемы.

Вот некоторый реальный код, демонстрирующий ваш пример уровня. Первый фрагмент только для сравнения - перейдите ко второй части, если хотите увидеть окончательное решение. Мы начнем с реализации Джикстры, которая находит правильный путь, но мы проигнорировали все препятствия и ключи. (Попробуйте, Вы можете видеть это только beelines для конца, от комнаты 0 -> 2 -> 3-> 4-> 6-> 5)

function Transition(cost, state) { this.cost = cost, this.state = state; }
// given a current room, return a room of next rooms we can go to. it costs 
// 1 action to move to another room.
function next(n) {
    var moves = []
    // simulate moving to a room
    var move = room => new Transition(1, room)
    if (n == 0) moves.push(move(2))
    else if ( n == 1) moves.push(move(2))
    else if ( n == 2) moves.push(move(0), move(1), move(3))
    else if ( n == 3) moves.push(move(2), move(4), move(6))
    else if ( n == 4) moves.push(move(3))
    else if ( n == 5) moves.push(move(6))
    else if ( n == 6) moves.push(move(5), move(3))
    return moves
}

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

    if (!nextStates.length) return ['did not find goal', history]

    var action = nextStates.pop()
    cost += action.cost
    var cur = action.state

    if (cur == goal) return ['found!', history.concat([cur])]
    if (history.length > 15) return ['we got lost', history]

    var notVisited = (visit) => {
        return visited.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
    };
    nextStates = nextStates.concat(next(cur).filter(notVisited))
    nextStates.sort()

    visited.push(cur)
    return calc_Djikstra(cost, goal, history.concat([cur]), nextStates, visited)
}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, 0)], []))

Итак, как нам добавить элементы и ключи в этот код? Просто! вместо каждого «состояния» начинается только номер комнаты, теперь это кортеж комнаты и состояние нашего инвентаря:

 // Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }

Переходы теперь превращаются из кортежа (стоимость, комната) в кортеж (стоимость, состояние), поэтому они могут кодировать как «перемещение в другую комнату», так и «подбор предмета»

// move(3) keeps inventory but sets the room to 3
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b))
// pickup("k") keeps room number but increments the key count
var pickup = (cost, item) => {
    var n = Object.assign({}, cur)
    n[item]++;
    return new Transition(cost, new State(cur.room, n.k, n.f, n.b));
};

наконец, мы вносим некоторые незначительные изменения, связанные с типом, в функцию Djikstra (например, она все еще просто совпадает с номером комнаты цели вместо полного состояния), и мы получаем наш полный ответ! Обратите внимание, что напечатанный результат сначала идет в комнату 4, чтобы забрать ключ, затем идет в комнату 1, чтобы забрать перо, затем идет в комнату 6, убивает босса, затем идет в комнату 5)

// Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }
function Transition(cost, state, msg) { this.cost = cost, this.state = state; this.msg = msg; }

function next(cur) {
var moves = []
// simulate moving to a room
var n = cur.room
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b), "move to " + room)
var pickup = (cost, item) => {
	var n = Object.assign({}, cur)
	n[item]++;
	return new Transition(cost, new State(cur.room, n.k, n.f, n.b), {
		"k": "pick up key",
		"f": "pick up feather",
		"b": "SLAY BOSS!!!!"}[item]);
};

if (n == 0) moves.push(move(2))
else if ( n == 1) { }
else if ( n == 2) moves.push(move(0), move(3))
else if ( n == 3) moves.push(move(2), move(4))
else if ( n == 4) moves.push(move(3))
else if ( n == 5) { }
else if ( n == 6) { }

// if we have a key, then we can move between rooms 1 and 2
if (cur.k && n == 1) moves.push(move(2));
if (cur.k && n == 2) moves.push(move(1));

// if we have a feather, then we can move between rooms 3 and 6
if (cur.f && n == 3) moves.push(move(6));
if (cur.f && n == 6) moves.push(move(3));

// if killed the boss, then we can move between rooms 5 and 6
if (cur.b && n == 5) moves.push(move(6));
if (cur.b && n == 6) moves.push(move(5));

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))	
return moves
}

var notVisited = (visitedList) => (visit) => {
return visitedList.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
};

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

if (!nextStates.length) return ['No path exists', history]

var action = nextStates.pop()
cost += action.cost
var cur = action.state

if (cur.room == goal) return history.concat([action.msg])
if (history.length > 15) return ['we got lost', history]

nextStates = nextStates.concat(next(cur).filter(notVisited(visited)))
nextStates.sort()

visited.push(cur)
return calc_Djikstra(cost, goal, history.concat([action.msg]), nextStates, visited)
o}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, new State(0, 0, 0, 0), 'start')], []))

Теоретически, это работает даже с BFS, и нам не требовалась функция стоимости для Djikstra, но наличие стоимости позволяет нам сказать, что «подобрать ключ легко, но бороться с боссом очень сложно, и мы бы предпочли отказаться» 100 шагов, а не сражаться с боссом, если бы у нас был выбор »:

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))

Назад A * сделает свое дело

Как обсуждалось в этом ответе на вопрос о прямом и обратном поиске путей , поиск путей в обратном направлении является относительно простым решением этой проблемы. Это работает очень похоже на GOAP (Goal-Oriented Action Planning), планируя эффективные решения и сводя к минимуму бесцельное удивление.

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

В деталях

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

Если ветвь незапертой двери находит ключ, то она продолжает поиск агента ИИ.

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

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

В бою

В вашем конкретном примере, поиск пути от цели к началу:

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

2. Ветвь А находит босса и теперь ищет Старт, но сталкивается с ямой.

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

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

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

6. Ветви A и D продолжают конкурировать, но когда ветка A достигает ключа, она ищет перо, и оно не достигнет пера, потому что оно должно снова пройти через запертую дверь. С другой стороны, ветвь D, достигнув ключа, переключает свое внимание на начало и находит его без затруднений.

7. Ветвь D побеждает. Он нашел обратный путь. Последний путь: Пуск -> Ключ -> Перо -> Босс -> Цель.

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

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

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

Решение Подход

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

Тем не менее, несколько правил вступят в силу при изучении, которые могут изменить приоритет ...

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

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

Расширение идеи с помощью «блокируемых» клавиш

У вас могут быть ключи, которые нельзя получить без другого ключа. Или заблокированные ключи как бы. Если вы знаете свои старые Колоссальные пещеры, вам нужна клетка для птиц, чтобы поймать птицу, что вам понадобится позже для змеи. Таким образом, вы «разблокируете» птицу с помощью клетки (которая не блокирует путь, но не может быть поднята без клетки), а затем «разблокируете» змею (которая блокирует ваш путь) с птицей.

Итак, добавив несколько правил ...

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

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