Python Shortest Walk 3D: Interpolate grid of points with start & end point to get shortest curve thorough points of grid

[STUDENT_F]

Hi,

simplified 2D logic:

what you can see in my drawing ist a grid of points. I want to interpolate from A to B and A to C for example. (Route 1: A start point, B endpoint), (Route 2: A start point, C end point).

I want to interpolate through one point in every single x column (diagonal is also okay for me) but at the end, I need the shortest possible curve from A to B.

Here is my file where I define start and endpoint at the end of the script.
Tester.gh (43.8 KB)

Maybe someone can help with with the script or just the logic as well.
Thanks a lot for your help!

[ivelin.peychev]

Google “A* python algorithm” or “A-star python algorithm”

[Dancergraham (Graham Knapp)]

Hi, in terms of the logic you just need to step each coordinate(x,y,z) by 1 until each matches your target coordinate

[STUDENT_F]

Is it the same like the Dijkstra’s algorithm?

[ivelin.peychev]

@STUDENT_F

Dijkstra’s

I don’t think so, because in A-star you don’t check every possible coordinate you mark the ones with increasing parameter values as DON’T GO THERE and you quickly find the path.

At least this is what I see on a prima vista.

A-star

Dijkstra

Gifs are from Wikipedia

Pretty descriptive

[STUDENT_F]

Searching algorithms are a hole new field to me.
I suspect that the Dijkstra algorithm has a negative consequence for performance, beacuse in complex contexts there are many “actors” that has to be analysed by the algorithm.

I will study A* the next hours, so hopefully it works for me. Maybe I will come back to you later.

Until now, thanks a lot for your help.
One more question. Without being a computer scientist, where did you learn that kind of stuff? Is there anywhere a offical Python “Algorithm Library of different kinds (Searching Algorithms, etc.)” . I am new to Python, so I am not really shure where to sort this in the topic of rhino, grasshopper, python.

[ivelin.peychev]

If you don’t know what you’re doing start with Dijkstra, with a single actor, the most basic one.

Hell, I haven’t yet implemented A-star myself. Mostly because I don’t have time for that. And because I’m stubborn and I wanna do it myself

[AndersDeleuran]

You could also implement a graph library, I like to use networkx in GHPython, uploaded a simple example of computing shortest paths on a RhinoCommon mesh here:

AndersDeleuran/MeshAnalysis/blob/master/src/MeshPaths.py

[Dancergraham (Graham Knapp)]

@"STUDENT_F

One more question. Without being a computer scientist, where did you learn that kind of stuff? Is there anywhere a offical Python “Algorithm Library of different kinds (Searching Algorithms, etc.)” . I am new to Python,

I personally learned by doing project Euler challenges and reading other people’s solutions. Also see here for a bunch of Python algorithms.
https://pygorithm.readthedocs.io/en/latest/

[STUDENT_F]

Thanks a lot. I will study that!
Please check you mails!

Fabian

[STUDENT_F]

Thanks a lot for that hint!

[Adam_M (Adam Mounsey)]

Chris Hanleychanley also posted some useful tips/resources here: Handy Tips for GHPython Editor/Component (Rhino 6)

[anon39580149]

maybe you need first to draw a box between the two points : start & end, that make it easier to find the shortest line

[STUDENT_F]

why do you thank that the box helps? The points that are stored inside have an similiar array like mine in the script I posted.

[STUDENT_F]

Interesting information! Thanks a lot!

[anon39580149]

you want the short way between A and B so you need to reduce the possibilities and the number of points ,you can’t use all points

[tim.stark]

This is no generic rule. Image a bigger box between the start and end point as obstacle and you won‘t find the Route.

…
About learning resources: I really enjoyed „the coding train“ YouTube channel by Daniel Shiffman and his book „the nature of code“. It‘s mostly written in processing, but it‘s easy to translate. He also has some path finding tutorials. The guy is super funny in my opinion

[anon39580149]

Do you understand the idea? 2 points in 3d space the shortest route is inside the box between them

[tim.stark]

I know what you mean. As I said, not if you have obstacles…

[STUDENT_F]

Guys, I am not able to implement the pseudocode example “A Star” into my script. Maybe someone can help me with the script. You can find the important part at the bottom of the script. Thanks a lot. Here is my new file: Tester.gh (47.0 KB)