Hi,
there are two 3D-points in a 3D point grid environment, defined as start- and endpoint. I am looking for the shortest path between start and end.
All points of the grid are in border_pts = [ … ]
Because it seams to be the easiest way, I want to use networkx module for that. I just found some code as an example from network x to apply the “A Star Shortest Path” Algorithm. Unfortunatly I only works for 2D and also not for Objects. Maybe someone can help me to modify the code for my purpose.
Hey,
I don’t know about networkx, but it looks like the method (dist) given to the a-star-algorithm computes a 2D-Distance only. U may want, if u can, just extend this calculation to the 3th dimension. Further more, u would need to add an other dimension to the Graph (again: if possible).
If u don’t care to switch from Python to C#, I could give u some advices in the usage of the plugin here. It contains some algorithms to calculate extrem paths trough a network…
On the level of pure code, the algorithms used there, are kind of independent from the (QuadEdge-)DataStructure; they just share some common interfaces…
I don’t know about networkx, but it looks like the method (dist) given to the a-star-algorithm computes a 2D-Distance only. U may want, if u can, just extend this calculation to the 3th dimension. Further more, u would need to add an other dimension to the Graph (again: if possible)
I thing is that I dont know how to extend to calculation or change the dimension of the graph, because the different ways I tried are not working at all.
I guess ‘a’ and ‘b’ are nodes. At least it looks like that each one holds a feature for each dimension.
if its 2D its ‘x’ and ‘y’
if its 3D its ‘x’ and ‘y’ and ‘z’
Depends on the naming
So, try to remove the ‘c’-stuff and add a ‘z1’ and ‘z2’ for ‘a’ and ‘b’
That works! Thanks a lot for your help!. So from now the final problem is that I have a list with point Objects. All Points objects are stored in a list called border_points.
How to add my list of points into G ( so it is about to replace the 3,3,3 grid) ?
BTW: Given the opportunity if you have any valid graph and the VV connectivity (as Matrix) and the cost from a to b is their Euclidean distance then this is a classic Dijkstra routing. There’s 2 options: from node to node … and from every node to a node. Shown the fist option.
I already know the Dijkstra Algorithm, but because of performance issues I decided for the A Star Algorithm.
The Problem is to define the Graph G in my script I posted above. May you can help how to insert a list of point objects into G? Please have an eye on my latest script picture
A proper D short route (non //, mind) takes - on an average I5 - about 5 milliseconds for 300 nodes and 900 connections (about 1-2 ms max on an I9/Ryzen). That said … well … from time to time I see posted D algos here and there that are indeed slower than any Harley Davidson :
With regard your issue: alas P is not my game … but if you want a C# solution just drop a word (but you said that it has to be P … meaning that you have plans to implement a “D-like” Method in a bigger def of yours?).
Well … I do hope that some P guy can resolve that.
BTW: D works on anything (say Meshes/Breps etc): all what you need is a Node of type Mesh/Brep and then calculate the cost as the prox Brep/Mesh distance (instead of the Point/Point distance).
BTW: This is the classic way to do a LOL D routing using Breps instead of points as nodes. Shown a (rather stupid) all to all “graph” (kinda) and a more reasonable one that is “like” a proximity graph using the GH component.
Moral: Abandon P, join the Dark Side ASAP (we have cookies for all).
I don’t know about the way this Graph is implemented, but u can use the nodes’ features for each dimension as an index to access ur data like point-coordinates or whatever u need to calculate a cost for going along a specific edge.
To do so, feed ur ‘u’, ‘v’, ‘w’ used in the nested for-loop to the creation of the Grid-Graph. Then in the def ‘dist’ use the features (should be integers) to combine them back to an index. In ur case this would be a combination of ‘u’ , ‘v’ , ‘w’…
To make this mr precise, check out ur creation of the array testgrid. The node which should associated to the features (x=0,y=0,z=0) is the same as ‘idx = u+v+w’ where (u=0, v=0, w=0) … the node-features (x=0,y=0,z=1) corresponds to (u=0,v=0,w=1) > ‘idx = u+v+w’ again…
It become tricky when u look up for a node at (x=3, y=2, z=4), which would correspond to idx=(xvw + y*v + z) (monday-morning-uncertainty, not 100% if this is right)
If u get the idx calculated the right way, u can easily access ur grid with testgrid[idx], where u get the features of the points. From this u can calculate the euclidean distance the same way as allready done…
It would be more easy, and more general for higher/lower dimensions if u try to create a nested array within the for-loop. If u do it the right way the accessing the testgrid become more easy > testgrid[xi][yi][zi]…
BESIDE:
The A-Star is exactly the same algorithm as Dijkstra’s. It adds only a heuristic to approach the goal in a faster way, but also with more error to the real optima solution.
I do not know about the heuristic used within this implementation, but I guess it could be the ‘Manhattan-Path’… This works fine if u want to calculate ur cost in an euclidean manner. If u want to use any other cost-function (dist in ur case) I would recommend to not use (this) implemenation of A-Star and swicht to pure Dijkstra, so u can be sure that u know whats going on. If there is a hidden heuristic in there, u never know whats going on. U could end up with amazingly wrong paths…
I just found some old code building up a n-dimensional matrix…
It may help to store ur data, It may make it more complicated for u to understand. I have written this code in 2013… long time ago… I do not code anymore in python…
Check out the class ‘Element’ (which is a dummy right know) to hold ur data, and the def ‘main’ at the end of file (creation and access of the matrix)
(monday-morning-uncertainty, not 100% if this is right)