# Dynamic navigation mesh generation algorithm

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
• How exactly do you find grid systems to be a problem with freely positioned objects? Apr 15, 2016 at 10:35
• I can't flag the question because of the bounty, but a possible duplicate with gamedev.stackexchange.com/questions/31208/….
– user35344
Apr 15, 2016 at 10:36
• @Tyyppi_77 my question is more about the HM algorithm, already saw this question but it did not help. WilliamMariager: obstacles and moving objects won't "snap" to a grid and I could have round objects (transformed to pseudo-round polygons). At the end, I want to generate a graph of convex polygons, but I need a fast-triangulation algorithm to achieve this Apr 15, 2016 at 10:53
• Navigation and how things move visually are two different things. The result of navigation on a grid doesn't mean your object has to move in a gridlike manner. Just has to move from one node to the next. Apr 15, 2016 at 11:00
• but you can only deal with horizontal and vertical segments, right ? Apr 15, 2016 at 11:04

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.

• Thanks for your try. I'm aware circle being a problem, that's why I turn them into polygons. I had a look at people.mpi-inf.mpg.de/~mehlhorn/ftp/FastTriangulation.pdf and I am looking for the outer tirangulation algorithm. My map is divided into chunks and each one is responsible of maintaining its navmesh. This way I have multiple levels of pathfinding and I can avoid generating a huge navmesh each time something is added. Apr 16, 2016 at 17:01
• It's not as much the circle (which IS a polygon) being the problem, but that your polygon is not simple - you want to triangulate between multiple polygons. BUT: Would it be acceptable to merge any obstacle polygon with the surrounding "arena" polygon, each time one appears (and reverse as it disappears), so that you still end up with one simple polygon for that chunk? This would simply mean finding the closest vertex in the "full" poly. THEN the HM algorithm (which is rather simple to implement) would do the job you want. You'd possibly have to number each obstacle, for chain breaking issues. Apr 16, 2016 at 19:20
• I made a pen to show different use case : codepen.io/VincentCharpentier/full/bpMYVd I don't see how you would merge an obstacle with the area polygon if they have no vertice in common (first example). (Thanks for your help) Apr 17, 2016 at 10:00
• Maybe I should go for a Delaunay triangulation instead ? It seems to accept holes in the poly Apr 17, 2016 at 10:01
• You would connect the obstacle square/poly with the surrounding arena poly, by drawing two lines, one from an arena corner A to an obstacle corner B, and one from that same corner B back to the same arena corner A, hence merging the two polys into one. It would have two vertexes on top of each other, but that shouldn't be a problem, just keep track of the line segment's direction, to be able to skip the bad line of them when testing for opposite vertexes in the HM partition. Ofc cut the arena poly where this happens. Same with next obstacle, "bridge" to a nearby arena poly vertex. Apr 17, 2016 at 11:57

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.