Path planning with Inventory-driven Jump-Point-Search
This addresses pathfinding for non-player characters in video-games with inventory-dependent obstacles, but it is incremental as it adapts an existing algorithm to a specific scenario.
The paper tackled path planning in navigational domains where traversability depends on acquired items, presenting invJPS, an inventory-driven extension of Jump-Point-Search. The result shows that invJPS preserves JPS's optimality guarantees and symmetry breaking advantages in inventory-based game maps, as demonstrated formally and experimentally.
In many navigational domains the traversability of cells is conditioned on the path taken. This is often the case in video-games, in which a character may need to acquire a certain object (i.e., a key or a flying suit) to be able to traverse specific locations (e.g., doors or high walls). In order for non-player characters to handle such scenarios we present invJPS, an "inventory-driven" pathfinding approach based on the highly successful grid-based Jump-Point-Search (JPS) algorithm. We show, formally and experimentally, that the invJPS preserves JPS's optimality guarantees and its symmetry breaking advantages in inventory-based variants of game maps.