Case-based subgoaling in real-time heuristic search for video game pathfinding

摘要: Real-time heuristic search algorithms satisfy a constant bound on the amount of planning per action, independent problem size. As result, they scale up well as problems become larger. This property would make them suited for video games where Artificial Intelligence controlled agents must react quickly to user commands and other agents. actions. On downside, real-time employ learning methods that frequently lead poor solution quality cause agent appear irrational by re-visiting same states repeatedly. The situation changed recently with new algorithm, D LRTA*, which attempted eliminate automatically selecting subgoals. LRTA* is poised games, except it has complex memory-demanding pre-computation phase during builds database In this paper, we propose simpler more memory-efficient way pre-computering subgoals thereby eliminating main obstacle applying state-of-the-art in games. algorithm solves number randomly chosen off-line, compresses solutions into series stores database. When presented novel on-line, queries most similar previously solved case uses its solve problem. domain pathfinding four large game maps, delivers eight times better while using 57 less memory requiring 14% time.