Path caching in real-time strategy games

This paper proposes a performance optimization for search-based path-planning simulations with the aim to improve systemic scalability. Instead of clustering path requests per agent group, paths are cached at path-request time. Paths are cloned or re-used after selection based on request characteristics, agent properties and external matching criteria. Graph search effort is reduced proportional to the number of agents with similar nearby destinations, while the unique navigational behavior of each individual agent remains unchanged and intact. Formation coherence is maximal for homogeneous navigation, and agent response time improves significantly for large agent groups compared to solutions without this optimization. Explicit multi-agent consensus models are not required and behavioral discontinuities are avoided