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