Shortest Walk slows down with large graphs


(Giulio Piacentino) #1

Continuing the discussion from Grasshopper 2:

@Thomas_Helzle do you have a small sample of the definition that you can make public, where I can test and see where the add-on slows down? Also, if you could make a small scheme of which parameters besides Euclidean distance would help you, then I can consider what to add!


Hey piac,

I’m a bit busy ATM but I’ll try to create something for you that shows what I think would be interesting to make the plugin more versatile. Basically it’s about “directability” - having ways to tell the paths that they should follow a certain path or direction as long as possible.
This is an example from Houdinis “shortest path” with custom path costs:

You can see how the paths try to stay in the centre and only turn towards their individual endpoint when they “have to”.
Most natural forms are like that and it generates a much more interesting variety of patterns.
So I could imagine defining a spline curve as a “goal” or “attractor” that the shortest path tries to follow. Attractor behaviour would be good, so the paths don’t follow the guide too absolutely(or at least not if I don’t want them to).

Like you pointed out in the other thread, I’m not even sure if Shortest Walk is the performance hog or if GH simply has a hard time with lots of points no matter what tools you use. I worked with very detailed grids and the system became extremely slow.
Does the plugin use multithreading internally? In theory it should be possible to search each path in it’s own thread?

Cheeers and thanks again for your feedback!


(Giulio Piacentino) #3

The real longer and more difficult part is not multi-threading the finding of a path, but rather constructing the graph from the bunch of lines only once, and in a fast way. Pathfinding should not be very difficult after that. Several different pathfinders can run at the same time.

Another question eventually for later. Should path length always be positive? Or could there be ‘sinks’/shortcuts that have negative or 0 lengths?


I see.

Well, lengths as such should be positive and “real” (the output value I mean), but with path cost I could imagine allowing all kinds of values - this is a different thing in Houdini and can be output per path as well as per point.
They also offer turning cost (which I found quite interesting) and a mode where the actual path length doesn’t come into it at all…
Here are the three interface tabs:

The first can’t be reproduced in GH - every point or line can have resulting values assigned to attributes that you can use later in the graph (so you don’t fiddle with lists and order but instead each entity can hold it’s own information).
The second deals with different costs, for points, primitives (~lines in GH), then turning and angular costs (can be per point as well). etc.
The third tab allows to restrict the path to certain objects, uni-directional primitives and edges to avoid. This is done by entering group names one assigned beforehand.

While this is very flexible, I could imagine a more artist-friendly way, where one deals not with such abstract values but like I said with for instance a spline curve which the paths try to stay close to (with a custom falloff) or something like that. I don’t know the algorithm well enough to offer good suggestions how it could be done.

Cheers and thanks for looking into it!


(Giulio Piacentino) #5

Logged as RH-36458.