Sunday Experiment - Generating Procedural Roads

I'm a bit sick this morning, so this week's Sunday Experiment is a quicky. One of the things I want to improve in When Pigs Fly is the feeling of a live world around you.  The first step in that direction is adding towns and roads.  Also, as I start distributing more things to do around the map, its important to have some sort of system to guide players to those activities.  I think roads are a nice, subtle method of directing players to new areas.  For today's Sunday Experiment, I started laying the foundation for a system that generates roads procedurally, while still allowing me to control where certain roads end up.

The map in When Pigs Fly is pretty big (and possibly infinite in the near future). As a solo developer, I don't have time to hand lay roads.  At the same time, I don't want a completely random road system.  I need the roads to lead to certain areas, and sometimes specific points. 

This morning, I wrote a script that accomplishes this at the most basic level.  It takes in an array of transforms that represent points where I need the road to go, then randomly generates a predetermined number of extra points.  Finally, I generate a road system that connects these points using a Voronoi minimum spanning tree (rather than reinvent the wheel, I used the MIT-licensed Unity-delauney package available here).

Here's the code:

public Rect bounds;
public Transform[] intersections;
public int numRandomPoints;
public float roadHalfWidth;
public Color roadColor;

void GenerateRoads()
{
        //Generate points
	List points = new List();
	List colors = new List();
	for(int i = 0; i < intersections.Length; i++)
	{
		colors.Add(0);
		points.Add(new Vector2(intersections[i].position.x, intersections[i].position.z));
	}
	for(int i = 0; i < numRandomPoints; i++)
	{
		colors.Add(0);
		points.Add(new Vector2(Random.Range(bounds.xMin, bounds.xMax), Random.Range(bounds.yMin, bounds.yMax)));
	}

	//Generate map
	Delaunay.Voronoi voronoi = new Delaunay.Voronoi(points, colors, bounds);
	List lines = voronoi.SpanningTree(Delaunay.KruskalType.MINIMUM);

	//Build Mesh
	List verts = new List();
	List tris = new List();
	List normals = new List();
	List col = new List();

	int triIndex = 0;

	for(int i = 0; i < lines.Count; i++)
	{
		Vector3 p0 = new Vector3(lines[i].p0.Value.x, 0f, lines[i].p0.Value.y);
		Vector3 p1 = new Vector3(lines[i].p1.Value.x, 0f, lines[i].p1.Value.y);
		Vector3 perpendicular = Vector3.Cross(Vector3.up, p1 - p0).normalized;
	
		verts.Add(p0 - (perpendicular * roadHalfWidth));
		verts.Add(p0 + (perpendicular * roadHalfWidth));
		verts.Add(p1 - (perpendicular * roadHalfWidth));
		verts.Add(p1 + (perpendicular * roadHalfWidth));

		tris.Add(triIndex);
		tris.Add(triIndex + 2);
		tris.Add(triIndex + 1);

		tris.Add(triIndex + 2);
		tris.Add(triIndex + 3);
		tris.Add(triIndex + 1);

		triIndex += 4;

		for(int x = 0; x < 4; x++)
		{
			normals.Add(Vector3.up);
			col.Add(roadColor);
		}
	}

	MeshFilter filter = GetComponent();
	Mesh mesh = filter.sharedMesh;
	if(mesh == null)
	{
		mesh = new Mesh();
		mesh.name = "roads";
		filter.sharedMesh = mesh;
	}
	mesh.vertices = verts.ToArray();
	mesh.triangles = tris.ToArray();
	mesh.normals = normals.ToArray();
	mesh.colors = col.ToArray();
	mesh.UploadMeshData(true);
}

I'm pretty happy how well this works.  Obviously, the system is very limited at this point.  It's generating simple planes for roads, not accounting for terrain elevation.  In the future, I'll need to improve the system to sweep along the roads and match their height to the terrain below them.  The basic principles are working though.  If I use this system in small 'cells', I'll be able to use the random points to generate small towns around the map (with buildings spawned along the roads), as well as use the predefined points to connect the towns, guide players to activities, and route roads through mountain passes.