Custom Navmesh

Custom implementation of a Navigation Mesh using Unreal Engine as editor

Showcase:

Setup (in progress)

• Add a supported agent in the project settings with the Nav Data Class as NNNavMesh
• Place a NNNavMesh in the world
  • It should be the only NavData placed in the world
• You character movement component should have the NNavMesh as the preferred NavData. There are many ways to do so.
  • Make you AI character inherit from NNCharacter
  • Make your movement component's character AI inherit from NNAvMovementComponent
  • Override the prefered Navdata from your movement comonent's character AI yourself

TO DO

• Voxelization
  • Gather Geometry
  • Footprint the geometry
  • Implement heightfields
  • Identify walkable spans
  • Implement an open heightfield
    • Create the open spans with the solid spans
    • Collect the open spans walkable neighbours
• Region Generation
  • Implement the water shed algorithm
  • Filter small regions
  • Clear null region borders
• Contour Generation
  • Implement contour generation
  • Simplify the contour
• Convex Polygon Generation
  • Triangulate contours
  • Merge triangles to form convex polygons
• Detail Mesh Generation
• Implement pathfinding
  • Graph generation
  • A*
  • Implement simple point projection
  • Implement path smoothing
• Bake results
• Combine multiple navmesh bounds

Improves

• Refactor the distance field generation
• Replace unreal triangulation with custom one without using ear clipping
• Profile
• Make navmesh generation asynchronous
• Rebuild only the dirty area and not all the navmesh
• Store the polygons in an Octree
• Find proper way to check nearest point to a 3D polygon
• Convert debug macros to console variables for proper debugging