I'm working with a navmesh of an existing game. There are two components of the navmesh data: rectangles (min corner and max corner) which represent the cells and edges (min point, max point, src cell, dest cell, and whether the edge is walkable or not) which represent portals between cells. I'm not sure how to find the shortest path between two points generally in this navmesh.

I had an impression that the steps of finding the path were quite easy after reading this article: https://www.gamedev.net/tutorials/programming/artificial-intelligence/navigation-meshes-and-pathfinding-r4880/​

I expected that I could: 1. Find the sequence of cells which contain the shortest path. 2. Use a string-pulling algorithm to take some unnecessary steps out of the path.

However after a lot of trial an error, step 1 it turning out to be quite difficult. I have completed a couple different iterations where I get suboptimal paths. In both cases, I'm creating a graph based on the cells' geometry and the connectivity between cells. I then search this graph using Dijkstra's algorithm and the physical distances between the nodes I've created.

https://imgur.com/a/Rt3jZRu​ In this first case, I connect the midpoint of every cell to the midpoint of every portal from/to that cell.

https://imgur.com/a/ULIeEta​ In this other case, I connect the min and max point of a portal to the min and max point of every other portal in the same cell. In both cases I'm ending up with a suboptimal sequence of cells. I'm at the point where I don't have any ideas how to find a more accurate sequence of cells or if this two-part high level algorithm I've described is even the right approach.

Will that approach give you the strictly shortest path? I don't think so. A* will give you the shortest path through the cells based on the cell costs. But string-tightening takes out some more distance, and it's not guaranteed that the shortest path before string-tightening is the shortest path after string-tightening.

But do you care? It's not going to be that far off.

SandSnip3r said:
https://imgur.com/a/Rt3jZRu​ In this first case, I connect the midpoint of every cell to the midpoint of every portal from/to that cell.

Looks all good and correct, so if you are not happy with the result, i guess you want a more detailed navmesh to get more precise results. Which ofc. will take more time to find shortest paths.

To add details, there are many options:

Ditch navmesh and use fine regular grid instead. (sounds brute force, but grid needs no adjacency pointers, so at some point it may become faster)

Tessellate your navmesh. Starting from your center approach, the purple center lines and green rectangle lines from a quad mesh.
You could triangulate each quad, by adding an edge that splits the quad, and taking the shorter edge of the two options we have.
Optional: Use voroni triangulation, and eventually vertex relaxatation to improve the quality of the mesh. (relaxatation would distort your initial rectangle regions, so maybe that's no option).

The result should be much better, but to improve it further you could try to make the initial distribution of vertices more adaptive to requirements.
For example, Large rectangles that neighbor small rectangles could add more vertices to their interior than just a single center vertex. E.g. adding a region of 3 x 2 vertices for a rectangle that has initial size of 5 x 4.
After that, i expect the result to be pretty optimal.

I found this image to illustrate what i would consider to be optimal:

It has higher resolution where necessary (here at the boundary), and the triangles are well shaped without sharp angles.

Nagle said:

Will that approach give you the strictly shortest path? I don't think so. A* will give you the shortest path through the cells based on the cell costs. But string-tightening takes out some more distance, and it's not guaranteed that the shortest path before string-tightening is the shortest path after string-tightening.

But do you care? It's not going to be that far off.

I care about the theory. Though it might not be much of an improvement, I'd like to find out why this method isn't finding the optimum path. I'm familiar with A*, but I'm not sure how it's going to give a shorter path. What exactly do you mean by “cell costs”? Somehow I need a measure of distance of my path. I cant entirely trust center-of-cell to center-of-cell because that straight line might cut corners of another cell.

JoeJ said:

Looks all good and correct, so if you are not happy with the result, i guess you want a more detailed navmesh to get more precise results. Which ofc. will take more time to find shortest paths.

Thanks for suggesting more approaches!

https://imgur.com/a/PgRgfhT​ I don't think the first image I posted looks correct. The blue line is what seems to be the actual optimum path, which involves different cells than the cells in the pink calculated path. Yes, this would be post-string-pulling. Is it really impossible to do better with this navmesh? It seems like a more detailed navmesh like you've shown only gives you more expressivity around curved edges in the world. Shouldn't any correct navmesh be sufficient?

Your paths (both of them) are clearly topologically correct, and can be turned into the same optimal path by string-pulling, so what's the problem?

@a light breeze Is that true? I don't know any string pulling algorithms besides the “stupid-simple funnel algorithm” mentioned in that article I linked. How does a string-pulling algorithm change the cells along the path? Or, worded another way, how does a string-pulling algorithm move the path into other cells that weren't a part of the originally found path?

I've found an even shorter path! https://imgur.com/a/jA1n5z7​​ (This is the same graph and algorithm as in my second image in the original post, but I fixed a bug in my Dijkstra's)

Unfortunately, because of my graph construction, this is the best I can do.

If I really wanted to find an even better path, I'd need to start adding more “nodes” to my graph at seemingly arbitrary points of cells, or I'd need a string-pulling algorithm which can “nudge” the path into different cells if the overall path is better.