Belief-Driven Pathfinding through Personalized Map Abstraction

Abstract

We investigate the case of belief-driven pathfinding (BDP) according to which characters hold a personalized account of a dynamic changing game-world. BDP is concerned with maintaining and revising a set of beliefs that persists over time as a character navigates to subsequent target destinations. This allows for a differentiation among characters with different observations in the game and can provide better believability. We present BGCA*, a practical BDP approach that is based on (i) decomposing the map into regions, (ii) using personalized beliefs per character about the connectivity of regions, and (iii) employing a regular pathfinding component as a service. We evaluate BGCA* in terms of computational effort and precision wrt a regular solver over several benchmark maps. Our results motivate a simple belief revision strategy that induces small overhead and amortizes effort spent toward precision.