*This article has been originally published on Gamasutra.*

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