Shortest path through an ordered list of points

Question

Intro

Shortest Path is very well documented if you want to generate Start / End path specified by two points. Like here Start at index 0 and End at index 3 ...

Note: Specifically in my case I will use some obstacles blocking the direct connection ...

My question

Is it possible to generate shortest path passing through a several points? Like in this example (with randomly selected vertices) ... the path should start at index 1 find shortest path to index 14, than shortest path to 40, than 44, 58, 61, 70, 74 and end at index 80.

Sorry for old version of blend (3.4 alpha) home workstation limit :) at work I use the latest version.

Note: I already tried connect bunch of points by a spline and thanks to Markus's answer I could let a curve to push from an obstacle, but there are a lot of splines penetrating an obstacles for some reason. So I would like to try a different approach (also recommended in my original post).

Answer 1

This is my approach to solve this problem without simulations. Let's give it a name - Constrained Shortest Path.

In summary, the idea is to force a path [edge selection] via iteration of the Shortest Path algorithm that passes through select set of points (in ascending index number order) from a Mesh grid, giving the resulting path a tangled cable appearance.

Here is the result so far:

The Mesh grid will be added for clarity. As you can see holes are implemented via points deletion using a control Empty object.

Here is the node set up, however it is too complicated to explain in detail here. A .blend file is provided at the end of the post for your own studies.

Here is the short description:

1. Initial Point selection - Select points from the Mesh plane via random value generation to speed up the testing process. As it is hard to control the exact number of selected points or generate a good point distribution this way other methods for selection initializing should be considered.

2. Plane with Hole(s) - this is the mesh from which we select the initial points. The plane has an option for vertex deletion (single hole) . The hole widens with scaling the Empty object.

There are few types of input Geometry grids tested:

• Ordered quad grid - separate object, when the random points are connected they produce a zig-zag like pattern and are not a good candidate.
• Quad grid - separate object with vertex index randomization
• Triangulated grid via modifiers - the host Plane object with modifiers stack before the Geometry Nodes modifier.
• Triangulated grid - separate object with vertex index randomization

Here is a comparison:

All grids are available for testing in the file

3. Elevate the initial point selection - The selected points are moved slightly above the surface, the end points - even higher.

4. Shortest Edge Path Modules - The process is as follows:

a) Select first two vertices from the selection (in ascending order) - Output shortest path via curve

b) Remove the smaller index vertex from the selection.

c) Pass the resulting selection to the next module.

d) Repeat the process.

There are 1+20 operations currently. The file will work best with about 21 selected vertices or less. Add more modules for larger number of selected vertices.

Blender 3.6 doesn't have looping nodes, A Repeat zone is expected to be released in Blender 4.0. This will make the iteration over repetitive processes so much easier.

5. Distribute Mesh Line on Paths - All generated paths are joined in specific order so the indices are in ascending order. A Mesh Line is generated to match the point count of the curve and the positions of these points thus forming a continuous single thread. The Mesh Line is then converted to Curve.

6 Randomize slightly Z positions - just to decrease the amount of overlapping points due to path backtracking.

7 Resampled Auto Handle Curve to Cable - giving the curve a Bezier type with Automatic point handles gives best cable like appearance. Lastly a simple Curve to Mesh node is applied to generate the cable.

You are welcome to explore the .blend file:

Edit: As requested by @vklidu I am including the setup for the upcoming Blender v4.0 using the Utilities > Repeat Zone instead of connecting / removing modules for different amount of selected points:

and a close-up:

You can change the number of Iterations manually or plug the number of selected points to control it automatically.

This should work for Blender Versions 4+. I can't guarantee the Repeat Zone will change after release, but it is most likely to remain the same.