Reading time: 2 minutes.
Improve Inventory-Aware Pathfinding with Map Preprocessing
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
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”.