I'm working on a 2D game (top down / zelda like view)
I'm struggling with navigation mesh generation, in complex scenarios my homemade algorithm is lost and too slow...
I would really love to see a detailed explanation of Hertel-Melhorn Algorithm (if you have any ressources). I'm open to suggestions for other good algorithms, as long as I can process round and square obstacles.
My map is randomly generated and obstacles can be added anytime.
- I don't want to use a grid system, my entities are positionned freely.
- My map is big so I can't store precalculated paths / I just need pathfinding to be efficient
I am looking for serious documentation of fast triangulation algorithm
If I understand the process of navmesh generation :
- Input walkable area(s) as polygons
- triangulation of walkable area
- (Optionnal) merge triangles to big convex polygons
- Output a node graph