Bounded-Search Pathfinders Based on Influence Maps Generated by Attractors and Repulsors

摘要

This article combines pathfinding and influence fields (or influence maps) in a way that the influence costs replace the traditional distance costs. By placing repulsors and attractors in the game world, we are mixing their influence fields into an overall game influence field, which determines the influence costs in finding a path between a start and a goal node. For that purpose, we introduce an automated method to place such attractors and repulsors, which builds upon the concept of thinning graph (and its dual). This thinning graph is a sort of medial axis of the set of passable tiles of the game map. As a result, we obtain bounded-search pathfinders that avoid obstacles (repulsors) and follows checkpoints (attractors) in an intuitive manner. Moreover, the well-known problem underlying the influence fields, called local extremum trap (i.e., an agent may enter into a place from where there is no escape away), is solved in an elegant way. Also, our influence-driven bounded-search pathfinders are comparable to other influence-based pathfinders in terms of memory expenditure and time performance.