Open Collections

Abstract

Efficient pathfinding on grid-based maps is a crucial aspect of many video games. Multiple algorithms have been developed to solve this problem. The DBA* algorithm leverages a database of pre-computed paths to speed up pathfinding and is both memory- and time-efficient. However, its efficiency is limited to static maps. In this work, we present a case-based system for updating the pre-computed information used in DBA* to adapt the algorithm after the occurrence of map changes. This allows us to apply DBA* to dynamically changing maps, while guaranteeing the same suboptimality as on static maps. With this new system, DBA* can compute paths faster than A* search even while performing two map updates for every path search.