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

Continue Reading on Gamasutra!

Header Image
Inventory-Aware Pathfinding - Part 1

Everybody know what pathfinding is. I don’t think I have to explain to a game developers audience why pathfinding is so important in games. If something in your game is moving not in a straight …

Read
Header Image
Boost Hierarchical Pathfinding with Extended Graphs

As you may already know if you follow me on Twitter (why not?), I often work with pathfinding. This thing started as a small side quest during my Ph.D. and then grew up to become the main topic of my …

Read
Header Image
Back from AIIDE 2014

Hi everyone! Sorry for the long absence but my days are really full of commitments and terrible news. It is still not over, but but I really need write about something before is too late. :) During …

Read
comments powered by Disqus