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