A* Shortest Path - Egress Diagram (Almost There But Need Help)

[AndersDeleuran]

@maje90

Relaxing is after, first you have to find an initial rough path passing on the right side of obstacles.
If you found the wrong path, relaxing or optimizing that path do not help, it will be still wrong.

That is true. However, if the mesh is a fairly isotropic triangle mesh (e.g. remeshed using TriRemesh), and you operate on face-face graphs, that does appear to work fairly predictably. See an example here:

Shortest path - taking obstacles and the terrain into account

FWIW, it’d be pretty trivial to add slope angle as the edge weight to this MeshPaths GHPython component I once wrote (i.e. add another weightMode to the two functions that generate the graph), which implements networkx for the graph computation. You can download the 1.5 version here and unzip it to: C:\Users\USERNAME\AppData\Roaming\McNeel\Rhinoceros\7.0\scripts Edit: Here’s a quick implementation of what I was suggesting above. I also added a Smoothen input, which iteratively averages the pa…

@maje90

also, method like kangaroo will create a new path that often cut corners…

Yes it can be pretty tricky to find the right combination of resolution/constraints/settings. Edit: Regarding the cutting corners issue, one might use the Collider goal to prevent the relaxed polyline edges cutting into vertices of the mesh naked perimeter vertices. I haven’t tried it, but it might be worth considering.

The example you posted can be solved using the convex hull to find two paths around the obstacle and picking the shorter one, or using a visibility graph. Which can both be extended to work on 2.5D meshes. It would probably help if we had a mesh/case that can not be solved using such relatively simple methods.