Hi,
I’m looking for a way to find the “cheapest” way to get from one point to another.
E.g.:
a.; the more bends there are in the route, the more it costs → need to minimize the bends.
b.; every inch took inside the rectangular costs 2 times more than the inches took outside the rect.
I would appreciate any thoughts and suggestions how to do this.
Thank you!
cheapest_path_Q.gh (17.4 KB)
Hi Imre
I did a quick definition
The thing you would need to define what weighs more the number of bends or the lengths inside the box
On the example they align but they wont necessarily . I added another curve to test that it works with more than just two. You can keep adding here
I would add multipliers to the two parameters you chose to drive the cost (bends, and Length inside box) to add a weight to each one and then add and sort.
cheapest_path_Q_NL.gh (11.1 KB)
Apologies, maybe I was unclear… the three paths are example paths only, but there are plenty of which I should find the best. So what I would need is an algorithm that finds the cheapest among all the different possible paths, based on weighted vertices and the number of bends.
Think of it like this: 1 inch outside the box costs 1$, 1 inch inside the box costs 2$ and each bending costs 3$. find the cheapest path between the two points (not just among this three examples)
Sure
That’s what I mean by the multiplier. The dollar value.
So if you multiply and add and then sort
You will get them sorted by price.
Grasshopper is unitless, I use millimetres in Rhino so I’m multiplying the units of length by the dollar value so its an expensive length, since it will be a dollar per millimetre. But I’m from not the USA so thankfully don’t deal in feet or inches, but the conversion should be easy.
cheapest_path_Q_NL.gh (13.5 KB)
it’s that I don’t have the paths to compare. for that I need an algorithm
Sorry
Do you want an algorithim that compares the paths…or an algorithm that makes the paths.
Cause if youre making the paths yourself i can tell you a straight line will be the best path.
When you say all the possible paths… that is literally an infite amount of paths unless you set some contraints.
I dont quite understand what you want.
one, that does it all 
an algorithm that makes the paths based on a given graph, compares them by the weights of the vertices and returns the best scoring path, which is depending on the weights, is not necessarily the shortest one.
So you want to make lets say randomized paths and then select the best ones.
With the current rules you have i can tell you with no algorithm the cheapest path is a straight line.
If you want an algorithm to make randomized paths have a stab at sketching some rules and i can try help you make the algorithm but as I say right now you can make infinite paths.
you can calculate the cheapest path if you assign weight/cost to some sort of grid of points, but if all points in a very large area do have the very same weight/cost then it’s just a matter of proximity -assuming a regular grid- using the least amount of points to get to destination
instead of generating random paths and calculating their costs, it might be easier and probably infinitely faster to have a recursive/backtracking approach
The general case (any valid Graph) has as follows:
Assuming that your Graph is “splitted” in Islands (if exist). By splitted I mean isolated sub-Graphs kinda disjoined Meshes.
Assuminig that you have a symmetric square Matrix (*) per Island where non zero value cells contain the distances of the connected Graph Nodes (i.e. Vertices)
(*) that’s called Adjacency Matrix (kind a VV Connectivity DataTree so to speak)
… then …
the classic algo to use is the A-Star (an evolution of Dikjstra’s famous old and rather slow algo).
The A-Star algo yields the min cost path given a pair of start / end Node indices … OR … all the paths from any Node index to the start Node index - for that case see the mp4 below (TextDots refer to Node indices) :
See A-Star VS a simple 2d Grid of positions:
See A-Star (parallel coding used on that) VS a 3d Graph.
It’s highly unlikely that you can do that without code. I have no idea if exists a GH add-on that does A-Star routing (that’s how the shortest path is called).
here’s what i have now:
dijkstra_mod.gh (18.7 KB)
(probably my code doesn’t look nice to say the least, i’m very very bad at coding.) it seems to work but very very slow…
I have a 2D grid and among its vertices the algorithm finds all the shortest path.
From here what I would need is to add an area, whithin the nodes have different weights than those outside, meaning that even though the lengths of the paths are equal, the values of them are different based on if the path crosses the area or not (eg.: the area is hatched on the picture below, but it could be in anywhere)
Not sure if this is clear this time appreciate your patience and help!
Hi
If you plug the paths generated on your grid to the script I made it shoud give you the cheapest one.
You could even plug the whole thins to galapagos using the pirce as the fitness criteria and let it iterate until if finds the best possible path.
I can try having a stab at it if i have time later today.
Hi Imre
So if you want to do this properly I would follow both Inno’s or Peter’s suggestions and look into graph theory, it is a similar exercise to making an optimal maze
Maze generation algorithm - Wikipedia.
I don’t have time to get into that rabitthole so I just wrote a quick script that generates a path across the grid based on three parameters that I use as genepool for Galapagos, I then set the cost as fitness and set to minimize
The issue is that with the current cost the cheapest path is obviously this
Since it has only one bend and all the length is outside the expensive area.
I would tweak the costs to see if you get something more interesting since if not it will always converge to this obvious result
cheapest_path_Q_NL_2.gh (31.0 KB)
ignore for a second the thing that you have an “inside boundary” where the points have a different weight/cost/reward:
in a standard scenario of a grid of points where all them have the very same weight/cost/reward, because there are no obstacles, the shortest distance between two points is the Manhattan distance, which is x_steps + y_steps, like in this image:
x=11, y=10 → whatever final route that had you move a total of exactly 10 times up and exactly 11 times right, in any combination, will get you from the bottom left corner to your destination point, and all of them will be equal in terms of cost (21 moves, of which 10 up and 11 right)
at this point of the conversation, we can start adding the concept of an area inside of which the costs of movement is halved
in order to get the best outcome, you want to make as many useful movements as possible inside that area, which means in the particular case shown in your picture to get from point Start to point 1, then from 1 to 2 at half the cost, and finally from 2 to destination, like this:
because of the location of the area in this particular example, you will see that the problem is just 3 identical subproblems, again solvable with Manhattan distance 
First problem: 6 right + 3 up
Second problem: 2 right + 4 up
Third problem: 3 right + 3 up
any combination of paths you can find using the above rules, will give you the shortest available path in this particular configuration
but what happens if your “half cost area” is in other positions?
for instance, because it’s randomly placed, it could also come in locations like:
in blue it’s visualized a rectangle that is equal to Manhattan distance between Start and Destination: only the points of “half cost area” that lie inside the blue rectangle will contribute to a cheaper path… and the principle is always the very same:
Start - point_1 ; point_1 → point_2 ; point_2 → Destination
it’s important here to distinguish if the associated cost of a movement has to be calculated by distance, like in the above case, or by corners -as initially stated- because the scenarios are much different
if you associate the cost of a given path exclusively to the number of corners, of course the cheapest is always A or B, because both consist of only one corner in total:
thanks for this explanation! It took some time and I’m not there yet to connect multiple points, but I made an updated algorithm, that returns all the shortest path variations between 2 point of a list through a grid’s edges and added extra weights for the edges inside the rectangular area and for each bend of the path as well. It runs very slow though 
in case anybody would be interested, here it is:
cheapest_path_Q2.gh (19.5 KB)
Hello
you could use “Shortest Walk” plugin.
cheapest path.gh (16.7 KB)
