This is my attempt to create a Pathfinding solution from scratch in a 2D space using Godot. After watching a GDC 2018 session, precisely "AI Summit: 'Death Stranding': An AI Postmortem" session, which motivates me to try recreating the algorithms used.
NOTE: This demo is not perfect in any way, as this is a part of my learning journey.
I like to recreate something that I recently study about Dynamic Navmesh creation and Pathfinding from scratch. This is one of my way to learn thoroughly about something. In the end, I will not use this algorithm as there will be more stable implementation of the algorithm, but for the purpose of learning, I tried to recreate it.
- For Navigation Mesh creation, it uses a combination of grid array of circle bodies, and Marching Squares to create the polygons based on the same grid.
- As a note, since polygons created by Marching Squares has too many lines, it uses Visvalingam–Whyatt algorithm.
- Then, for the triangle (Pathfinding nodes) creation it uses Greedy based ear clipping method.
- Pathfinding method is A*, and the results are passed to Funnel algorithm to create more simplified path.
- And since the path created by A* is not yet optimal (due to the nature of triangle shaped nodes), the resulting path will be processed again using Divide and Conquer with raycast (explained further in one of the comments of the article "Simple Stupid Funnel Algorithm " in references).
Use Mouse Right to move the camera by dragging, use scroll wheel to zoom in and out.
Switch mode to "Polygon Creation", "Move Polygon" or "Delete Polygon" to manipulate the Navmesh data by using polygons.
Use "Navigate Nodes" to try navigate between start position and finish position.
Debug Step Popup will help visualize what is currently happening with the algorithm used.
While in the root directory, run Sconstruct to compile.
scons
Open Godot Engine and load this project (or import godot-workspace/project.godot file from Project Manager window). Run the main scene (navmesh_server_test.tscn) or press F5.
To create much more optimized build, you have to compile the template builds of Godot Engine. Refer to build-profile/custom-template.py comments to start.
- https://gdcvault.com/play/1027144/AI-Summit-Death-Stranding-An
- https://en.wikipedia.org/wiki/Marching_squares
- https://dyn4j.org/2021/06/2021-06-10-simple-polygon-simplification/
- https://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method
- https://en.wikipedia.org/wiki/A*_search_algorithm
- http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html
- https://medium.com/@reza.teshnizi/the-funnel-algorithm-explained-visually-41e374172d2d
- And more in the comments of some functions in algorithm.h source code.