# Cheapest path

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)

1 Like

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)

1 Like

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).

3 Likes

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

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)

1 Like

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:

2 Likes

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.

The only trick ist to make extra curves at each intersection and give a weight depending on the curvature. Here I used length of curve but it could be better to join curves with arc or blend and measure the angle between tangent at start and tangent at end.

cheapest path.gh (16.7 KB)

2 Likes