romanwck

Procedural Generation of Road Networks

As part of my master’s thesis at Kempten University of Applied Sciences, I researched and developed an algorithm for the procedural generation of road networks within a heightmap and answered the following research question:

How can an algorithm be realized that autonomously generates a road network within a heightmap while taking into account the requirements of scalability, modularity, parameterizability, and visual fidelity?

As a proof of concept, I’ve developed a prototype in the Vektoria Engine, using it only for rendering and graphics API integration. All geometry was procedurally generated by my algorithm.

Making Of

Since the road network must adapt dynamically to the terrain, I began by generating the heightmap geometry from a noise texture:

To meet the requirements of scalability and modularity, I decided to split the terrain into chunks, which allows parts of the mesh to be culled for optimization reasons.

As a first step, it was important to be able to determine the height of the terrain at any given point. By dividing the x and z coordinates by the chunk size and applying a floor operation, the indices of the chunk can be determined. In the same way, the indices of the quad within the chunk can be determined.

Since the diagonal is given by y = x, it can easily be determined in which triangle the position lies. Given the vertices of the triangle, the height of any point within it can be computed using barycentric coordinates. This approach is inspired by ThinMatrix.

This information becomes particularly valuable when the road network must adapt to the terrain and avoid intersections with it.

As a next step, I developed a procedural algorithm to plan the road network. Since the terrain was already chunk-based, adopting a tile-based approach for road network generation was the natural choice. I came across an algorithm for the procedural generation of dungeons by Blackthornprod which served as a good starting point for my own algorithm.

The algorithm uses a selection of equally-sized rooms. Each room can have up to four doors. The TRBL room has doors to all sides, while the RL room only has doors to the left and right sides.

The algorithm starts by generating the first room at random. For the most even distribution possible, a TRBL room is most suitable. All unconnected neighbor tiles are written into an open list. In each iteration of the algorithm, the first element is processed and removed from the list. If a tile has constraints imposed by adjacent tiles, those constraints must be met. Out of the subset of rooms that fulfill the requirements, one can be selected at random. These steps are carried out for each tile in the open list until the algorithm naturally terminates at some point or is constrained by artificial termination conditions.

I took this idea and applied it to the procedural generation of road networks. Instead of thinking of rooms in a dungeon, a TRBL room can also describe an intersection, three-letter rooms as junctions, TB and RL rooms as straights, the remaining two-letter rooms as curves, and one-letter rooms as dead ends.

At this stage, the road network appeared highly regular, but this issue will be addressed later when it comes to generating the geometry. Up to this point, the road network only existed in 2D and was still totally disconnected from the heightmap.

To address this, I’ve sampled the height of the terrain where a tile connects to its neighboring tiles. In the TRBL case, I’ve sampled four additional points and used these to calculate the angle of the slopes. If a slope is too steep, another constraint is applied to the tile, further reducing the pool of possible tiles.

Next, I needed to generate the geometry for the roads. I created a simple profile in 2D which can be extruded along the third axis. This approach was already suitable for straight roads.

To create roads with curves and meet the requirement of visual fidelity, I’ve decided to generate the geometry along a cubic Bézier spline. This approach is inspired by a video essay titled “The Beauty of Bézier Curves” by Freya Holmér. I’ve sampled the Bézier spline in discrete steps and calculated a TBN coordinate system (tangent, bitangent, normal) at each point and used this local coordinate system to offset the vertices of the profile.

Since I was still considering the very standard case of 90° angled curves where four tiles would form an approximation of a circle, I calculated the control points of the cubic Bézier spline accordingly. I’ve used mirrored control points at the transition between two tiles to achieve a smooth continuous road.

The next challenge was that the road intersected the heightmap terrain. That was because the sample rate was too low. The road sampled the terrain only at the start and end of it, but not in between. I also couldn’t sample the terrain height at every discrete step along the cubic Bézier spline, as doing so would produce a bumpy road and break the smoothness of the curve in the vertical direction.

The solution was something in between: I constructed each road out of four road segments, sampled the height at these points, and interpolated in between using four cubic Bézier splines.

For the intersections and junctions, I chose to create procedural models. I started with the TRBL case, as all junctions can be easily derived from it. I set up the equations of the lines and calculated all the points of intersection. In the special case of a 90° intersection, vertices collapse in the same position.

To easily identify each intersection point independent of the case, I assigned indices. Next, I triangulated a mesh from the points and created a triangulation table.

Junctions were generated in the very same way. I’ve also created triangulation tables for them. These five triangulation tables are used as LUTs (lookup tables) when generating the mesh.

At this point, I was able to generate all components of the road network. The final step was to eliminate the regularity.

To achieve that, I defined min and max values along the edges and randomly picked a point along each edge. When the points are connected, a basic intersection is formed. Doing it that way for every tile would produce abrupt changes in direction at the transition between two tiles.

To address this, I’ve composed the TRBL case from four roads and one intersection. The normal of the road is always perpendicular to the edge of the tile, and the control points of the cubic Bézier spline are mirrored.

If the road network should maintain some regularity, the intersection can be moved to the center of the tile and the roads will automatically adapt to it.

To ensure parameterizability, all parameters were made fully configurable, enabling the generation of a wide variety of road networks.

Screenshots

Tags