Improve Inventory-Aware Pathfinding with Map Preprocessing

In the last article we introduced a basic approach for Inventory-Aware Pathfinding (IAP), a pathfinding algorithm capable of interacting with obstacles and not just avoiding them. If you have not read it, I encourage you to go back and read it to understand the basic challenges and the main ideas behind the proposed solution.

For instance, we can have a pathfinding algorithm that can solve small plans and “puzzles” involving reasoning like “before passing this door, I need to get that key”. This is definitely planning territory. However, if we focus on a small subset of the problem, we may squeeze the algorithm into the pathfinding search itself.

In order for the red NPC character to reach the King, he needs the KEY to open the door. But to get the KEY, he needs to give the MEAT to the DRAGON. But to do this he needs to kill the SKELETON with the MAGIC AXE. Or he can talk to the MONKEY and get a SPECIAL ARMOR that allows him to pass the LAVA RIVER.

We have already seen that, if we focus on this type of item-related problems, then we can tweak the problem in such a way it can be naively solved by a traditional pathfinding algorithm with just a minimal set of changes.

Unfortunately, the resulting problem grows exponentially with the number of collected items. If a pathfinding algorithm is not good at pruning the search space, it can barely solve problems with more than 2-3 items on the map.

To solve this problem, we can use smarter algorithms (like Jump-Point Search) and push the limit to 7-8 keys/items on the map (that are more than enough for many games). However, using this simple approach we cannot avoid the main drawback of IAP. If a path cannot be solved, the algorithm will lose time by searching  into a huge amount of “copies of the original map”.

In this article, we will show an additional precomputation step capable of pruning away “probably unnecessary” keys from the map before the real pathfinding search even start. As complexity is exponential in the number of items encountered by the pathfinding search, removing even 1 item from the map can give us a great improvement!

This procedure is divided in two steps:

Let’s see this in more detail using this map as example:

Step 1: The offline preprocessing

The goal of the offline preprocessing step is to analyze the game map and extract information on the different regions that are connected through obstacles. The basic concept is this: a region represents an area of the map that can be fully explored by a character starting in it with no items.

Computing this is crucial. This structure allows us to reason on the high-level relation among items, obstacles and reachable locations on the map. In particular, using this information we can:

For this task, we take as input the map annotated with the location of every obstacle and we  generate two different outputs.

The first one on the left is the connected area map. It is a copy of the original map in which each location (tile, mesh or whatever) is annotated with an integer. If two locations are labeled with the same integer, then they belong to the same connected area (and vice versa).

The second on the right is the obstacle connectivity graph, a graph in which each node is a connected area and each edge represents the obstacle connecting two areas. This graph is the core of the preprocessing method and it is used to answer questions like “which obstacle I will encounter if I move from start to destination?”

If we traverse the graph from the starting point region to the area where the destination point is, the edge we traverse represents the obstacles we necessarily need to unlock to reach the destination.

Once we have got these two pieces of information, we can serialize them and store them on disk.

Step 2: The online pre-search

The second step is where we do the actual magic. This step takes as input the precomputed data from Step 1 (connected area map and obstacle connectivity graph) and the pathfinding query (current location and desired goal), and produces a subset of the total items on the map that “should be sufficient to reach the goal within a range of confidence”. In fact, the bad news is this algorithm, in general, cannot guarantee that the output set of items is enough to reach the destination. However, the good news is that we can control this behavior by allocating more resources to the algorithm. In the extreme case, we can also obtain a complete subset of items (that means, we can be sure that this set can allow us to find a solution, if it exists).

We will explore the preprocessing step with the above example. Disregarding the effort to do pathfinding inside a single region (which we know is is always possible), the goal is to go from the yellow region (where the NPC starts) to the purple region (where the King is) using the items on the map. At first glance, it is clear that some objects are unnecessary as there are 3 obstacles (namely the BAT, the DRAGON and the DOOR) and 5 items!

In Step 2 the pre-search algorithm works in this way. First, we look at the graph and we search all the possible paths going from YELLOW to PURPLE (without loops, obviously). This produces a set of sequences of the form “region -> obstacle -> region -> …”. In the example there is only one possible path: YELLOW -> DOOR -> PURPLE.

If we take any of these sequences, then we know that all the obstacles in it MUST be unlocked to reach the destination traversing all the areas in that sequence. If we take all the sequences in the set, then we know that to solve the problem we need AT LEAST ALL THE ITEMS IN AT LEAST ONE sequence. For now, let’s be on the safe side and consider that we need to unlock all the obstacles in all the sequences.

We can then use this information to generate a set of significant obstacles in the map; we call this set Necessary Obstacles Set (NOS). In the small example above there is only one sequence available and therefore the NOS trivially contains only the DOOR. In general, things are more complicated and there are different ways to choose this set. However, as we said before, we can try to be safe and put into NOS all the obstacles for every sequence.

Once we have our NOS set, we can produce the corresponding set containing the items that unlock all the obstacles in NOS. We call this set Necessary Items Set (NIS). In the example above, the DOOR is unlocked by the KEY, therefore the NIS set contains only the KEY.

Now we can start an instance of Inventory-Aware Pathfinding that uses only the items in the NIS set ignoring everything else. We managed to go from 5 items to only 1, i.e., the KEY! Not bad!

A slightly more complex example

However, in general, the items in NIS may be not sufficient for reaching the destination. Consider for example that the KEY is in the GREEN region (the one blocked by the DRAGON). If we are allowed only to take the KEY, we are stuck because we cannot remove the DRAGON.

To solve this problem we can use a recursive approach. We call the NIS set obtained so far with NIS(0). Then, we need to repeat the above algorithm using as destination the region of every item in NIS(0). In other words, we look for all the possible paths from the starting point to the i-th item in NIS(0)  and add all the items returned by the algorithm to NIS(0). We call this  new set NIS(1).

Let’s look at the example. As we have seen before, NIS(0) = { KEY }. Then we set the region containing the KEY as a destination and we repeat the algorithm. Looking at the connectivity graph, the only path from start to KEY is (YELLOW -> DRAGON -> GREEN). The NOS set will contain { DRAGON } and, therefore,  the corresponding NKS set will be { AXE }. We add this to NIS(0) and we get NIS(1) = { AXE, KEY }.

Now, we repeat the same thing again for every item in NIS(1). However, you can verify this time NIS(2) will be the same of NIS(1). As a consequence, we can stop iterating and return { AXE, KEY } as the final NIS set. We can easily see how AXE and KEY are the only two items we need to reach the king!  Finally, we can apply a IAP algorithm limited to AXE and KEY, and solve the problem.

Unfortunately, with this approach we lose general optimality. For instance, this algorithm will not include items that can be used to open a shortcut in the same region. As a consequence, the final path may not be optimal. I will leave the details of this for another time. However, in many practical cases, removing more than 50% of the items on the map is more important than solving the optimal problem.

Additional Resources:

This work has been done in collaboration with Stavros Vassos and Sebastian Sardina. You can get more info and ask question about IAP by visiting my website.