Roads of Daggerfall

Show off your mod creations or just a work in progress.
hurleybird
Posts: 5
Joined: Mon Dec 10, 2018 12:00 am

Re: Roads of Daggerfall

Post by hurleybird » Wed Mar 13, 2019 6:43 pm

I think in terms of procedural generation you're dealing with two issues... where to place roads and how to place roads. In other words "I want a road between A and B" versus "The road between A and B should curve around these mountainous regions.

Only the second problem seems difficult, but it also feels like a problem that can be done incrementally, starting with straight lines and working up from there.

The first problem seems pretty easy. Voronoi/Delaunay was mentioned. I'm not sure if the OP is still looking for ideas here, but I've more or less implemented a Delaunay-esque system (eg. not true Delauny, but looks pretty much identical) for my own project (a 4X game with optional starlanes). It's possible and even likely that there are better solutions, but I may as well share my implementation if it might be able to help.

Psuedocode:
  • Create an edge between every vertex and every other vertex. Store this in a list which we'll call edgeList.
  • Sort edgeList based on the length of each edge, in ascending order.
  • Create a list of edges which we'll refer to as acceptedEdges.
  • Iterate through edgeList, and in the case that an edge does not intersect with any edge in the acceptedEdges list, then add that edge to acceptedEdges. (For something like daggerfall though, I'd suggest keeping a small percentage of the intersecting edges to create the occasional intersection.)
  • From this point on, when talking about edges in the context of a collection we're referring to acceptedEdges, not edgeList.
  • Remove all edges that are greater than a certain distance. (In my game this can result in gaps in the starlane network, but fleets can travel outside of the network, just very slowly, and far away clusters of stars get connected via wormholes anyway. If everything must be connected regardless of distance, skip this.)
  • Iterate through edges. We'll call the current target of this iteration queriedEdge.
  • If we satisfy a random roll (I use a 25% chance) and the condition that the first vertex of queriedEdge can reach the second (using other edges that are not queriedEdge) in x (I use 3) or less hops where each individual edge length in that path (multiplied by some constant, I use 1.125) is shorter than the length of queriedEdge, then remove queriedEdge. (You can probably skip this step, at least to start. For my own game this helps encourage certain interesting and aesthetically pleasing geometry. In the image below you can see how this helps to create a few more ring-like shapes.)
  • Iterate through vertices. We'll call the current target of this iteration middleVertex.
  • For each iteration, get all edges that contain middleVertex and store these in a list, sorted by descending length. We'll call it vertexEdges.
  • Then still inside the original iteration, iterate through vertexEdges. We'll call the current target of the iteration edgeA.
  • And inside that iteration, iterate through vertexEdges again. We'll call the current target of this iteration edgeB.
  • If edgeA== edgeB, then continue.
  • Otherwise, Find the vertex in edgeA that is not middleVertex, which we'll call it startVertex.
  • Do the same for edgeB. We'll call it endVertex.
  • Find the angle between edgeA and edgeB. In Unity, this should look like:
    Vector2.angle (middleVertex.position - startVertex.position, middleVertex.position - endVertex.position)
  • If the angle is greater than some threshold, then remove edgeA. This prevents some funny and unflattering shapes endemic to ultra acute edge angles. (This shouldn't result in any gaps in the edge network if the threshold is under 45 degrees. I use 36.67)
  • After we've iterated through every vertex, that's it. We should now have a valid set of edges that can be used for roads, or whatever.

An implementation of the above, using the values listed, looks like:

Image
(The squiggly line up top is a wormhole, inactive for 23 more turns, not a starlane.)


By changing the value of the various constants you can get a decent amount of variety. No idea how much this may or may not help, but if you're looking just to get you started, you can try something this like this combined with straight roads, plus a check to make sure that roads don't intersect water, and then iterate from there.
Last edited by hurleybird on Thu Mar 14, 2019 4:04 am, edited 12 times in total.

User avatar
jayhova
Posts: 219
Joined: Wed Jul 19, 2017 7:54 pm
Contact:

Re: Roads of Daggerfall

Post by jayhova » Wed Mar 13, 2019 9:13 pm

I was thinking about this and the procedures that would come about in real life to construct roads. The first roads are between points of the greatest commerce. This means that 2 large population centers that are near each other will first have a worn path and then an improved road constructed on top of that path. There may come an intermediate step of a gravel road. These shortest of roads become building blocks for other roads.

Roads follow certain guidelines among these are they avoid steep inclines that have a increasing detriment on animal traffic; In particular carts carrying goods. An example of this could be you have a road that must go over or around a hill. Going over looks like the best solution because it seems like a straight line but in fact the line curves in the vertical. Now let's say by going straight over the hill your path is 1/3 shorter. This now seems like a good trade-off. However now you must account for the horse drawn wagon that must slow down to deal with both the rise and fall in elevation. At this point the travel time savings may be minimum. Now on top of that the effect on a horse in that situation is that the horse was forced to exert much more effort and hence has a significantly increased fatigue level and so will be required to stop sooner. A road that exhausts the traveler before they can complete that leg of their journey does not have a great deal of value. So we are left with the equation of shortest length of road with an acceptable rise. Sometimes it will be better to connect to your destination via other nodes
Remember always 'What would Julian Do?'.

Post Reply