Colt “MainRoach” McAnlis—Ensemble Studios
James Stewart—Stormfront Studios
In the years since Greg Snook’s seminal article in the first Game Programming Gems [Snook00], navigation meshes have become the search space representation of choice for pathfinding in games. Compared to the waypoint approach of the previous generation, navigation meshes are more amenable to automatic offline generation, produce better (in many cases, optimal) paths, and provide more useful information to entities that must negotiate dynamic obstacles. These benefits come at the cost of increased memory usage and slower search performance, problems of increasing severity given the content demands of next-gen titles—open-world games in particular.