ai – Any good pathfinding algorithm for lots of different speed zones? NavMesh seems not work


I have a terrain map with lots of different areas: roads, grass, swamp, forest, mountains. Each has different speed for the player. The map is continuous 3D map, not grids.

Given a start & end point, I want to find the shortest time path instead of shortest distance path.

I tried NavMesh with area cost as the standard solution. But it could not solve system with different speed zones correctly.

For example, given a simple NavMesh graph, each square is a nav mesh (you can think of two triangles if you like), gray is road, which has fastest speed; green is swamp, which has slowest speed. Given the start point s1 to end point e1. The NavMesh algorithm will give the direct path p1 since it’s translating within one mesh, no matter what the area cost is. But the actually shortest time path would be p2: get out of swamp, then travel along the road, finally get into the swamp again.

enter image description here

Another example is s2 -> e2. The actually shortest time is the direct path, but the NavMesh would give the red path since each mesh only count once, without considering the path length.

So for my use case, what would be a good path finding algorithm?