I'm building a sort of city building sim and would like the ability for people to automatically place roads (or rail) based on a start and end point and for the sim to calculate the optimal route. I thought this would be relatively easy to do with normal path finding but I'm finding it challenging to deal with impassable obstacles and areas where you really wouldn't want a road/rail unless there was no other option!
See an example below - the difficult terrain might be a swamp or a park which we'd like to preserve if possible and the impassable might be really bad terrain, or something protected - for example a National Park.
I thought about using Dijkstra's algorithm but there is no real set of routes/nodes - as you can see the possible routes are quite open, same with A*. The areas covered would also be quite large so I'm trying to avoid a grid based system - I'm wondering if there is a vector based path finding algorithm? I found this https://faculty.nps.edu/ncrowe/opmpaper2.htm which creates a grid of vectors which looks halfway to what I want, but again could be quite expensive on a large area.
Any suggestions would be appreciated!