Game pathfinding is a challenging problem due to a limited amount of per-frame CPU time commonly shared among many simultaneously pathfinding agents. The challenge is rising with each new generation of games due to progressively larger and more complex environments and larger numbers of agents pathfinding in them. Algorithms based on A* tend to scale poorly as they must compute a complete, possibly abstract, path for each agent before the agent can move. Real-time heuristic search algorithms satisfy a constant bound on the amount of planning per move, independent of problem size. These algorithms are thus a promising approach to large scale multi-agent pathfinding in video games. However, until recently, real-time heuristic search algorithms universally exhibited a visually unappealing “scrubbing” behavior by repeatedly revisiting map locations. This had prevented their adoption by video game developers. In this chapter, we review three modern search algorithms which address the “scrubbing” problem in different ways. Each algorithm presentation is complete with an empirical evaluation on game maps.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- Real-Time Heuristic Search for Pathfinding in Video Games
Nathan R. Sturtevant
- Springer New York
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia