Pathfinding by Demand Sensitive Map Abstraction

摘要

This paper deals with the problem of pathfinding in realtime strategy games. We have introduced a new algorithm: Demand Sensitive Map Abstraction (DSMA) to overcome some of the challenges faced by the benchmark hierarchical pathfinding algorithm: Hierarchical Pathfinding A~* (HPA~*). DSMA is a type of hierarchical pathfinding algorithm in which we vary the granularity of the abstract map based on pathfinding request demand associated with various regions in the abstract map and the time taken by DSMA to find the previous path. Results from experiments show that dynamically varying the granularity of abstraction helps in maintaining a balance between path quality and search time.