24-July-2019 UPDATES highlighted in this color.
27-July-2019 UPDATES highlighted in this color.
29-July-2019 UPDATES highlighted in this color.
Short answer: yes. What should matter is what we think is best, not what others have done. A little longer answer may be: yes, but we shouldn't overdo it.
I agree it's not out of the realm of possibility, but I think this wouldn't have been done except for roads of imperial importance. Since, we can assume there wouldn't be a lot of these, we can also assume we'll be able to add some tweaks to the generation process manually (e.g. an extra low-cost connection between the two ends of the tunnel) so we wouldn't need to teach the algorithm to put tunnels in place automatically.ByteMixer wrote: ↑Tue Jul 16, 2019 5:23 amIn the case of Tamriel, and the extensive spell creation within the era of Daggerfall, I don't see why not as far as magic being used to create tunnels. Surely some mages could be able to create a spell to carve out earth. Certainly not out of the realm of possibility, but I don't know how detailed the lore goes with roads.
Don't want to quote the entire post, but I like your way of thinking. I'll get beck to this in a minute. One final quote before my own thoughts.Dalebvr wrote: ↑Tue Jul 16, 2019 1:40 pmI would think that working out the logic for the main roads to the biggest cities, getting that working right and defining the road itself would be a better approach. That is what the Empire would have built to last. Since other roadways would be different, that might be better done as a follow on. Break the villages around the cities into sectors and trickle a road from the hub city outward in each sector. That would establish the 'spoke' pattern common in older road systems, and not the grid mesh of modern transportation, where you have multiple paths to point X.
This is a suggestion we've been needing for a while now. We've been talking about a lot of things. About manually doing some things, about having a computer do some things etc. We have been talking a lot. But sooner or later, it would have broken down to: 'can we do it or not?'.CHAPPJO wrote: ↑Sat Jul 13, 2019 12:59 amSome people here seem to be proposing some quite complicated ways to try and generate the basic layout of the roads. Trading routes? I'm not a programmer, but I know a bit about some of the stuff. So I thought I'd share my idea to generate the roads. (that probably sucks)
This is obviously an imperfect solution that would need huge refinement. Either way, to me at least, it seems achievable (maybe?). The basic road layouts would be generated in advance, and would likely need to be re-generated for mods that alter the heightmap. This would all use the A* algorithm, with each ~800x800m world chunk being a node.
Finally, an answer to 'HOW?'. It might not be the best answer (I don't know), but it addresses the issue: if we ever want to have an algorithm draw any roads, we will definitely need a concrete algorithm to do it. I've studied the proposed algorithm only briefly, but it looks promising: we might find a good way to parametrize it to provide an acceptable solution to the problems at hand.
If I have not misunderstood something, it operates on graphs. In our case, the heightmap points would act as nodes and each would be linked to its neighboring points. Now, at first glance, the 800x800 seems to be low-resolution, depending on how the 800x800 figure is to be interpreted, we might need as much as 10-100 times more detail. We might be able to fix this by creating a more detailed heightmap. I am beginning to understand how the game generates heights inside the 800x800 units. A neat deterministic algorithm that yields the same results every time, thus removing the necessity to store data about every square meter of the map. With a good enough understanding (I should be there in a couple of weeks), a heightmap could be calculated in more detail (theoretically infinite detail). The bad news is that having a heightmap so detailed would take a lot of space and the algorithm would run slowly because of the increased amount of nodes.
An alternative could be to run the algorithm once on a low resolution graph and once those results are in, i.e. we have the rough route (plus or minus 400), the route in more precision, i.e. the 'exact' location - each square meter the road takes up - within the individual 800x800 tiles could be generated, deterministically by a neat algorithm, if we can come up with a suitable one (or the suitable parameters for the existing one to solve this, little different task). Come to think of it, this might be the way to avoid copious amounts of data and computational power requirements. One point seems important: we need an algorithm that can re-generate the exact location of the road/roads in the individual segments because otherwise we would need to store too much data. Another point of interest: if an algorithm is re-generating the tiles the roads take up in real-time, we might be able to also tweak in a few minor height corrections for the road tiles (to avoid some of the awkwardness jayhova pointed out in the past and can also be clearly seen in the picture in the first post). This does not seem impossible to me at this point. Will be giving some thought to this in the coming weeks.
This is the place we need to pack all the things our algorithm is to take into account. The suggestion is a good starting point, not sure I am able to add anything, but will be giving this some more thought in the coming weeks also.CHAPPJO wrote: ↑Sat Jul 13, 2019 12:59 amDifficulty to move to each different node would depend on several things;
1) Incline of slope (the higher the harder)
2) If the node is already a larger road (make it easier, intended to simulate the road joining up, then separating again), in other words, "meeting up" and temporarily joining with other larger only(?) roads. As can be seen in the following image, this smaller road from the farm joins with the larger one between the towns up to get to the destinations.
3) If the node contains a location, e.g. a tavern or home, not dungeons(?) (makes it actually take away "movement points"(or whatever the technical term is). It makes sense to make a small deviation to a resting place for travellers, does it not?). This is helpful in situations such as the one below, where it's only a small detour from sentinel to the tavern.
4) If it's water (making them impassible / making them bridges and very hard)
I will also be looking for a way to incentivize the algorithm to generate straight roads, without too many curves. Not sure to what degree this will matter, but finding a way to do it can't hurt. Have a feeling it would make some difference for the better, but not sure how to accomplish it.
Another thing is the direction of the roads: will it be just North-South, East-West? If not, how many directions to allow?
The individual categories should also be thought through (e.g. is 32, 16 suitable or we can think of better thresholds - experienced DF players should be able to judge this relatively easily).CHAPPJO wrote: ↑Sat Jul 13, 2019 12:59 amThe generation would start with large cities (>=32 blocks?), then go to smaller towns (>=16 blocks?), then down to the smallest (<16 chunks?). Any roads generated from this would be one of three qualities / sizes, this would be based of which of the previous categories of cities it would be.
After the cities it would move on to taverns, then farms, then houses, these would have even smaller and worse quality roads.
By having some data pre-generated and the details generated at run-time, this issue might be tackled. Regarding the alignment to e.g. city gates, see my thought about 'zooming-in' here and there detailed below.CHAPPJO wrote: ↑Sat Jul 13, 2019 12:59 amIssues (that I can think of):
-The big one: This is only for the vague layout, not anything at the actual game level, just the world. This could be addressed by increasing the "resolution" of nodes, e.g. having 4, 16, or even 64 in each "chunk". Even after that you would still have many issues, lining up the roads with the city gates for example.
I agree. Let's not exert any effort to avoid them. Let's see what happens.
Agree, some manual addition to the graph before running the algorithm should work around this.CHAPPJO wrote: ↑Sat Jul 13, 2019 12:59 am-In that one kingdom containing that "river", in reality a bridge would be built, this does not simulate this. You could make water chunks traversable to get around this, however you would have to limit in to large roads only, and somehow make a sectioned models of bridges to chuck together.
Let's see what happens. If we don't like it, we can still make corrections either to the algorithm or the data we feed it.
I have slept on it and I think I better understand what you mean now. The issue is: what happens if running the algorithm on the low-resolution map yields radically different results in comparison to running it on a more detailed map? This can clearly be the case for those 800x800 chunks that have a lot of height differential within. My first thought is to look for a solution where we can feed these chunks to the algorithm in more detail. Since we are operating on a graph-based algorithm, even adding some parts of the map in more detail than other parts should not be impossible.
I could also imagine an iterative process whereby the algorithm checks how much height differential is in a given segment and if the differences are too large, it 'zooms in', i.e. recalculates and adds the given sector into the graph in more detail. The zoom-in method would tackle the problem of aligning the road to exactly where they belong, like city gates.
A thought occurred to me. What if the game generated the roads via a deterministic algorithm at the same time it generates the terrain. This way the heights could indeed be adjusted to accommodate the roads.
Some points should be calculated up-front and the locations saved, perhaps in the same way and in the same format as other locations are saved. This is especially important in the case of main (longer) roads where the optimization could take longer - we don't want the loading of a new region to take forever... like in the case of a 50 km road, the location of the ends, the junctions, the points where the road crosses a territorial boundary and a point per say every 1 km could be saved along with the data about which of these points is to be connected to which other points via what kind of road. Then, during the loading of the region, the game would use the algorithm to connect these points to each other.
I don't want to write a lot now, but I am planning to contact Interkarma instead to inquire about a few technical details of how I think this could work and whether he thinks it would be possible.
(27-July-2019) Interkarma gave some good suggestions in private. I'll try to give a brief summary and then my current take on how to proceed.
The core suggestion was that deciding where to put the roads is the more difficult part of the problem and that having a good solution for this part is of no use if we don't have a good way to actually put the resulting road network into the game. So, it would be wise to first develop a way to actually flatten/smooth the tile selected to be a road and apply the appropriate texture and then continue with solving the 'where best to put the roads' problem. A good place to look would be to see how the game flattens the terrain at locations and how city ground texture tiles are set.
In short, I agree with this suggestion and will be looking into the relevant parts of the code and asking further questions where needed. I'll be aiming to figure out how to devise a method to (1) place a road tile, (2) place a continuous road from point A to point B a short distance away. Sooner or later, some good road textures will also be needed (perhaps they are already available somewhere, just need to look) - for testing purposes, any old texture will do.
I'll also be trying to get in touch with Uncanny_Valley in the upcoming days. (Needless to say: anybody else working on this, please continue your work, don't wait for me, for I cannot promise anything for certain. I will be more than happy to applaude and find something else to do.)
(29 July 2019) Got a response from Uncanny_Valley: much of the work done a long time ago is lost due to HDD failure, but did give a useful tip where to look first if we want to flatten terrain tiles.
I also made an attempt to contact hedgelord. So far, no answer, but it has only been a couple of days. I'll study some further parts of the code while I wait for a reply. Perhaps he is already 90% of the way to doing it, in which case it would be worth it to wait for the results.