Question for people acquainted with A* pathing algorithm. Is there a way to find straight line path throught A* algorithm?
I’ ve tried two ways.
First, I make smallest number of rectangles in straight way between start and endpoint.
Second, I tried to make grid of Y-axis line to continuous line.
please help…
Hi @jaesung.kim,
Have you tried traversing the grid cell centers instead of the edges. This should yield a straighter path.
I implemented the A* algorithm about two years ago in GHPython, but never quite finished it.
You can probably see that it doesn’t respect not crossing a diagonal between two adjacent walls. 
However, the traversed path is quite straight.
If you have a good heuristic for the weighting (euclidean distance for example) that should come out of the box see http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
Thank you for your answer. It seems impossible to find the shortest path of the minimum curve through the A* algorithm. Is there any other add-on to use in grashopper?
Shortest walk is built on the basis of A* algorithm and does not find a way to the shortest path to the minimum curve.
It seems impossible to find the shortest path of the minimum curve through the A* algorithm.
Is there any other add-on to use in grashopper?
Hello
You have 3 ways to solve your problem
Implement yourself the algorithm that is good for your problem
Find a library or another tool that can solve your problem
Change the paths in order to put more cost on turns. You can also overestimate the length of some lines.
Thank you. I looked for additional add-on but I couldn’t find them. I think we need to develop the relevant code.
I think it could work with changing a bit the network and adding big cost to the turns which can be 45 degrees lines
Or elevating say the curves that are horizontal. And connecting upper and lower curves with vertical lines. So you bring cost going up and down.
You could also look into Dijkstra’s algorithm or the Traveling Salesman problem, maybe they are a better fit?
Here’s an old thread of mine discussing the TSP in combination with a genetic algorithm. It’s written in Python and it should be rather straightforward to add more fitness values or weights, like discussed by @laurent_delrieu above.
Hello
here something thats seems to woork better.
First one the outcome you have
To have the network you’ll have to suppress vertical paths, then project all paths. And that’s all.
2D_straight_square_help_LD.gh (30.7 KB)
It is also possible to do things like that (motorway style)
On red curve horizontal length is say multiply by 2.
Genius!
Did you come with this idea by yourself?
Very cool!
So… for the 3d version of the problem, it could be used an octahedron?
Love this.
Yes it is my idea for that, but as @jaesung.kim problem is like road problem, I think at the end it is quite natural to have though of this type of solution, but it will require to feed the “L” length of the ShortestPath algorithm. And length must be the time to travel, fastest on linear portion, slower on “curves”.
GHopperGIS has A* built in you can have a look at the component that does it (look at the examples that come with the plugin), it works similarly to ShortestWalk. I haven’t worked with the plugin for some time as I have been very busy (I am the developer) but I guess it should work with the latest versions.
