So I've tried implementing the code from https://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html​ , I've really wrote it down line by line, my A* works, but the string pulling does not have the desired effect. I have a suspicion that the problem might be that this algorithm expects the “left” and “right” points of a portal to be the same, no matter if you are going from node A→B or B→A. Right now I have one connection going each way, with the right and left points being relative to the direction that the connection is leading. I thought this makes sense, but it seems like it's only working one way, and is doing the opposite of what it's supposed to if you go the other way. I could test this out, but would have to rewrite the parsing and serializing of the navmesh quite a bit, so would like to know if anyone knows whether this is the issue!

One thing I don't understand about typical games pathfinding is that they stick to the navmesh approach, which is much less flexible than a roadmap-based graph data structure, and also much more difficult to generate graphs for because of the need for a convex decomposition of walkable space. With a roadmap, you basically just generate random points and connect them if they are mutually visible. With some post-processing to remove extraneous/redundant graph edges and nodes, this can produce a clean simple graph for navigation.

To do the path smoothing with a roadmap, you just check at each time step if the agent can see the next node on the planned path. If so, it checks the next nodes in the path until it finds one that is not visible. Then, the agent heads toward the point that is farthest along the path that it can see. As nodes become visible, the agent will turn toward the new intermediate goal. You can make this path smoother by just smoothing the agent's current direction angle with a simple low pass filter.

Aressera said:
One thing I don't understand about typical games pathfinding is that they stick to the navmesh approach, which is much less flexible than a roadmap-based graph data structure, and also much more difficult to generate graphs for because of the need for a convex decomposition of walkable space.

I would argue:

The wikipedia article proposes to generate the graph at runtime from a set of (precomputed) points. That means you need an acceleration structure to query nearby points. Navmesh does to need any of this.

A navmesh can be made respecting the size of agents, so they fit through a narrow passage. A roadmap line connecting two points lacks the information. A NPC may try to get through a passage which is too narrow.

Convex decomposition is one method to generate a navmesh, but not the only one.

A roadmap (as seen in the example) can have multiple road lines crossing each other at the same space. But there is no node to connect them at the point they meet, so an agent can not pick the other route at a crossing - he has to get to a node first, causing a detour.

A navmesh does not only describe potential paths, but also area of space using polygons. So you can use it to implement dynamic obstacle avoidance, strafing to dodge shots, and many such things a game needs, only by looking at the navmesh. There is no need to do collision detection with the static environment, because the navmesh alone already knows enough about it.
I think that's the major advantage, but ofc. that's restricted to assuming a static environment.

JoeJ said:
A navmesh can be made respecting the size of agents, so they fit through a narrow passage. A roadmap line connecting two points lacks the information. A NPC may try to get through a passage which is too narrow.

This can be accounted for by inflating the configuration space by the size of the agent. I.e. don't place points near obstacles, and do a swept sphere test to check visibility instead of ray tracing.

JoeJ said:
That means you need an acceleration structure to query nearby points. Navmesh does to need any of this.

How do you determine what navmesh polygon the agent is within when it spawns? You need some kind of acceleration structure for that anyway, or pay the O(n) tax. Finding the nearest point is also simpler/faster than finding the nearest polygon.

Roadmaps can be generated dynamically and incrementally at runtime as the agent navigates the space, which is a major advantage for procedural content.

Aressera said:
How do you determine what navmesh polygon the agent is within when it spawns?

I link the spawn point to the navmesh, all done offline \:D/

Aressera said:
Roadmaps can be generated dynamically and incrementally at runtime as the agent navigates the space, which is a major advantage for procedural content.

I see. So you use it because you can't do offline pre-computation at all.

Maybe i'll do something dynamic too. I plan to generate small framebuffers from the surfel hierarchy i use for GI. Then i can experiment with vision based AI for moment to moment gameplay. Not sure if this makes sense, but worth a try… : )