Shortest path - taking obstacles and the terrain into account

Hi, I am interested in performing a shortest-path analysis which takes the terrain into account. However, I am not aware of any method that works in a 3-dimensional path structure.

For example, I want to find out the shortest paths between the points in red. These paths could be the ones shown in blue, if they take obstacles into account. If not, it may generate the dashed line in blue

I came across this fairly rudimentary algorithm that uses Galapagos to optimise the shortest path.

Using that method, I could cull points that are within the polylines of an obstacle and then put a penalty on the resulting distance to filter the results (i.e. if the number of points is lower than the starting number, multiply by 10).
Though, I find that approach a bit too rough, since it won’t find paths that may be a bit more indirect, but a lot less sloped. Like this approach with Kangaroo:

From: Min/Max Slope Pathfinder in Kangaroo - #7 by arten

So my question is: is there a middle course between these two approaches? Ideally, I would like the optimisation to take obstacles into account without immediately resorting to penalties.

2 Likes

I would probably divide the terrain into a regular grid of points and get rid of the points that are within one or more obstacles. The path finding algorithm, which gets the points as input, should thus only be able to travel to valid points and around obstacles.

I do have a point grid that I could use for that. But do the various Dijkstra/ shortest walk algorithms take the 3rd dimension into account? They will only generate the shortest path, right?
I am therefore thinking about using Octopus to minimise the overall travel length as well as the vertical distance travelled.

It depends, but most algorithms can be adapted to take weights into account, which could be the z-values of your points.

Try this: Megarachne | Food4Rhino

Turn your terrain into a mesh, Megarachne will turn this mesh into a graph. Then you can find path using one of the algorithms. It works in 3d as well.

To take obstacles into an account: obstacles should cut out the terrain mesh. If you want to have your terrain mesh as you have right now - you can have 2 meshes: terrain mesh, and mesh created from terrain mesh but with cut outs, just to use it as graph.

1 Like

A few notes that might be worth considering:

A common path finding strategy in video games and robotics is to use a navigation mesh, which enables one to find shortest/weighted paths in topologically complex environments (i.e. with obstacles, holes, terrain etc.) using graph theory algorithms (e.g. Dijkstra’s shortest path). I did a bunch of work on this a long time ago using NetworkX/GHPython for the graph stuff:

But today you could use any of the graph plugins that exist for Grasshopper (edit: as @w.radaczynski points out above, my bad).

An alternative appropriate graph is the visibility graph, where one connects all the vertices of the obstacles and cull any that intersect the obstacles. Which should yield the shortest visible path (i.e. which would be difficult to represent with navigation mesh):

Another alternative that might be appropriate is a medial axis route network graph, which is what we eventually went with while doing the research above:

11 Likes

4 Likes

@AndersDeleuran interesting approach to Space Syntax by using the Medial Axis, in other threads, such as Old Town Roofs I read that people had difficulties with finding such a line. Looks like a clever solution =b
I have already established a full space syntax analysis of the site (I did the pixel version of a Visibility Graph Analysis :wink: ).

Thanks @w.radaczynski I will give Megarachne a try, looks really convenient for what I want. I also like the clear documentation. I have two questions:

  1. Can I use the vertical distance between mesh edges as weights? That way, I could compute the path with the least vertical deviation. This would be useful for wheelchair paths, amongst others.
  2. For smoothing the shortest path, would it hurt the speed of the algorithm a lot if I add diagonals across the entire mesh (so create 4 triangles out of every square)? If it doesn’t that would make it easier to convert the path into a smooth curve.
  1. If I remember correctly it uses only absolute distances in 3d as weights.
  2. What I do is I smooth the result curve at the end to make it look natural. But yes, you can add diagonals (triangulate) and yes, it will affect the speed, but you have to check out if it’s an issue in your case or not. Generally I recommend trying out different meshes to see how it affect the end result. Would love to see your results :wink:

Yeah it really is an interesting and deep field of research. I think Megarachne should work well for you indeed.

In addition to graph theory and relaxation, another strategy I omitted that’s worth considering is agent-based logic. I’m not sure if there are any plugins available that would work, but it’s not too complex to write some code that finds the least/target steep path on a terrain for instance. I recently wrote this one (in-house, so can’t share), that operates by stepping N times from a source to a sink node by sampling along a view fan/cone onto the terrain at each step. Something like this should also be able to take obstacles into account, either as voids or appended in/onto the terrain mesh:

2 Likes

Unfortunately, I can’t write code and this project’s scope is not suited to do so.

I am now also looking into the DecodingSpaces toolbox’ example files, because it should be able to do custom edge weighting (incl. slope). It also has CUDA compute, so it should be fast for me.


And I need it anyways to judge my design, so I can avoid the round trip from Grasshopper > DepthmapX > QGIS…

Given the opportunity:

  1. Any decent D routing algo can solve the path in 3D. Input is the classic AdjMatrix (with distances as R/C cell values) and the from/to Graph node indices. Any valid Graph is suitable for a go (as far as Islands are correctly found - this is done solely via Graph’s VV Connectivity and Recursion). See a Random Prox Graph, and 2 Meshes (as Graphs) . So for a terrain DR you need just a Mesh with a proper user defined (in order to speed up the results) dubdivision/refinement.



  1. Adding arbitary roules to the cost calculation (obviously rules related with max slope, obstacles [i.e. Graph nodes marked as no-no], min radii turn [hairpins] etc etc - if we are talking roads and the likes) is more or less possible. If time permits I’ll add some using a random terrain generator of mine for testing. For instance - shown a rather small part of a DR Method - this is the first (out of few) if clause that needs some mods.

  1. Another way to define obstacles is simply to remove the terrain mesh faces of interest (thus the resulting graph [i.e. the Mesh edges, that is] would be ready for a routing with no other checks).

  2. For Graphs with 5-15K nodes expect times around 200-400 ms (in my slowest - on purpose - test CPU). With some 12th gen i9K you can hope for 50-100 ms.That prior implementing parallel solutions.

@PeterFotiadis That looks really helpful and I am very interested in your script. I will certainly give you credit and add your script to my reference list. I was also looking into adding additional cost rules, but for the DecodingSpaces toolbox, they can only be set to the vertices. :frowning:
As for 3. culling the mesh faces or edges would indeed do the trick for non-access areas.

Please let me know if you could manage to provide the script for me. No worries if you are not able to, then I’ll use Megarachne for the shortest path and octopus optimalisation for the least sloped path.

Well … as least for the slope roule we are talking about a Matrix similar to the Adj Matrix mentioned above … the only difference is that cells contain slope angles per given R/C Node pair. So validation(s) [i.e **score rating**] related to the correct next Node should implement logical AND (&& in C#) condition(s).

I don’t know how DecodingSpaces implemented this in the code, I only see inputs for weights per point, so I don’t see how this would equate to a node pair (edge), because it doesn’t seem to be that way to me. At least, from the nodes and the example files that I could find online.

I understand the these algorithms work, but I don’t understand the scripts, both in terms of syntax and the way it is written in general, though I can understand a little python by reading it.

I used the Spider Web add-in a few years back to compute catchment areas based on road networks weighted with speed limits for each road segment. At that time the creator Richard Schaffernick had some good documentation and examples posted online, but the links no longer seem to work.

The attached definition is created from on one of his example files I found in my archive showing the shortest path with weights based on slope.

FlattestPaths_BW.gh (1.8 MB)

2 Likes

That’s very bad: you’ll be always dependant on others work (I never do that - at any cost). That said P is not the way for that type of stuff (if Nodes are a zillion).

Other than that Plan B could be a classic A-Star routing with additional rules (DR is in fact a subset of ASR), See a 2D demo (for clarity) where a random grid (with user controlled density propability [ thus rnd “obstacles” - the voids, that is]) is used - instead of a classic Graph. Rectangles replace pts for clarity. In 3D this is rather hard to visualise. If that was a Graph … obviously Island dedection is the first thing to do (otherwise you’ll get bananas).

That said obstacles may be “fixed” (like a very big rock or some building) or “removable” (like a small rock or some obsolete building). Having slopes in mind a small local steep valley … well … this may be a non issue (via a small bridge) … blah, blah. Plus (real-life roads) the ground characteristics (dictating the final cost) … blah, blah.

That said a “composite” weight Node Property is one thing … but in real life and for real terrains and for real roads … I can hardly see how this could been solved without a robust backtracing approach (and that brings us to the rabbit hole: performance with a zillion Nodes on hand).




2 Likes

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 path vertices and projects them back onto the mesh in Z:


220531_LeastSteepMeshPath_00.gh (312.8 KB)

4 Likes

Thanks @Brian_Washburn your definition seems to work really well.
I am having some difficulties interpreting the graphmapper remapping.

Screenshots:

Although I do see a pattern in what the mapping does, I would prefer to have a 0 to 1 slider to mediate between the shortest path and the least slope priority. Do you know how I could incorporate this? I have tried a couple of things with the weight input, but couldn’t get it to work.

Shortest Path - Internalised data.gh (1.2 MB)

As far as triangulation is concerned, apparently spiderweb doesn’t like that.

It create these interesting patterns (first is from a delaunay mesh). But it does compute the paths as expected.