Dynamic navigation mesh generation algorithm

Question

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'm working with Javascript, I can't use c++ library like detour/recast

---

Edit

I am looking for serious documentation of fast triangulation algorithm

If I understand the process of navmesh generation :

1. Input walkable area(s) as polygons
2. triangulation of walkable area
3. (Optionnal) merge triangles to big convex polygons
4. Output a node graph

Answer 1

I'm afraid this answer won't be satisfactory for you.

1. You say you have obstacles, and if i understand right, these would be inside a surrounding, large polygon? The Hertel-Melhorn algorithm works on a single polygon only, not on a polygon holding polygons inside. Additionally, having multiple obstacles (polygons) for partitioning on the outside creates a "compare each polygon to each other" situation. And that sounds very exponential = expensive.

2. You say you want to include round obstacles. Seen from outside, a circle is concave, implying that each of it's vertices is a partition point, and the same of course goes for each other round obstacle as well. It seems this pretty much nullifies the advantage of partitioning in the first place?

A bad path for the logic may be that you want to first create a large, full data set for the entire scenario, and apply navmesh thinking on that - have that as a basis for all objects' all navigation, and maybe for a loger period of time, while yet having moving (or at least appearing/disappearing) obstacles. As partitioning is a "global" thing, each minor change somewhere would cause an entire arena re-partitioning?

Perhaps it would still be more sensible to apply local-to-the-moving-object pathfinding grids (small, isolated ones) with high granularity, such that only take into consideration what is relevant for (very nearby to) the object in question, at it's very current position and only for the next few moments. And then have a larger scale similar, for general (main goal) movement directions?

Also to note: Moving objects do often not have to follow grid points (or node points) exactly. This depends on what they are. You can still make them dislike turning, react slowly, aim n points ahead, calculate curves/polynoms to follow in the grid, etc.

Answer 2

I believe, if you are creating a voxel mesh up 2D, you should create a class that takes a 2D position (Vector2), and one byte (0-255). Every position, there is a value from 0 to 1, and there is a function in the script the AI that makes it surround a position, and a script that do it an interaction between the positions of enemies and items from the list, and when are with a distance, I know it, 10, it calls the function or void AI and passes the corresponding position.