by Davide Aversa on 06/12/17 01:07:00 pm

The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

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:

- An
**offline preprocessing step**that generates a logical description of the connections between regions and doors on the map. - An
**online pre-search step**that, given the starting and destination position and the position of every item, can generate a subset of necessary (but, in general, not sufficient) items for the specific path in question.

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

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:

**Understand how different regions of the map are connected through the different obstacles.****Understand how obstacles are related with each other.**For instance, certain obstacles can be encountered only if we remove other obstacles first.**Understand how different map regions are connected.**For instance, if we ask for a path between two disconnected regions, then we can return a failure without even starting with the search.

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**

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

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

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:**

- Slides about IAP preprocessing and pruning: https://www.slideshare.net/DavideAversa/pruning-and-preprocessing-methods-for-inventoryaware-pathfinding
- The paper: http://ieeexplore.ieee.org/abstract/document/7860417/

*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.*