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

STUDENT_F · March 15, 2019, 10:54am

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 · March 15, 2019, 11:18am

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

Dancergraham · March 15, 2019, 11:35am

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 · March 15, 2019, 11:47am

Is it the same like the Dijkstra’s algorithm?

ivelin.peychev · March 15, 2019, 11:54am

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 · March 15, 2019, 12:09pm

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 · March 15, 2019, 12:11pm

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 · March 15, 2019, 12:16pm

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:

github.com

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

""" 
Calculate shortest paths on a mesh. Uses the NetworkX 1.5 Python module:
Download here:
http://networkx.lanl.gov/download/networkx/
Read about shortest path algorithms here:
http://networkx.lanl.gov/archive/networkx-1.5/reference/algorithms.shortest_paths.html
-
Name: MeshPaths
Updated: 141031
Author: Anders Holden Deleuran (CITA/KADK)
Copyright: Creative Commons - Attribution 4.0 International
GitHub: www.github.com/AndersDeleuran/MeshAnalysis
Contact: adel@kadk.dk

    Args:
        Mesh: The mesh to calculate paths on.
        Destinations: List of lines representing path source (line start) and path target (line end).
        GraphType: Make the mesh graph nodes from either its vertices or its faces
        PathMode: The algorithm to use when calculating the shortest path (refer to NetworkX documentation).
        WeightMode: The graph edge weight. Can be either metric length or the same weight for all edges (1).

This file has been truncated. show original

Dancergraham · March 15, 2019, 12:51pm

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 · March 15, 2019, 12:59pm

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

Fabian

STUDENT_F · March 15, 2019, 1:00pm

Thanks a lot for that hint!

Adam_M · March 15, 2019, 1:04pm

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

anon39580149 · March 15, 2019, 1:28pm

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 · March 15, 2019, 1:30pm

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 · March 15, 2019, 1:31pm

Interesting information! Thanks a lot!

anon39580149 · March 15, 2019, 1:33pm

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 · March 15, 2019, 3:51pm

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 · March 15, 2019, 3:56pm

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

tim.stark · March 15, 2019, 4:39pm

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

STUDENT_F · March 15, 2019, 5:33pm

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)