Challenge: Map Path generation

Given a topology and points of interest generate a set of paths such that all the regions of interest are connected

I really like Steiner Trees I think I first came across them in a Numb3rs Episode Toxin from series 2 where Charlie the erstwhile mathematician uses a few known points of interest for a criminal to try and predict a location where it might be possible to catch him which while convoluted does work in the episode. [extract from the episode](https://www.youtube.com/watch?v=w10qQgjnhHw)

I've seen the problem solved in a few ways with soap [James Grime Video](https://www.youtube.com/watch?v=dAyDi1aa40E) and various Computational ways like [this one by Zeffman on Youtube](https://www.youtube.com/watch?v=kZUWB5ZktEA) Or [This one also by Zeffman](https://www.youtube.com/watch?v=ItmLfeaGLUk) Or [This by Rasmus Fonseca](https://www.youtube.com/watch?v=bQPAqNIFVlI)

However, I've not seen a version that's more generally useable and certainly not a version that's user-friendly and has the ability to apply real-life-ness factors to it even if only in the barest most approximate ways which seems to be your speciality.

Stage 1 would simply be a Steiner Tree with nodes on a plane connect them with the minimum line length and you can add intermediate nodes to reduce the path length.

For example, connecting 3 points to their Fermat point (where ABC BCA and CAB are all less than 120 degrees) will generate the 3 nodes and a Steiner point.
While 4 nodes adds 2 Steiner Points

Stage 2 Inaccessible regions connect the nodes without a path entering a blacked out zone This gets us closer to real life by adding areas like lakes that cannot be walked on.

Stage 3 noise based terrain where a path's value is some formula combining its length, total elevation change and its steepest gradient. For simplicity, nodes get connected with arcs (circle sections) or straight lines only and N-2 Steiner points. This should model that humans make paths that avoid unnecessary elevation changed, prefer gentler gradients to a point and will try to optimise for shortest length.

Stage 4 User inputted topologies a user could input an image file perhaps with Green brightness indicating elevation, 0 being lowest elevation, 255 being highest. Red brightness indicating the difficulty, 0 being not accessible at all, 255 being no added terrain difficulty. And Blue brightness being the points of interest, in effect binary, 0 for not interesting 255 node locations. At this point, it would be simple to compare the simulated networks with the ones that exist in real life like road networks. At which point we can tweak the settings to make them more realistic.

Oh and the [Wiki page](https://en.wikipedia.org/wiki/Steiner_tree_problem)