Roads of Daggerfall

Show off your mod creations or just a work in progress.
hurleybird
Posts: 8
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: 382
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?'.
Windows 10 Pro 64 bit. DFU Ver. 0.7.120

Narf the Mouse
Posts: 743
Joined: Mon Nov 30, 2015 6:32 pm

Re: Roads of Daggerfall

Post by Narf the Mouse » Fri Mar 29, 2019 1:32 am

Perhaps A* pathfinding for building roads, with the cost taking into account both distance and the square of elevation change?
Previous experience tells me it's very easy to misunderstand the tone, intent, or meaning of what I've posted. If you have questions, ask.

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

Re: Roads of Daggerfall

Post by jayhova » Sun Mar 31, 2019 12:10 am

Narf the Mouse wrote:
Fri Mar 29, 2019 1:32 am
Perhaps A* pathfinding for building roads, with the cost taking into account both distance and the square of elevation change?
jayhova wrote:
Tue Nov 27, 2018 12:13 am

in my research on the subject, I found this book https://books.google.com/books?id=f9DNAAAAMAAJ
Generally you don't want to make a road with a rise of more than 1' for every 30' (1.9°) and less than that if you can manage it. You can have a short rise that is reasonably steep if it is short and if having that saves you a much longer route. Roads will need a thing much like cities where the ground is leveled, trees etc. removed. Perhaps they could be placed like buildings but tiled one after the other. Roads themselves are not flat across but peaked in the middle to get water to run off and raised above grade to keep from flooding.

If you want to factor road cost into the equation you could start with a basic gravel road having a cost of 1 per linear mile. For a broken stone road the cost would double to 2. For a cobbled highway the cost would be 4. The cost to build on a hillside would add 4 at 45 degrees incline representing the excavation cost. This cost would go up or down for a greater or lesser incline.

Each population center gets points to spend based on the number of people let's say .1 per person so a village of 100 people could build a 10 mile gravel road. A city of 10,000 could build one thousand miles of gravel road, 500 miles of stone road, 250 miles of highway. They would likely concentrate building toward another population center. That population center would share the cost.

Each population center will spend points to gain commerce. Let's say that roads net commerce in the same way people equate road building points. Where the goal of a city is to maximize the commerce. Better roads increase commerce from a connected city. A gravel road gives 1 commerce point per 10 people a broken stone 2 and a highway 3. The population centers divide up these points based on the number of road building points they spent.

You can think of this as cost from available tax revenue and incentive from commerce to connect to population centers. If a small village is on the way to a large town there may be a significant incentive to take the highway to that town. However it may be more commercially viable to build a straighter road to the larger place and a gravel road to the village. This might create a road that spits off and then rejoins the highway later on or simply cuts at a convenient angle to the village.
Remember always 'What would Julian Do?'.
Windows 10 Pro 64 bit. DFU Ver. 0.7.120

hurleybird
Posts: 8
Joined: Mon Dec 10, 2018 12:00 am

Re: Roads of Daggerfall

Post by hurleybird » Tue Apr 02, 2019 6:50 am

Narf the Mouse wrote:
Fri Mar 29, 2019 1:32 am
Perhaps A* pathfinding for building roads, with the cost taking into account both distance and the square of elevation change?
That might be the best way to do it, actually. And of course you can tweak cost for each unit area after the fact to take into account things like population density. But you'd would start simple and build from there.

Here's an idea for an implementation:

Iterate through every city, and A* to every other city within some specific radius, closer neighbours first. Start with a rather small radius and do the whole process several times, each time increasing the size of the radius.

The key to this is that you give existing roads a zero, or at least near-zero cost. So in this way, when the radius is larger the algorithm is extremely unlikely to create paths to far away places, but will see that existing roads suffice. This approach should also allow for the organic formation of intersections, since the A* from one city to another might find that it's more optimal to intersect with an existing road rather than going straight to the city in question.

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

Re: Roads of Daggerfall

Post by jayhova » Wed Apr 10, 2019 7:15 am

hurleybird wrote:
Tue Apr 02, 2019 6:50 am

That might be the best way to do it, actually. And of course you can tweak cost for each unit area after the fact to take into account things like population density. But you'd would start simple and build from there.

Here's an idea for an implementation:

Iterate through every city, and A* to every other city within some specific radius, closer neighbours first. Start with a rather small radius and do the whole process several times, each time increasing the size of the radius.

The key to this is that you give existing roads a zero, or at least near-zero cost. So in this way, when the radius is larger the algorithm is extremely unlikely to create paths to far away places, but will see that existing roads suffice. This approach should also allow for the organic formation of intersections, since the A* from one city to another might find that it's more optimal to intersect with an existing road rather than going straight to the city in question.
I don't think you need to do anything with radius. If you are a city or town in the middle of nowhere you will have a road going somewhere even if that somewhere is another road. That's rule one, every city, town, home has at least one road going somewhere. Okay, Let's now start with the largest population center in a region. You can next path an arbitrary number of paths, let's say 6, to the closest population centers, starting at the closest. This will allow you to branch paths to further places from existing paths. Think of this as roads that have been surveyed. Next, you do a cost/benefit analysis on each potential road. Let's say you build 6 roads. Start with gravel roads which provide a 50% return on investment.

Now, let's say you look at the length of the road in linear miles vs the population being connected to. In this example we will assume that 5 of the towns each have a population of 1000 and the total road to reach them is 100 miles but the last has a population of 10,000 and takes 200 miles of road to reach. At this point you can look at how many miles of road the 10k city will invest to reach you. Do this and subtract that number from the total to be invested in building the road. Now you have some roads you can then look at improving them. We have already calculated the linear miles of road your city is responsible for maintaining, We now do the same cost/benefit analysis on an improved road. Let's assume an improved road nets you 75% return on investment. Since an improved road is twice the cost of a gravel road and only gains you an additional 25% return this may or may not be worth the investment. If yes the road is improved. If benefit of improving a road is zero or less that road is not improved. If there is a higher cost/benefit connecting a new road to a new location that is done instead.

After an arbitrary number of road segments have been created, let's say 12, you move to the next major city and repeat the process. lather rinse repeat. After you have gone through all the major cities you cycle back to the first and continue. Remember that any place that has a road connected to it incurs the cost and/or benefit of that road and that road is subtracted from any initial roads to be built. If a place is already connected to 2 other places the number of initial paths to create is 4 and not 6; the cost to build those roads having already been deducted.
Remember always 'What would Julian Do?'.
Windows 10 Pro 64 bit. DFU Ver. 0.7.120

hurleybird
Posts: 8
Joined: Mon Dec 10, 2018 12:00 am

Re: Roads of Daggerfall

Post by hurleybird » Wed Apr 10, 2019 7:31 pm

Out of curiosity, are you a developer? There's a big difference between saying what you want to happen versus showing how to do it.

The point of my last example is that it does let roads lead to other roads instead of cities, and also avoids edge cases.

In contrast:
Okay, Let's now start with the largest population center in a region. You can next path an arbitrary number of paths, let's say 6, to the closest population centers, starting at the closest.
Is naive and will fail many edge cases. Imagine a group of six cities more or less in a line. Start at a city on one end of the line. Now you have six basically parallel paths, which isn't what you want.
This will allow you to branch paths to further places from existing paths.
...How exactly? Nothing you've said describes this.

User avatar
King of Worms
Posts: 1509
Joined: Mon Oct 17, 2016 11:18 pm
Location: Scourg Barrow
Contact:

Re: Roads of Daggerfall

Post by King of Worms » Wed Apr 10, 2019 9:41 pm

Guys, too much theory, too little roads :D
That being said, I like hurleybirds implementation and base attributes layed down at the space map post

hurleybird
Posts: 8
Joined: Mon Dec 10, 2018 12:00 am

Re: Roads of Daggerfall

Post by hurleybird » Wed Apr 10, 2019 10:01 pm

Thanks, although I actually think that the expanding A* idea is more promising since it doesn't require a second step (how to place the roads after determining which cities get roads) and should be very organic.

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

Re: Roads of Daggerfall

Post by jayhova » Fri Apr 12, 2019 6:53 pm

hurleybird wrote:
Wed Apr 10, 2019 7:31 pm
Out of curiosity, are you a developer? There's a big difference between saying what you want to happen versus showing how to do it.

The point of my last example is that it does let roads lead to other roads instead of cities, and also avoids edge cases.

In contrast:
Okay, Let's now start with the largest population center in a region. You can next path an arbitrary number of paths, let's say 6, to the closest population centers, starting at the closest.
Is naive and will fail many edge cases. Imagine a group of six cities more or less in a line. Start at a city on one end of the line. Now you have six basically parallel paths, which isn't what you want.
This will allow you to branch paths to further places from existing paths.
...How exactly? Nothing you've said describes this.
I'm not a developer. I'm a guy who has read a bit on ancient roads and how and why they were built. People don't build roads to reach other roads, they build roads to reach places. However, sometimes it is easier to reach those places by connecting to an existing road. The first road people build does not intersect another road generally speaking. Roads do not spring up all at once in a planned fashion (except in rare instances). Roads must be paid for. Any population center will attempt to build the least amount of road for the greatest benefit. Roads in the ancient world did not get built straight through hilly terrain.

I think if you examine how I have laid out my suggestions you will see that there is little danger of the roads being built in a non-realistic way. To help I will explain my reasoning.

First, why do I suggest starting with the largest population centers? Because these are the places with the most commerce and hence the most need for and ability to build roads. Would anyone build or improve upon a road that did not most efficiently promote commerce? No. As it happens having a road with even moderately steep inclines can multiply the effort needed to move along that road. This is why roads wind around hills rather than going over them.

Second, I suggest laying out the roads first because pathing can possibly change based on how the roads lay out. A city is unlikely to spend extra money on a road that does not pay for itself. Perhaps a single road leading out and then forking would be a better choice. Just bear in mind that the best roads will always be those that have the greatest commercial or military value.

To answer your question of branched paths you must bear in mind that a city will not pay for an expensive road they do not need. Since you build a road to the closest place first (as is likely to happen in real life), it should be relatively simple to path to the next population center using the smallest amount of additional road. Here is where it gets tricky. If you path to your second place and that place is significantly bigger there may be enough economic incentive to repath to make the second road as short as possible. If we talk about these things growing organically then you have to grow them as organisms would.

So as I said, people don't build roads to roads, people build roads to places. Lets assume you start out with settlements and no roads. This is a pretty safe assumption. People then move between settlements because trading goods and services tends to prevent starvation and people are highly motivated to do this. People tend not to journey too far because there are no roads. So what you have are paths leading to each place. The most established paths are to the best places commerce wise. Now, as you so wisely pointed out, they are unlikely to build roads on parallel paths. But, they will likely build roads on existing trails.

When the roads get built, they are less organic than the original paths because there is a cost involved, whereas moving along a dirt path imposes no real cost. Remember, if there are no roads, moving directly to your destination is the easiest way to get there, if it is within a day's travel and always if you are camping out. Roads change this by making traveling significantly easier and faster. This creates a counter intuitive condition where a longer route along a road is faster, easier and safer than the more direct route. Roads will be constructed in a manner that brings the best return on investment. The equation for this is (number of people connected/length of the connection)* quality of the road. This equation should pretty accurately predict the value of a road. I should point out that roads that connect to ports are significantly more valuable because water is a road that connects to every port it touches. If you construct an algorithm that maximizes the value of each road segment you will have a pretty accurate view of how they would be laid out in real life.
Remember always 'What would Julian Do?'.
Windows 10 Pro 64 bit. DFU Ver. 0.7.120

Post Reply