So, on yesterday's stream I've implemented a different algorithm for generating the road network: flood-filling a voronoi map (accounting for terrain movement cost) and connecting two villages where their voronoi regions meet. (1/n) #indiedev #gamedev #indiegames

This worked fine, but often it would generate weird roads because the place where two villages' regions meet isn't necessarily on the shortest path between them. (2/n)

So, I switched to generating the actual shortest path between any two villages with neighbouring voronoi regions. It works better, but I felt like it produces way too many roads, especially way too many intersections. (3/n)

In the end I switched to a simpler idea: use the same Delaunay triangulation to determine which villages to connect, but then find the true shortest path between them for the actual road. This approach looked the most satisfying to me. (4/4)

@lisyarus You want to solve the Steiner tree problem to create your road network, it will give you exactly what you want.