Real-Time Heuristic Search for Pathfinding in Video Games

摘要: Game pathfinding is a challenging problem due to limited amount of per-frame CPU time commonly shared among many simultaneously agents. The challenge rising with each new generation games progressively larger and more complex environments numbers agents in them. Algorithms based on A* tend scale poorly as they must compute complete, possibly abstract, path for agent before the can move. Real-time heuristic search algorithms satisfy constant bound planning per move, independent size. These are thus promising approach large multi-agent video games. However, until recently, real-time universally exhibited visually unappealing “scrubbing” behavior by repeatedly revisiting map locations. This had prevented their adoption game developers. In this chapter, we review three modern which address different ways. Each algorithm presentation complete an empirical evaluation maps.