4
$\begingroup$

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 ...

enter image description here enter image description here

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

enter image description here

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.

enter image description here

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).

$\endgroup$
17
  • $\begingroup$ Hi, there.. would 'Shortest path through an ordered list of points' be a more accurate title? Just quibbling, might be wrong.. $\endgroup$
    – Robin Betts
    Oct 29, 2023 at 19:25
  • $\begingroup$ Sure ... Thanks :) It is already a few days I'm scratching not only my head for this topic ... trying to find right direction from many directions :) so I'm loosing control and my healthy distance. $\endgroup$
    – vklidu
    Oct 29, 2023 at 19:35
  • $\begingroup$ sounds like you answered your own question in your question: why don't you make several "shortest path" for every "subpath" and then connect them? $\endgroup$
    – Chris
    Oct 30, 2023 at 8:22
  • 1
    $\begingroup$ @Chris Because I don't have a clue how to automate such process :) ... and also I thought there could be probably much better way. $\endgroup$
    – vklidu
    Oct 30, 2023 at 9:58
  • 1
    $\begingroup$ If I understand correctly you want to connect via shortest path the indices pairwise: 0>14,14>40, 40>44, 44>58, 58>61, 61>70, 70>74, 74>80. This can't be done with a single Shortest Path node set up. You need exactly one start vertex and one end vertex to force a pair connection. That means you need 8 Node setups with the current algorithm. If there is a way to define a set of points as mandatory to pass through then that would be great. The only way with the current algorithm I see is via manipulating the Edge Cost values. Not sure how to that yet, but its worth exploring. $\endgroup$ Oct 30, 2023 at 10:02

1 Answer 1

2
$\begingroup$

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:

enter image description here

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

enter image description here

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.

enter image description here

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.

enter image description here

  1. 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:

enter image description here

All grids are available for testing in the file

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

enter image description here

  1. 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.

  1. 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.

enter image description here

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:

enter image description here

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:

enter image description here

and a close-up:

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ Thanks a lot for the answer ... may I ask you to extend your answer about Repeat Zone version you mentioned? That is something I hoped for :) Thanks for your time. $\endgroup$
    – vklidu
    Nov 7, 2023 at 10:53
  • 1
    $\begingroup$ Edited the answer to include the Blender v4 Repeat Zone. This will save a lot of Node space :) $\endgroup$ Nov 7, 2023 at 12:50
  • $\begingroup$ Awesome :) Thank you again. $\endgroup$
    – vklidu
    Nov 7, 2023 at 13:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .