22
\$\begingroup\$

I'm working on a game with maps that resemble lock and key puzzles. The AI needs to navigate to a goal that may be behind a locked red door, but the red key may be behind a locked blue door, and so on...

This puzzle is similar to a Zelda-style dungeon, like this picture:

Zelda dungeon

To get to the Goal, you must defeat the Boss, which requires going over the pit, which requires collecting the Feather, which requires collecting the Key

Zelda dungeons tend to be linear. However, I need to solve the problem in the general case. So:

  • The goal could require one of a set of keys. So maybe you need to get either the red key or the blue key. Or there could be an unlocked door the long way around!
  • There could be multiple doors and keys of a kind. E.g. there could be multiple red keys in the map, and collecting one will grant access to all the red doors.
  • The goal may be inaccessible because the right keys are behind locked doors

How would I perform pathfinding on such a map? What would the search graph look like?

Note: the last point about detecting inaccessible goals is important; A*, for example, is extremely inefficient if the goal is inaccessible. I would like to deal with this efficiently.

Assume that the AI knows where everything is on the map.

\$\endgroup\$
  • 4
    \$\begingroup\$ Does the AI only know of and discover things once it unlocks them? E.g., does it know the feather is behind the locked door? Does the AI understand concepts like, "That's a lock so I need a key" or is something more simple like, "I have something blocking my way, so try all the things I've found on it. Feather on door? No. Key on door? Yes!" \$\endgroup\$ – Tim Holt Oct 31 '17 at 0:25
  • 1
    \$\begingroup\$ There was some previous discussion of this problem in this question about pathfinding forwards vs backwards, which might be of use to you. \$\endgroup\$ – DMGregory Oct 31 '17 at 1:18
  • 1
    \$\begingroup\$ So you’re not trying to simulate a player, but trying to create an optimized dungeon run? My answer was definitely about simulating a player behavior. \$\endgroup\$ – Tim Holt Oct 31 '17 at 2:14
  • 4
    \$\begingroup\$ Unfortunately detecting an inaccessible goal is quite hard. The only way to be sure there's no way to reach the goal is to explore the whole of the reachable space to ensure none of it contains a goal - which is exactly what A* does that makes it take so many extra steps if the goal is inaccessible. Any algorithm that searches less of the space risks missing an available path to the goal because the path was hiding in part of the space it skipped searching. You can accelerate this by working on a higher level, searching the graph of room connections instead of every tile or navmesh polygon. \$\endgroup\$ – DMGregory Oct 31 '17 at 3:20
  • 1
    \$\begingroup\$ Offtopic, I instinctively thought of Chip's Challenge instead of Zelda :) \$\endgroup\$ – Flater Oct 31 '17 at 13:17
22
\$\begingroup\$

Standard pathfinding is Good Enough -- your states are your current location + your current inventory. "moving" is either changing rooms or changing inventory. Not covered in this answer, but not too much additional effort, is writing a good heuristic for A* -- it can really speed up the search by preferring to pick up things over moving away from it, preferring to unlock a door near the target over searching for a long way around, etc.

This answer has gotten a lot of upvotes since it came first and has a demo, but for a much more optimized and specialized solution, you should also read the "Doing it backwards is much faster" answer https://gamedev.stackexchange.com/a/150155/2624


Fully operational Javascript proof of concept below. Sorry for the answer as a code dump -- I had actually implement this before I was convinced it was a good answer, but it seems pretty flexible to me.

To start off when thinking about pathfinding, remember that the heirarchy of simple pathfinding algorithms is :

  • Breadth First Search is about as simple as you can get.
  • Djikstra's Algorithm is like Breadth First Search but with varying "distances" between states
  • A* is Djikstras where you have a 'general sense of the right direction' available as a heuristic.

In our case, just encoding a "state" as a "location + inventory" and "distances" as a "movement or item usage" allows us to use Djikstra or A* to solve our problem.

Here is some actual code demonstrating your example level. The first snippet is just for comparison -- jump to the second part if you want to see the final solution. We start off with a Djikstra's implementation that finds the correct path, but we've ignored all the obstacles and keys. (Try it out, You can see it just beelines for the finish, from room 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)], []))

So, how do we add items and keys to this code? Simple! instead of every "state" begin just the room number, it's now a tuple of the room and our inventory state:

 // 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 }

Transitions now change from being a (cost, room) tuple to a (cost, state) tuple, so then can encode both "moving to another room" and "picking up an item"

// 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));
};

finally, we make some minor type-related changes to the Djikstra function (for example, it still is just matching on a goal room number instead of a full state), and we get our full answer! Note the printed result first goes to room 4 to pick up the key, then goes to room 1 to pick up the feather, then goes to room 6, kills the boss, then goes to room 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')], []))

In theory, this works even with BFS and we didn't need the cost function for Djikstra's, but having the cost allows us to say "picking up a key is effortless, but fighting a boss is really hard, and we'd rather backtrack 100 steps rather than fight the boss, if we had the choice":

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'))
\$\endgroup\$
  • \$\begingroup\$ Yes, including inventory/key state in the search graph is one solution. I'm concerned about the increased space requirements though - a map with 4 keys requires 16 times the space of a key-less graph. \$\endgroup\$ – congusbongus Oct 31 '17 at 4:12
  • 8
    \$\begingroup\$ @congusbongus welcome to the NP-complete traveling salesman problem. There is no general solution that will solve that in polynomial time. \$\endgroup\$ – ratchet freak Oct 31 '17 at 9:19
  • 1
    \$\begingroup\$ @congusbongus I don't think generally that your search graph is going to be that much overhead, but if you're concerned about space, just pack your data -- you could use 24-bits for the room indicator (16 million rooms should be enough for anyone) and a bit each for the items you're intererested in using as gates (up to 8 unique ones). If you want to get fancy, you can use dependencies to pack down items into even smaller bits, i.e. use the same bit for "key" and "boss" since there's an indirect transitive dpendency \$\endgroup\$ – Jimmy Oct 31 '17 at 12:49
  • \$\begingroup\$ @Jimmy Even though it's not personal, I appreciate the mention of my answer :) \$\endgroup\$ – Jibb Smart Nov 1 '17 at 1:28
13
\$\begingroup\$

Backwards A* will do the trick

As discussed in this answer to a question about forward vs backward pathfinding, pathfinding backwards is a relatively simple solution to this problem. This works very similarly to GOAP (Goal Oriented Action Planning), planning efficient solutions while minimising aimless wondering.

At the bottom of this answer I have a break-down of how it handles the example you gave.

In Detail

Pathfind from the destination to the start. If, in your pathfinding, you come across a locked door, you have a new branch to your pathfinding that continues through the door as if it is unlocked, with the main branch continuing to look around for another path. The branch that continues through the door as if it's unlocked is no longer looking for the AI agent -- it's now looking for a key it can use to pass through the door. With A*, its new heuristic is distance to key + distance to AI agent, instead of just distance to AI agent.

If the unlocked-door branch finds the key, then it continues looking for the AI agent.

This solution is made a little more complicated when there are multiple viable keys available, but you can branch accordingly. Because the branches have a fixed destination, it still lets you use a heuristic to optimise the path-finding (A*), and impossible paths will hopefully be cut off quickly -- if there's no way around the locked door, the branch that doesn't pass through the door runs out of options quickly and the branch that goes through the door and looks for the key continues on its own.

Of course, where there are a variety of viable options available (multiple keys, other items to circumvent the door, long path around the door), many branches will be maintained, affecting performance. But you'll also find the fastest option, and be able to use that.


In Action

In your specific example, pathfinding from the Goal to the Start:

  1. We quickly encounter a boss door. Branch A continues through the door, now looking for a boss to fight. Branch B stays stuck in the room, and will soon expire when it finds there's no way out.

  2. Branch A finds the boss and is now looking for the Start, but encounters a pit.

  3. Branch A continues over the pit, but now it's looking for the feather, and will make a bee-line towards the feather accordingly. Branch C is created which tries to find a way around the pit, but expires soon as it's unable to. That, or it gets ignored for a while, if your A* heuristic finds that Branch A is still looking most promising.

  4. Branch A encounters the locked door, and continues through the locked door as if it's unlocked, but now it's looking for the key. Branch D continues through the locked door as well, still looking for the feather, but then it will look for the key. This is because we don't know if we need to find the key or the feather first, and as far as the pathfinding is concerned, the Start could be on the other side of this door. Branch E tries to find a way around the locked door, and fails.

  5. Branch D quickly finds the feather and continues looking for the key. It's allowed to pass through the locked door again, since it's still looking for the key (and it's working its way backwards in time). But once it has the key, it won't be able to pass through the locked door (since it couldn't pass through the locked door before it found the key).

  6. Branch A and D continue to compete, but when Branch A reaches the key, it's looking for the feather, and it will fail to reach the feather because it has to pass through the locked door again. Branch D, on the other hand, upon reaching the key, turns its attention to the Start, and finds it without complication.

  7. Branch D wins. It has found the reverse path. The final path is: Start -> Key -> Feather -> Boss -> Goal.

\$\endgroup\$
6
\$\begingroup\$

Edit: This is written from the point of view of an AI that is out to explore and discover a goal, and does not know the location of keys, locks, or destinations ahead of time.

First, assume that the AI has some kind of overall goal. E.g,, "Find the boss" in your example. Yea you want to beat it, but really it's about finding it. Assume it has no idea how to get to the goal, just that it exists. And it will know it when it finds it. Once the goal is met, the AI can stop working to solve the problem.

Also, I'm going to use the generic term "lock" and "key" here, even if it might be a chasm and a feather. I.e., feather "unlocks" the chasm "lock".

Solution Approach

It seems like you'd start first with just an AI that was basically a maze explorer (if you think of your map as a maze). Exploring and mapping out all the places it can go would be the primarily focus of the AI. It could be based purely on something simple like, "Always go to the closest path I have seen but not yet visited."

However, a few rules would kick in while exploring that might change the priority...

  • It would take any key it found, unless it already had the same key
  • If it found a lock it had never seen before, it would try every key it had found on that lock
  • If a key worked on a new type of lock, it would remember the key type and the lock type
  • If it found a lock it had seen before and had the key, it would use the remembered key type (e.g, second red lock found, red key worked before on red lock, so just use red key)
  • It would remember the location of any lock it could not unlock
  • It would not need to remember the location of locks it had unlocked
  • Any time it found a key and knew of any previously unlockable locks, it would immediately visit each of those locked locks, and try to unlock them with the new found key
  • When ever it unlocked a path, it would simply revert back to the exploration and mapping goal, prioritizing stepping into the new area

A note on that last point. If it has to choose between going to check out an unexplored area it's seen before (but not visited) versus an unexplored area behind a newly unlocked path, it should make the newly unlocked path the priority. That's probably where there are new keys (or locks) that will be useful. This assumes a locked path probably won't be a pointless dead end.

Expanding the Idea with "Lockable" Keys

You could potentially have keys that can't be taken without another key. Or locked keys as it were. If you know your old Colossal Caves, you need to have the bird cage to catch the bird - which you need later for a snake. So you "unlock" the bird with the cage (which doesn't block path but can't be picked up without the cage), and then "unlock" the snake (which blocks your path) with the bird.

So adding some rules...

  • If a key can't be taken (it's locked), try every key you already have on it
  • If you find a key you can't unlock, remember it for later
  • If you find a new key, go try it on every known locked key as well as locked path

I won't even get into the whole thing about how carrying a certain key might negate the effect of another key (Colossal Caves, rod scares bird and must be dropped before bird can be picked up, but is needed later to create magical bridge).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.