Page 12 of 12

Re: Roads of Daggerfall

Posted: Sat Nov 30, 2019 7:48 am
by meritamas
HeinzFiction wrote:
Thu Nov 28, 2019 3:47 pm
Its in developement i think. Sorry im completely new to this forum.
Yes, in development and in the early stages, so there is nothing yet to show.
BadLuckBurt wrote:
Wed Nov 27, 2019 6:02 pm
I've sparred quite a bit with the terrain sampler and a tiny bit with the class that does terrain texturing in the wilderness. While I still have my doubts about how feasable roads are in Daggerfall, I'll do what I can to support your efforts because if you do succeed that'd be freaking awesome.
Well, I hope we can put something together because I completely agree on that last point: it really would be awesome. A fairly usable roads mod would help further some other goal of mine. Since I do not have a lot of time to spare, after reviewing the developments since September and reviewing some of my ideas, I will be concentrating my efforts on this project and hope for the best. Will get back to you in PM soon regarding the details.
meritamas wrote:
Sat Aug 10, 2019 5:51 am
12 November 2019 UPDATE: I am back now and in a couple of weeks I anticipate to be able to come back regularly and also work on this project. I got a response from hedgelord so we might be working on this together in the future.
Since the last report I have lost contact with hedgelord again, hope he'll eventually write.

Re: Roads of Daggerfall

Posted: Sat Nov 30, 2019 6:14 pm
by BadLuckBurt
meritamas wrote:
Sat Nov 30, 2019 7:48 am
Well, I hope we can put something together because I completely agree on that last point: it really would be awesome. A fairly usable roads mod would help further some other goal of mine. Since I do not have a lot of time to spare, after reviewing the developments since September and reviewing some of my ideas, I will be concentrating my efforts on this project and hope for the best. Will get back to you in PM soon regarding the details.
Sounds good. I found a few interesting articles about generating terrain:

https://www.redblobgames.com/maps/terrain-from-noise/
http://www-cs-students.stanford.edu/~am ... eneration/

Especially the second one could be of interest for roads and rivers. I'll play around with this a bit later on to see if it can be used.

Re: Roads of Daggerfall

Posted: Mon Dec 02, 2019 5:13 pm
by Jeoshua
I think one of the biggest problems in creating a realistic road network for Daggerfall is that in order to link cities in a realistic way, one must first have realistic placement of cities. Roads are built along paths, paths connect places, yes. But also places grow up along paths, and roads can make places dry up if they make passing through or around them easier than stopping by. There is not a strict order in which things are built, place or path. They come together or not at all. There aren't places people live in, in the world, without paths to them. And there aren't paths which don't lead to places, however marginal. This goes back before people, even, as one will not find a game path than doesn't lead to some place, be it a den or a watering hole, nor a location that doesn't have a path (excepting those places only flying animals frequent).

That being said, I think what I'm trying to say is that you're not looking at a one-step process to make a perfect set of roads to realistically connect places, as the existing cities you're looking at aren't realistically placed. Instead, you should focus on the idea of paths between locations, then giving each one of them a weight based on the amount of traffic expected between those nearby places, then attempting to "bend" those paths together, and at the final step taking the most traveled paths and making them roads, everything else remaining as a dirt path.

Weight of paths could be calculated based on several factors:
Population - Obvious, just use size.
Type - Cities being highest, Temples second, Dungeons third, and Graveyards fourth.
Location - People live near the coasts, so you might think there is more weight, but people there can travel on the water. So, weight between locations with a port should be reduced (not eliminated as coastal roads could still exist). Weight between coastal locations and inland ones should remain the same.
Terrain - Take a simple look at roughness and overall elevation in the height map. Higher or Rougher means worse terrain for travel.

Realistically one would worry about grade and terrain, not wanting to take roads up steep inclines, but given the nature of the terrain we are working with (very sparse), that part can be safely ignored when generating paths and instead handled when the roads are drawn on the map in later stages, warping the terrain into something that makes sense for the paths that will be there. Roads are flat but paths can be whatever, and elevation weighting already would make mountains and hills less attractive for roads.

I have also noticed a lot of talk here about rivers... Forget it! The height map as given is just simply not hydrologically correct, as I discovered in trying to use GIS tools and World Machine to automatically map out a river map. I do have a great rendition of a more in-depth height map that I have made with these tools, which uses Daggerfall's Height and Travel maps as rough inspiration for what IS a hydrologically correct map, but that's not what you're dealing with in Vanilla.

That being said, if anyone wanting to make rivers does need an eroded height map and basic river map, I am willing to provide.

Re: Roads of Daggerfall

Posted: Mon Dec 02, 2019 6:13 pm
by BadLuckBurt
Jeoshua wrote:
Mon Dec 02, 2019 5:13 pm
-snip

But I did read it all :P
The problem (and advantage) of Daggerfall's terrain is that each map pixel is 800x800 meters and as long as it's not a location (city, dungeon, temple, etc), the terrain for that map pixel is generated using noise which is fed by the large noisy heightmap in Daggerfall's data and then further interpolated by the terrain generator's code.

The simplest way I see a road generator working is to connect all the large cities per region, by keeping a list of map pixels that have roads and the directions that road travels in within the map pixel should allow for some basic road generation. When the terrain generator starts doing it's work, it can check wether the map pixel it's working on has a road, which directions it needs to go and start capping the noise accordingly.

Once something like that works, it can be expanded on for less weighty roads and paths, maybe rivers even.

Do you have any screenshots of the eroded heightmap and basic rivermap? I loaded the base heightmap into L3DT but decided I knew too little to actually turn it into a traditional heightmap.

Re: Roads of Daggerfall

Posted: Mon Dec 02, 2019 8:30 pm
by Sitrus
BadLuckBurt wrote:
Mon Dec 02, 2019 6:13 pm
Jeoshua wrote:
Mon Dec 02, 2019 5:13 pm
-snip

But I did read it all :P
The problem (and advantage) of Daggerfall's terrain is that each map pixel is 800x800 meters and as long as it's not a location (city, dungeon, temple, etc), the terrain for that map pixel is generated using noise which is fed by the large noisy heightmap in Daggerfall's data and then further interpolated by the terrain generator's code.

The simplest way I see a road generator working is to connect all the large cities per region, by keeping a list of map pixels that have roads and the directions that road travels in within the map pixel should allow for some basic road generation. When the terrain generator starts doing it's work, it can check wether the map pixel it's working on has a road, which directions it needs to go and start capping the noise accordingly.

Once something like that works, it can be expanded on for less weighty roads and paths, maybe rivers even.

Do you have any screenshots of the eroded heightmap and basic rivermap? I loaded the base heightmap into L3DT but decided I knew too little to actually turn it into a traditional heightmap.
Quick question would it be possible to process to maps city by city by using local minimas and is it possible to alter the terrain afterwards?

i.e. some pseudocode to explain a bit what I mean ( sorry that it's probably kinda unclear and this might be a dumb question).

Code: Select all

1st calculate closest cities for each city, such that if pair (a,b) exists, that won't be chosen again.
for each city a:
	for each city b:
		if dist(a,b)> local_minima and a!= local_minimas[b][0] <- make sure the pair doesn't exist
			local_minima = dist(a,b)
			local_minima_pair = b
	local_minimas[a] = [local_minima_pair , local_minima]

	
2nd start connecting each city to it's closest neighbor
for each city a in local_minimas:
	choose dist_min(city) as b:
		x,y,z = where city a gates begin
		for each tile map connecting cities
			if tile has no roads
				choose min path through tile towards destination (with curving constraints in path finding) 			
				add tile to set of tiles which have roads.
			if tile has roads
				calculate a path towards existing road & continue on it until dist to end of tile in direction such that direction change from continuing on existing road is less than some arbitrary threshold
			x,y,z = where previous road block ends
			if x,y,z == destination
				add city b to set of roads connected to city a
	
3. Iterate through every city and make sure it is connected somehow to all of its neighbors, so the graph is not cut anywhere and is a one large component

for each city a
	calculate minimum distance to each neighboring city b
		if no connecting path is found:
			iterate through tiles to find the closest tile with road that has been added using it's x,y location
				return closest tile
			if dist(closest_tile, a) > min_dist(a,b)
				connect city a to city b using previous logic
			else 
				connect city a to closest tile

Re: Roads of Daggerfall

Posted: Mon Dec 02, 2019 8:48 pm
by BadLuckBurt
Sitrus wrote:
Mon Dec 02, 2019 8:30 pm
Snipping this one as well or it's gonna be a long thread
Not sure what local minimas are but the process you describe is relatively similar to how I envision it:

1. Connect the major cities
2. The roads that connect the major cities are bound to cross each other
3. Add offshoots to the roads to connect smaller towns and do that recursively to get a branching road system

As for filling a map pixel with a road, that's probably the easiest part but the terrain should be altered as it's generated. At the very least it needs to know it's getting a road. Using a seeded function to generate roads in a map pixel should always produce the same results in the same location, the terain itself uses a similar setup.

It would probably be easiest to rip the location data from Daggerfall Unity, put that in a database so it can be queried and basically build a road generator that way. It could be adapted for other things too. It's quite a bit of work to set up, I know how to do it but I can't commit to it right now. I'll keep this in mind though, when I finish up the other stuff I'm working on I'll take a stab at it.

Re: Roads of Daggerfall

Posted: Mon Dec 02, 2019 9:35 pm
by Jeoshua
BadLuckBurt wrote:
Mon Dec 02, 2019 6:13 pm
Jeoshua wrote:
Mon Dec 02, 2019 5:13 pm
-snip

But I did read it all :P
-snip away! -

Do you have any screenshots of the eroded heightmap and basic rivermap? I loaded the base heightmap into L3DT but decided I knew too little to actually turn it into a traditional heightmap.
I still have to give it a little more work. It's highly eroded nkw, and I think I need to splice some more noise into it, the higher the map goes. So far Daggerfall province looks great, but for the flat coastal cities which sit up on a square pad lifted ~50m above the waves (more coast needed is all).

But this is out of scope for the thread. I wanted to bump this idea, not thread jack.

Re: Roads of Daggerfall

Posted: Mon Dec 02, 2019 10:17 pm
by BadLuckBurt
Jeoshua wrote:
Mon Dec 02, 2019 9:35 pm
BadLuckBurt wrote:
Mon Dec 02, 2019 6:13 pm
Jeoshua wrote:
Mon Dec 02, 2019 5:13 pm
-snip

But I did read it all :P
-snip away! -

Do you have any screenshots of the eroded heightmap and basic rivermap? I loaded the base heightmap into L3DT but decided I knew too little to actually turn it into a traditional heightmap.
I still have to give it a little more work. It's highly eroded nkw, and I think I need to splice some more noise into it, the higher the map goes. So far Daggerfall province looks great, but for the flat coastal cities which sit up on a square pad lifted ~50m above the waves (more coast needed is all).

But this is out of scope for the thread. I wanted to bump this idea, not thread jack.
No rush, I was just curious. Looking forward to seeing it when you're ready. And to stay on topic, a regular heightmap instead of classic Daggerfall's would allow for some really nice roads.

Re: Roads of Daggerfall

Posted: Wed Dec 04, 2019 12:55 pm
by Sitrus
BadLuckBurt wrote:
Mon Dec 02, 2019 8:48 pm
Sitrus wrote:
Mon Dec 02, 2019 8:30 pm
Snipping this one as well or it's gonna be a long thread
Not sure what local minimas are but the process you describe is relatively similar to how I envision it:

1. Connect the major cities
2. The roads that connect the major cities are bound to cross each other
3. Add offshoots to the roads to connect smaller towns and do that recursively to get a branching road system

As for filling a map pixel with a road, that's probably the easiest part but the terrain should be altered as it's generated. At the very least it needs to know it's getting a road. Using a seeded function to generate roads in a map pixel should always produce the same results in the same location, the terain itself uses a similar setup.

It would probably be easiest to rip the location data from Daggerfall Unity, put that in a database so it can be queried and basically build a road generator that way. It could be adapted for other things too. It's quite a bit of work to set up, I know how to do it but I can't commit to it right now. I'll keep this in mind though, when I finish up the other stuff I'm working on I'll take a stab at it.
Local minima is in this the closest neighbor, i.e. connect first only cities that are closest to each other. It makes the roads make more sense and drops the amount of computation required. It should also drop the level of error for making nonsensical roads trying to cross the sea or lakes.

I think the terrain could just be smoothed. if you know the path that is calculated, just smooth the area based on the left and right heights of the road. If there's a slope, you just start iterating from one side at height n by n-1 until you reach the othersides height. if they're on the same plane or similar planes, smooth them to the same level. I would start with this and see what it does, then start calculating a slope of the sides by a logaritmic curve or sth else. Then smooth out the path forward using a peek forward (so you peek to see the height of the map for the next 10 meters, to decide do you start to make the road rise or go lower).

I have some time for this if you need help, I can mostly stab at it in C++/C or Python if that is any help. I understand the terrain generation can be altered? Is there a guide for that, I think I could whip up a proof of concept for the algorithm quite quick actually if it's relatively simple to setup.

*Edit*

I just realised this after posting, but for the traffic generation to decide the size of the road. I don't think that's a good idea to try and aim for immediately, first handle the path finding and get that working to some degree. After that it would be easier to start working on the traffic, most likely by assigning a weight based on the classification of the city. I.e. if it's a capital or an actual town, assign a higher weight. Weight determines the width and material of the road.

Re: Roads of Daggerfall

Posted: Wed Dec 04, 2019 2:11 pm
by BadLuckBurt
Sitrus wrote:
Wed Dec 04, 2019 12:55 pm
Local minima is in this the closest neighbor, i.e. connect first only cities that are closest to each other. It makes the roads make more sense and drops the amount of computation required. It should also drop the level of error for making nonsensical roads trying to cross the sea or lakes.

I think the terrain could just be smoothed. if you know the path that is calculated, just smooth the area based on the left and right heights of the road. If there's a slope, you just start iterating from one side at height n by n-1 until you reach the othersides height. if they're on the same plane or similar planes, smooth them to the same level. I would start with this and see what it does, then start calculating a slope of the sides by a logaritmic curve or sth else. Then smooth out the path forward using a peek forward (so you peek to see the height of the map for the next 10 meters, to decide do you start to make the road rise or go lower).

I have some time for this if you need help, I can mostly stab at it in C++/C or Python if that is any help. I understand the terrain generation can be altered? Is there a guide for that, I think I could whip up a proof of concept for the algorithm quite quick actually if it's relatively simple to setup.

*Edit*

I just realised this after posting, but for the traffic generation to decide the size of the road. I don't think that's a good idea to try and aim for immediately, first handle the path finding and get that working to some degree. After that it would be easier to start working on the traffic, most likely by assigning a weight based on the classification of the city. I.e. if it's a capital or an actual town, assign a higher weight. Weight determines the width and material of the road.
I'm still pretty new to this and in the middle of reworking the terrain sampler while learning a lot in the process. The way you describe it, it'd be a pass after the terrain for the map pixel has been generated. What I had in mind would try to integrate it into the generation process.

Some background information about the terrain generation:

Each map pixel is 800x800 meters
128x128 samples are generated to create the random terrain
This makes each sample 6.25x6.25 meters

Using a list of sample coordinates that will be used for road, it should be possible to flatten out terrain for roads while also allowing some sloping to occur on the edges. The road weight would determine if it's 1, 2, 3 or however many tiles wide.

This way, it's generated in one go, later on when terrain texturing is done, it can just refer to the list of sample coordinates to determine if it's a road or not.

If you setup Unity and download the DFU github repo, you can play around with the default terrain sampler and see how it works. I can probably answer most questions you have about it. DFU and Unity use C# so you shouldn't have much of an issue coming to grips with it, I've never coded any C# before I got dragged into this.

I agree with starting simple but connecting the main cities in a region (or in a smaller controlled area) seems a better starting point to me but the approach is still the same.