NavMesh Generation

Description

A standalone tool to both create a 2D level with simple rectangles and generate a navigation mesh for the level. The tool has support for generating up to three meshes, each generated depending on the unit radius size that will be using it. Click here to view the Shadow Mapping Demo that utilizes this tool.

Below are pictures showing before and after generating the level. On the second image, three navigation meshes (Blue, Green, Orange) are displayed.

  • Blue:  Unit radius of 20.
  • Green: Unit radius of 10.
  • Orange: Unit radius of 5.

The Algorithm

  • Start with one large navigation mesh polygon
  • For each obstacle polygon
    • For each navigation mesh polygon
      • If the obstacle and mesh polygon are colliding, subdivide the mesh polygon into four equal parts.
      • If a mesh polygon surface area is smaller than some small size, remove it.
  • Repeat the collision and subdivisions until there are no more collisions.
  • Merge any polygons that have at least two equal vertices and repeat until there are no more.
  • Merge any special case polygons (see below). Repeating this step and the previous one until no polygons can be merged.

Untitled-2

Before

NavMesh_Start2

After

NavMesh_Done2