"Least Cost Path" for Blender Terrains?

Support Modeling
1

Choosing a road path in real life is a science, because it costs millions :slight_smile:


Real roads usually follow a 0-6% slope (car engines don’t like big slopes, ever seen old cars & trucks on the side of the road when you’re going up into the mountains?) .
You can build a few bridges and cut some mountains but that’s terrible for our planet, and even more expensive.

I can’t believe I can’t find an easy way to do this kind of stuff with Blender!

Does someone ever seen this kind of add-on?

2

have seen something like that yet !

what you describe is more civil engineering
and that is a complex task requiring many studies and cost evaluation

so I doubt there is one addon that can do all that !

happy bl

3

Thanks @RickyBlender!
I just want walkable roads in my fantasy maps, haha!
BTW, I’m pretty sure, it’s a knowledge we have since the Roman Empire at least.
Before using Theodolite, we used something else (groma?) to make lelvel roads or with constant slopes.

After searching and scratching my head about trails and path finding, I manually made one:

path finder
path finder1286×673 465 KB

This path is 5.8% (3.3°) all the way.
It’s pretty long though.

I’m sure there’s a way to automate this but I don’t know python enough.

4

an interesting goal !

there is an addon called curve to ground
that can lay down a curve

but this won’t calculate the 3 % slope on the curve
I guess it could be done with an addon

but this should be ask in python forum or blender.stackexchange.com

let us know if you find some addon

note : it is possible such a path with slope < 3 % does not exist too!

good luck
happy bl

5

OK, will see if it raises interest: https://blender.stackexchange.com/questions/177591/python-script-to-find-a-path-around-volume-given-a-slope

6

Here’s a landscape with an empty for a village location.
Find the path to the peak!
terrain.blend (1.9 MB)

7

There are multiple details I didn’t think about:

  • “stay on this side until …”: paths are mostly built in non-rocky parts of mountains
  • branches: path can lead to various other paths (different summits, designated locations)
  • shortcuts: small shortcuts can be walked for a short distance. a shortcut branches the same path or different paths.
  • houses are near roads +> vertex group of flat areas near roads.
  • vertex group to prevent trees on roads and paths but OK to add many regular trees near paths (via domitia).

This is far beyond my script knowledge for now.

Maybe testing spiral shrinkwraps differently and going the manual way for sub-paths is easier?

8

the major constraint is your 3 % slope
skrinkwrap won’t take care of that slope !

happy bl

9

Perhaps this post could be a clue for slope finding. Or thoses well known blender users.

10

@RickyBlender, a constant slope is known for a helix (https://en.wikipedia.org/wiki/Helix, https://mathcurve.com/courbes3d/helicecirculaire/helicecirculaire.shtml),

A circular helix of radius a and slope b / a (or pitch 2 πb ) is described by the following parametrisation:

x ( t ) = a cos ⁡ ( t ) ,
y ( t ) = a sin ⁡ ( t ) ,
z ( t ) = b t

So drawing a straigth helix (spiral+z, constant slope) should works fine in theory.
But the shrinkwrap projected on X and Y produced inconsistent results in some parts.
I didn’t check in details where it failed. Maybe, these parts could be removed and a segment could be done by hand.

@skuax, thanks for the link. I didn’t know about this project. Unfortunately it’s for 2.79. I guess it uses normals angle to worldspace Z to define and increase erosion slopes. It doesn’t help in my case but I really appreciate.

EDIT: useful geometry: http://p.loussouarn.free.fr/technic/helice/helice.pdf

11

if the path has to go all around a mountain

but how do you select that shape ?

path could be on same side of the mountain then it is not a spiral!

depends also on the Total Height to climb !

not an easy problem in 3D !

happy bl

12

Yeah. Way over my level for now.
Maybe a true Ninja can push a solution forward :slight_smile:

13

to start with
you could make equi isolevel curve on your landscape
may be every 1 meter high
let say you have a total height of 10 meters
then you make 10 iso level curves

then determine if between each curve level you got less then 3 % of slope

then keep going to find a min path with slope < 3 %

not easy and time consuming for an algo

happy bl

14

if needed there is an addon for 2D map for roads and cities
to find the min path between a start and end point

so this might become useful later on
not certain if it is appropriate right now but could be

happy bl

15

there is a A* implementation I use here

you will need to adjust the cost function*

16

@ BluePrintRandom

can you elaborate what it does ?

is it applicable in 3D path ?

thanks
happy bl

17

this uses A* to map each quad as a node -> it then pathfinds and uses a cost function to decide the shortest path

in the cost function I am using linear distance + (Z-height difference *Z-height difference)

so the greater the difference in height - the more expensive the cost - leading to ‘road like paths’ that follow the least steep paths.

most of my code is already in BPY for this - I will see if I can make a lib for you.

18

he did also spec that slope cannot be more the 3%
so that is a major constraint
and I guess there is like a start and end point on the mountain or landscape

some model might not even have a min path solution too!

a bit of a challenging math problem in 3D

thanks
happy bl

19

yeah this will get the ‘flatest path’
I can also color the road by grade - so if it’s over 3% it turns red.

20

interesting
would like to test that LOL

thanks
happy bl