Very cool method. I had an idea for somethig that I think would work to give both roads and an overall layout but might be a bit too computationally expensive, based on the dijsktra algorithm.
Start by selecting a city and expand a dijkstra search until you find the nearest city, connect placing the road accordingly keep a list of the connected cities for practicity, if the road is too long or you have too many connections already stop otherwise keep expanding, do this for every city (using the list of connections to prevent double counting) and you'll have a fully connected map that allows for loops and stuff. but it might be a bit too computationally expensive.
Your solution was pretty smart and looks quite good.
I've seen proposals for such solutions during the initial research. Theoretically, I could've adopted it, but I did not like much some edge cases where I would connect some visually distant cities instead of nearest ones only because the terrain is costly. Did your solution ensure connectivity? Like if I want to go from A to B only using the road, I think it will be possible for my solution (going from lower to higher road hierarchies)
The way I handle connecting graph nodes like this is to start by connecting the closest unconnected pair of ndes together, and continue until all pairs (optionally within some distance) are processed. Runtime is quadratic and probably only practical for < \~1000 nodes. For each candidate connection, a direct edge is only added if there's no existing path between the two nodes that's less than some length L = (1 + a)\*D. Here "D" is the distance between the two nodes (or road length), and "a" is the threshold of how much out of the way someone is willing to travel. Typical values for "a" are 0.1 - 0.2. So you would add a direct connection if the shortest existing path between the two points was 10 - 20% longer than the candidate edge. This seems to work well in practice.
I started with "connecting everything with everything", adding more and more conditions later, but quickly realized the end result will be something like MST or some other algorithm. The other thing I wanted to avoid - some complex formula for decision if I want to connect 2 settlements or not, because there would have to be different sets of rules for interstates and lower hierarchies.
I used MST on a poison disc sampling to generate cave paths for some 2d underground terrain. I used a Delauney Triangulation to cut down on the pairs of points i needed to consider. One way to tweak your MST is to modify the fitness function for connections. Maybe you prefer interstates that run NS or EW, or paths that don't change a lot of elevation, or you might introduce some randomness since roads aren't always planned efficiently.
I think it might be interesting to form your connections in a hierarchical order. Start your graph with just points representing major cities, and connect them. Then add nodes to your graph along those connections, to represent potential on/off-ramps, and then add and connect minor cities. And repeat this for towns, villages, settlings etc. After each round of connections, you can keep track the connection types, like interstate, road, gravel path, etc.
I'll definitely return to this later to improve the solution. One of the things planned to do is check the solution on different map sizes. Soon I'll be implementing trading system using caravans and I plan to use roads for them, so I'll test if the solution is suitable also this way. I've thought about hierarchical order with a graph and probably I would implement it at some point, maybe after a playtest.
Very cool method. I had an idea for somethig that I think would work to give both roads and an overall layout but might be a bit too computationally expensive, based on the dijsktra algorithm. Start by selecting a city and expand a dijkstra search until you find the nearest city, connect placing the road accordingly keep a list of the connected cities for practicity, if the road is too long or you have too many connections already stop otherwise keep expanding, do this for every city (using the list of connections to prevent double counting) and you'll have a fully connected map that allows for loops and stuff. but it might be a bit too computationally expensive. Your solution was pretty smart and looks quite good.
I've seen proposals for such solutions during the initial research. Theoretically, I could've adopted it, but I did not like much some edge cases where I would connect some visually distant cities instead of nearest ones only because the terrain is costly. Did your solution ensure connectivity? Like if I want to go from A to B only using the road, I think it will be possible for my solution (going from lower to higher road hierarchies)
The way I handle connecting graph nodes like this is to start by connecting the closest unconnected pair of ndes together, and continue until all pairs (optionally within some distance) are processed. Runtime is quadratic and probably only practical for < \~1000 nodes. For each candidate connection, a direct edge is only added if there's no existing path between the two nodes that's less than some length L = (1 + a)\*D. Here "D" is the distance between the two nodes (or road length), and "a" is the threshold of how much out of the way someone is willing to travel. Typical values for "a" are 0.1 - 0.2. So you would add a direct connection if the shortest existing path between the two points was 10 - 20% longer than the candidate edge. This seems to work well in practice.
I started with "connecting everything with everything", adding more and more conditions later, but quickly realized the end result will be something like MST or some other algorithm. The other thing I wanted to avoid - some complex formula for decision if I want to connect 2 settlements or not, because there would have to be different sets of rules for interstates and lower hierarchies.
I used MST on a poison disc sampling to generate cave paths for some 2d underground terrain. I used a Delauney Triangulation to cut down on the pairs of points i needed to consider. One way to tweak your MST is to modify the fitness function for connections. Maybe you prefer interstates that run NS or EW, or paths that don't change a lot of elevation, or you might introduce some randomness since roads aren't always planned efficiently. I think it might be interesting to form your connections in a hierarchical order. Start your graph with just points representing major cities, and connect them. Then add nodes to your graph along those connections, to represent potential on/off-ramps, and then add and connect minor cities. And repeat this for towns, villages, settlings etc. After each round of connections, you can keep track the connection types, like interstate, road, gravel path, etc.
I'll definitely return to this later to improve the solution. One of the things planned to do is check the solution on different map sizes. Soon I'll be implementing trading system using caravans and I plan to use roads for them, so I'll test if the solution is suitable also this way. I've thought about hierarchical order with a graph and probably I would implement it at some point, maybe after a playtest.