Situational awareness in path finding

Question

Assume you had to find the shortest path through a dungeon, where certain passages are only opened to you after certain items were collected, like locked doors and keys, for instance.

The normal gut reaction to the words "shortest path" would obviously be A*. But A* would fail in such an environment, since I see many problems defining a reliable heuristic and, additionally, it is very likely, that a node has to be visited multiple times, which is also not possible in conventional A* and would also make the heuristic harder.

What I thought about is simply looking for a path from the start of the dungeon to the end, ignoring any blocked doors. After this path is found, for each of the doors blocking our way, an additional path looking for the appropriate key and back to the door would be sought and traversed before the door is even reached. The very same system would be used to handle a situation, where the path to a key needed to open a door is again blocked by another door, which needs to be opened first.

A big problem I see with my solution is that after all the paths including the ones for item acquisition are found, the total distance travelled by the agent might not be the smallest possible, since there might be other blocked doors that are farther from the goal but have their appropriate key much more easily available. A* would have neglected these doors on the first pass where blocked doors are simply ignored.

I'm sure I'm not the first one to try to solve this and I would appreciate some input on the problem.

Answer 1

The way to handle such a situation optimally using straightforward A* is to expand the search space. That is, imagine that there exists a separate copy of the dungeon for each combination of items your character might be carrying.

In each copy of the dungeon, the doors which are passable are exactly those that can be passed using the corresponding set of items. The only way to pass from one dungeon copy to another is to stand on the location of an item and pick it up.

You can extend this trick to include other state changes, such as switches that can open and/or close doors. You could even allow the player to drop items, although this can get complicated since the state must then include the location of each dropped item, increasing the potential search space enormously.

A very useful optimization is to precalculate the shortest paths from each door (actually, each side of each door) and item to every other reachable door/item, assuming that all doors are locked. Once you have those paths, you can just treat each of them as a weighted edge in a graph connecting these significant locations to each other, and ignore all other locations.

For example, assume that your dungeon has ten doors and five keys. Then there will be 2 * 10 + 5 = 25 significant locations, and 2^5 = 32 possible item combinations, for a total of 25 * 32 = 800 nodes in the full search space. This is a very modest number, especially given that much of the search space is likely to be unreachable.

Answer 2

From a real-world viewpoint: If you were headed from A to B and found a door D in your way that was locked, you'd realise you have to find key D. So if your AI is as unknowing as the typical human is, that would involve scouting for the key, which is a set of tiny pathfinding steps in and of itself. On the other hand you might want your AI to know, before even attempting a path, that there is a locked door on that route, and in that case it will probably also know where to find the key.

Either way, the issue is one of connectivity at two levels. At the "on-the-ground" level, you know you can always move safely within one undivided zone... undivided by locked doors, that is. This is where you can use your current A* pathfinding implementation freely. (In a simplistic example, you could see a zone as a single room. You can't get to any other room without unlocking a door. In reality, it could be an entire region of your dungeon.) This is the foundation of your entity movement, but it's a bit like walking around with your eyes downcast, instead of surveying the area around you first -- you're likely to walk into a lamppost. Or in this case, a locked door. So your ground-level maps which your A* runs on must restrict the player to movement only within the current zone.

Next, there is a higher level map, which is more topological than topographical in nature. It doesn't really care about the on-the-ground details of obstacles and so on, it only cares about the connectivity between zones. This topological map bears connections between even zones that currently have a locked door between them, since it shows the ideal connectivity of all zones in your dungeon. In it's edges -- each representing a door between zones -- it stores what key is yet needed, if any, to open that door, else it is considered open. So in searching this graph for shortest path, it should limit that found path to only routes that are already open, by checking the data in the edges as the search runs. Connectivity here does not imply openness, rather it implies potential openness.

When you want to move to a point that falls within a separate zone, you first search your higher level map to find a path. (A* or any other shortest path algorithm may be used at this level.) Once you find a path, that higher level map should also provide info on which door you need to use to get from your current zone to the other zone. Now, in the local zone, you can do ground-level AI to navigate to that door. Once the door has been reached, your character can pass through that door/portal. He is now in zone B. If this is the target zone, he can use ground level navigation to go to the key. If it isn't, then you need to repeat step one until you reach the target zone.

There is the possibility that a key being sought is itself behind a locked door... and that the key to that door is likewise... and so on ad nauseum. This is essentially a dependency resolution problem, and there are a few ways to tackle this, one of which is Petri Nets. See this excellent paper.

PS. If you are creating your dungeon procedurally, then as you do so, you can store information on dependency ordering, provided you already know the starting position of the player.

Answer 3

The normal gut reaction to the words "shortest path" would obviously be A*. But A* would fail in such an environment, since I see many problems defining a reliable heuristic and, additionally, it is very likely, that a node has to be visited multiple times, which is also not possible in conventional A* and would also make the heuristic harder.

Firstly, an admissible heuristic doesn't have to be perfect. It just has to be an underestimate and it has to be better than nothing. Given that you're working with actual distances, it seems likely that A* would at least be of some help, and even if the heuristic didn't improve the search much, it would probably still be better than a standard breadth-first search or similar.

Secondly, A* can visit a node as many times as you like. Remember that A* is not a path-finding algorithm but a search algorithm. It searches through states. In games we often equate a state with a position, because we don't care how you reached that state - just how short the path was to get there. However in a problem like this the state is a combination of the position plus any other relevant state such as keys held.

It is true, however, that these complications will move A* from the realms of 'very efficient' to 'will succeed, but probably not in the timescale I require'. What is the timescale you require? In fact, why do you need to do this - do you really need the shortest path, or would any reasonable path suffice?

What I thought about is simply looking for a path from the start of the dungeon to the end, ignoring any blocked doors. After this path is found, for each of the doors blocking our way, an additional path looking for the appropriate key and back to the door would be sought and traversed before the door is even reached.

It's easy to prove that such a system would be suboptimal. Where would you begin the additional path from? If from the start, then you've wasted your time plotting the original path to the door. If from the end, then placing a key near the start means the path traverses the map twice when once would suffice. If you try and calculate optimal merge points for the paths to and from the door and the original path, that will yield an optimal result but will be resource-intensive due to the number of permutations and difficulty forming a heuristic to simplify the search. If you add multiple keys into the problem then you have the Travelling Salesman problem which is not easy to efficiently solve.

What I would attempt, if it's possible to relax the 'shortest path' criterion, is this:

• Create a high-level graph which only contains important locations - key positions, door positions, positions within locked areas, and note the straight-line distances between them. If your map already divides up into rooms or other discrete locations, that's great.
• Use A* to find a path through this graph, from the start to the end. The normal Cartesian distance heuristic should be sufficient to keep it manageable.
• Now, with this simplified path between these way points, use A* again to plot a low level path from one way point to the next.
• Join these low level paths together to form your whole path.

Once I got that working, I'd consider some minor optimisations - eg. weighting the areas with keys in more leniently so that the low level pathing would be more likely to make small detours to collect keys.

Answer 4

with the information you provided I think you can use A* with just a little modification. in a normal A* algorithm, you mark every node as you pass over them to make sure you won't ever pass it again. That is the exact part that makes problem with the Items. The key change is to remember what was your items when you previously passed from a node. here is a sudo code explaining what I mean:

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

with this algorithm you first start checking all nodes with no item. there is a high possibility that your first searching group end up blocked by some doors. but it'll find a key to that door before it search all the rooms. from that key you start a new search having that specific key. this time when you reach the door you may pass it. the same routine continues until you find your way out of dungeon. the only problem may be memory consumption whenever there are lots of doors and keys. although it won't be a problem for at least 10 or 15 keys.

Answer 5

Why don't you just use normal A*, and model locked doors as impassable regions; once you pick up the key (walk on the key tile?), that changes that particular locked door into a passable region.

What this means is that your path-finder will go for the shortest keyless route, and if it finds keys along the way, it will incorporate that into its path if that helps.

That seems pretty reasonable to me. It's not perfect, but it's a simple solution to the problem.