Automatic generation of navigation meshes and pathfinding on the meshes.
It uses a polygon triangulation algorithm to generate navigation meshes and the A* algorithm to find a path.
Used C++, SDL2, OpenGL, and ImGui.
All source codes are in the NavMesh folder, and the executable is in the Demo folder with libraries.
Use left/right mouse buttons to set start/end points of a path.
You can change the weight of the heuristic for A* using "Weight" bar.
Use "Show all nodes considered" option to see how it affects the pathfinding.
"Path smoothing" option shows a more narrowed path.
You may change colors using the color editor.
Click "Edit mode" in the UI.
To move walls, drag a red box at the center of a wall.
To change the shape of the wall, drag a red box on the vertices of a wall.
Generating navigation meshes uses Polygon Triangulation algorithm, which has two parts.
- Partition the polygon into y-monotone pieces.
- Triangulate each piece.
After triangulation has done, there is the pathfinding section.
- Find the path between two given points on the polygon using A*.
- Smooth the path using Funnel Algorithm.
You can read the detailed explanation of the algorithms below.