I've implemented anisotropic road pathfinding for very large terrains using the Find Shortest Path node. This node is extremely versatile and is clearly intended to be used for this purpose: it allows many ways to define the many costs involved such as slopes of path segments, slopes of terrain points, proximity to water bodies, one-directional paths, cost of tunnels and bridges and so forth. It is also quite fast.

However, there's one thing that cannot be done without calling an external function, and that is to limit curvature angles for roads to avoid generating roads like this:



As you can see, the exit angle from the red bridge is at an unacceptable angle which would make the road extremely dangerous and thus unrealistic. (The screenshot above is from the intermediate stage where paths have been generated and some terraforming has been done, but before final road geometry has been generated.)

There is one parameter that can be used to assign a cost to path curvature:



This applies the value of the Angular Cost attribute multiplied by the angle turned in degrees at each point. Using this will take us a little further, but not all the way. It won't help in the situation in the first screenshot, as the value for the bridge in all cases must be much higher than that of the curvature (or we would get bridges all over the terrain).

One possible approach might be to assign a uniform value to the angular_cost attribute to cater for all normal road points and a considerably higher value for bridges and tunnels. This would take us some way further, but again not all the way as it still would allow for extremely sharp angles if there is no alternative path.

The only solution to this problem I see is to handle this like all other costs: to create a cost function that will return INF (1e1000) for paths that never should be possible. The Find Shortest Path node is designed to handle this type of cost, as it won't consider paths or nodes with INF costs.

To do this, the Custom Edge Cost parameter would be used to call an external function that would accept three path points: the previous, the current, and the next under consideration. It would calculate the XZ angle between these points and return 1e1000 for impossible paths. This is straightforward to implement.

As the terrain is very large, typically 10x10 km with a pathfinding grid resolution of 5 meters, and this computation would be done many, many times, it's obvious that speed is of the essence. Thus I have two questions:

1. What would be faster here, an HScript custom function or Python?
2. Is there a faster way to achieve the same thing without calling an external function? Preliminary experiments indicate a slowdown of several magnitudes, and that's indeed painful as it would require cooking overnight.

This problem definitely has been solved before. It's part of creating the road networks in the Ghost Recon series and many other AAA games I know use Houdini for terrain generation. I'd be surprised if they didn't use this Houdini node for A*/Dijkstra terrain path searches.

Grateful for any ideas.

Reply, UDP fashion:

Using an external function is an unviable idea: HScript is clearly the fastest, but calling it increases the time to find each path from a second or two to several hours which rules out this approach completely. It's simply called too often.

Modification of the Find Shortest Path node itself isn't possible as it is a compiled node.

There remains only one way of removing too acute road angles, but it only works for tunnels and bridges: after the preparatory stage of constructing all possible paths (using an anisotropic path mask to eliminate duplicate paths), post-process the network by iterating over tunnel and bridge points. For bridge and tunnel segments, we can always find the other end, which means that when a segment approaches a tunnel or bridge we always have the three points required to find their XZ angle. Examine each such angle. When too acute, set the corresponding path cost to INF or remove the path entirely.

Angles between points that don't involve bridges or tunnels, i.e. between normal road segments, is trickier, as a full walk of the path structure to consider all possible path combinations probably is too expensive.

Hi Peter,

to avoid sharp curves maybe consider smoothing out the terrain in advance. Alternatively identify sharp turns and smooth them out locally?

Hi Konstantin,

Smoothing out the terrain is of course always an alternative, but in this case, I cannot rely on smoothing being an alternative as the algorithm needs to be completely general and work for any type of terrain, including extremely mountainous terrains. There is also the presence of water in the form of streams, rivers, lakes and oceans which complicate things further. This is no problem, however, as the cost weights and cutoffs can be set to balance things very nicely, and that the algorithm already does.

Identifying sharp turns after the fact, that is after all paths have been generated and modifying the result, is something which quite often is done, but optimal results are not guaranteed. Consider hairpin curves up a mountain slope, for instance - you only have certain leeway in moving path points around before things become unrealistic. But it can be done, manually (which is the most common approach) or algorithmically (which is more difficult).

It's much better to get these things into the basic pathfinding algorithm. In this case, I know I can do the tunnel and bridge angle connections quite easily. Creating cutoffs for the other angles is also possible: it's just a VEX graph traversal and search problem. I'm hoping computational times won't be prohibitive.

One thing which would fix this instantly (and also would be the fastest) is a Maximum Curvature Angle setting in the Find Shortest Path node. It would be trivial to add. But as the source isn't public, preparatory graph traversal will be my friend here.