Database-Driven Real-Time Heuristic Search in Video-Game Pathfinding

摘要: Real-time heuristic search algorithms satisfy a constant bound on the amount of planning per action, independent problem size. These are useful when time or memory resources limited, rapid response is required. An example such pathfinding in video games where numerous units may be simultaneously required to react promptly player's commands. Classic real-time cannot deployed due their obvious state revisitation (“scrubbing”). Recent have improved performance by using database precomputed subgoals. However, common issue that precomputation can large, and there no guarantee data adequately cover space. In this paper, we present new approach guarantees coverage abstracting space, same algorithm performs search. It reduces via use dynamic programming. The eliminates learning component resultant “scrubbing.” Experimental results maps tens millions grid cells from Counter-Strike: Source benchmark Dragon Age: Origins show significantly faster execution times optimality compared previous algorithms.