ABSTRACT
A navigation mesh is composed of a listing of regions, which are well-defined convex groupings of traversable space and an additional listing describing connectivity. Traditionally, navigation meshes have been created either by hand or using some form of automated spatial decomposition algorithm that examines the obstructions present in the environment and then breaks down the area between them into as few regions as possible. Existing growth-based spatial decomposition algorithms took advantage of a postprocessing step to improve the quality of the resulting navigation mesh. The Wavefront algorithm generates fast, high-quality decompositions for use as navigation meshes via a quad-based expansion algorithm. Such decompositions have fewer small and degenerate regions that can interfere with character navigation. Additionally, since wavefront algorithm only grows one region at a time, there is less post processing that would normally be caused by multiple regions competing to fill the same convex area.
