Roads of Daggerfall

Show off your mod creations or just a work in progress.
Post Reply
User avatar
Uncanny_Valley
Posts: 221
Joined: Mon Mar 23, 2015 5:47 pm

Re: Roads of Daggerfall

Post by Uncanny_Valley »

An algorithm you say? Hmm..

"Doing a quick google search"

Fortunes's algorithm:

Code: Select all

let *(z) be the transformation *(z)=(z_x,z_y+d(z)),
  where d(z) is the Euclidean distance between z and the nearest site
let T be the "beach line"
let R_p be the region covered by site p.
let C_{pq} be the boundary ray between sites p and q.
let p_1,p_2,...,p_m be the sites with minimal y-coordinate, ordered by x-coordinate
Q \gets S - {p_1,p_2,...,p_m}
create initial vertical boundary rays C_{p_1,p_2}^0,C_{p_2,p_3}^0,...C_{p_{m-1},p_m}^0
T \gets *(R_{p_1}),C_{p_1,p_2}^0,*(R_{p_2}),C_{p_2,p_3}^0,...,*(R_{p_{m-1}}),C_{p_{m-1},p_m}^0,*(R_{p_m})
while not IsEmpty(Q) do
    p ← DeleteMin(Q)
    case p of
    p is a site in *(V):
        find the occurrence of a region *(R_q) in T containing p,
          bracketed by C_{rq} on the left and C_{qs} on the right
        create new boundary rays C_{pq}^- and C_{pq}^+ with bases p
        replace *(R_q) with *(R_q),C_{pq}^-,*(R_p),C_{pq}^+,*(R_q) in T
        delete from Q any intersection between C_{rq} and C_{qs}
        insert into Q any intersection between C_{rq} and C_{pq}^-
        insert into Q any intersection between C_{pq}^+ and C_{qs}
    p is a Voronoi vertex in *(V):
        let p be the intersection of C_{qr} on the left and C_{rs} on the right
        let C_{uq} be the left neighbor of C_{qr} and
          let C_{sv} be the right neighbor of C_{rs} in T
        create a new boundary ray C_{qs}^0 if q_y = s_y,
          or create C_{qs}^+ if p is right of the higher of q and s,
          otherwise create C_{qs}^-
        replace C_{qr},*(R_r),C_{rs} with newly created C_{qs} in T
        delete from Q any intersection between C_{uq} and C_{qr}
        delete from Q any intersection between C_{rs} and C_{sv}
        insert into Q any intersection between C_{uq} and C_{qs}
        insert into Q any intersection between C_{qs} and C_{sv}
        record p as the summit of C_{qr} and C_{rs} and the base of C_{qs}
        output the boundary segments C_{qr} and C_{rs}
    endcase
endwhile
output the remaining boundary rays in T
:shock: :shock: :shock: :shock: (My head hurts)

May need to read up on it a bit further... or maybe I can just find a way to harness the awesome power of slime mold ;)

Having both cobblestone and dirt roads is part of the plan, but dirt roads will probably be added later. When working on the editor I also thought about rivers, and is definitely something that can be added using the same method. I plan to look into it after I finished the road part.
I like your idea ifkopifko, having sections of more dense forests and clearings would be really nice. The editor that I made could definitely be re purposed to be able to create a new type of landscape map that can be used to determine billboard placement.
For now, I plan is to add the roads manually using the editor, but try to make the process as easy as possible. And if any step of the process can be automated, it will.

And thank your for your help Interkarma. :)

User avatar
Nystul
Posts: 1501
Joined: Mon Mar 23, 2015 8:31 am

Re: Roads of Daggerfall

Post by Nystul »

ifkopifko wrote: Why I'm asking... I have a dream... :D Nah... I thought that the look of the land could be changed/improved by reorganizing the trees/rocks/somethings. You know, like creating dense forests and clearings. Just like in the real world. If one could edit this kind of stuff graphically, in a form of a map, I think it might actually be manageable even on the scale of DaggerFall game world. Most of the roads could actually be composed of treeless terrain, rather than a stone/mud texture... though some texture would be nice between the largest cities.
the forest stuff is something I planned for the IncreasedTerrainDistance mod in the ImprovedWorldTerrain.cs script in the future. I would like to generate a "tree/forest" density map automatically and use it in the shader for the world terrain. It would be necessary to make the near terrain read from this map as well for nature flat generation to make it look reasonable ;)
I am just not sure how to do it right, of course tree density will depend on altitude, but what other factors should be taken into account is something that needs to be worked out...

Uncanny_Valley wrote: I like your idea ifkopifko, having sections of more dense forests and clearings would be really nice.
This is exactly what I want to achieve

User avatar
Hoon
Posts: 11
Joined: Thu May 14, 2015 5:49 am

Re: Roads of Daggerfall

Post by Hoon »

For rivers it might be more beneficial to reference a heightmap rather than a regional map; and if rivers actually have a "flow" to them, that would have to be accounted for. And yeah, I don't see a way for rivers to cut through settlements without weirdness, but just putting rivers near settlements should be sufficient.

User avatar
Interkarma
Posts: 7236
Joined: Sun Mar 22, 2015 1:51 am

Re: Roads of Daggerfall

Post by Interkarma »

Uncanny_Valley, I posted this example code in another thread. It might also be a good help for you to get at that DFLocation data and get started with the coordinate conversions.

Code: Select all

int testMapPixelX = 207;    // 207,213 is Daggerfall, 859,244 is Wayrest, 397,343 is Sentinel
int testMapPixelY = 213;
Utility.ContentReader.MapSummary summary;
if (DaggerfallUnity.Instance.ContentReader.HasLocation(testMapPixelX, testMapPixelY, out summary))
{
    DFLocation location = DaggerfallUnity.Instance.ContentReader.MapFileReader.GetLocation(summary.RegionIndex, summary.MapIndex);
    if (location.Loaded)
    {
        // Output location and region name
        Debug.Log(string.Format("Location found is {0} in the region {1}.", location.Name, location.RegionName));

        // Derive longitude and latitude from map pixel coords
        DFPosition ll = MapsFile.MapPixelToLongitudeLatitude(testMapPixelX, testMapPixelY);

        // Calculated longitude and latitude should equal that stored in game data
        if (ll.X == location.MapTableData.Longitude && ll.Y == location.MapTableData.Latitude)
            Debug.Log("Longitude and latitude are a match.");

        // Derive unique map ID from longitude and latitude
        int id = MapsFile.GetMapPixelIDFromLongitudeLatitude(ll.X, ll.Y);

        // MapTableData.MapId & 0x000fffff should equal calculated id
        if (id == (location.MapTableData.MapId & 0x000fffff))
            Debug.Log("Map ID is a match.");
    }
}

User avatar
Interkarma
Posts: 7236
Joined: Sun Mar 22, 2015 1:51 am

Re: Roads of Daggerfall

Post by Interkarma »

Uncanny_Valley wrote: :shock: :shock: :shock: :shock: (My head hurts)
Haha my head hurts from that as well. :D I'm a serious math dunce and it takes me weeks to work through stuff some of my friends can understand almost right away (bastards).

Anyway, there are a few ways to calculate Voronoi diagrams, Fortune's is just one. Check out this amazing procedural generation tutorial. He uses Voronoi extensively to build a procedural island, run rivers, etc. It's so useful. There's bound to be plenty of C# examples out there if you decide to go down that route.

User avatar
Nystul
Posts: 1501
Joined: Mon Mar 23, 2015 8:31 am

Re: Roads of Daggerfall

Post by Nystul »

very interesting read, thanks!

User avatar
AshSlave
Posts: 11
Joined: Sun Mar 22, 2015 10:09 am

Re: Roads of Daggerfall

Post by AshSlave »

Roads is one of the features that will really compliment the vast world of Daggerfall. I would also like to add signposts and use them for fast travel with fast forward of desirable speed. And of course, random encounters.

User avatar
Dragothor
Posts: 5
Joined: Sun Mar 22, 2015 8:50 pm

Re: Roads of Daggerfall

Post by Dragothor »

This is looking very promising! Keep up the good work!

User avatar
TheLacus
Posts: 1305
Joined: Wed Sep 14, 2016 6:22 pm

Re: Roads of Daggerfall

Post by TheLacus »

I wonder if navgrid maps can be used to procedurally find and choose the limit of a road in town and then use it as a point to start the roads for the streaming word. This could also work in connection with wandering npcs for movement between towns.

User avatar
Biboran
Posts: 277
Joined: Thu Jun 25, 2015 8:26 pm

Re: Roads of Daggerfall

Post by Biboran »

TheLacus wrote:I wonder if navgrid maps can be used to procedurally find and choose the limit of a road in town and then use it as a point to start the roads for the streaming word. This could also work in connection with wandering npcs for movement between towns.
Good idea, but I think some roads may look not very good because random generation. But still, this first time I hearing real idea how to implement roads in df :D

Post Reply