Road Generators

WFC-based generators

Steps

1. Create some intersections
2. Convert intersection to Direction Intersections by identifying incident roads in direction quadrants (top is North, left is West, bot is South, right is East)
3. Create a grid and cells of it.
4. Apply WFC to fill cells with Direction Intersections
5. Get Direction Intersection positions based on the cell placement.
6. Adjust the original intersections' positions based on their direction counterparts' positions.
7. Connect incident roads based on their placement on the direction quadrant

2. Intersections -> Direction Intersections:

A direction intersection is defined by four direction quadrants (top is North, left is West, bot is South, right is East). An incident road is placed in a direction quadrant based on the outgoing heading at the incident point. Headings are calculated counter-clockwise from East.

The conversion tool is based one invariant in the intersections: no two incident roads ever overlap.

The process is shown here:

So, the direction intersection has only 4 properties each saving a reference to one direction quadrant. Each direction quadrant has two properties to save the number of incoming and the number of outgoing lanes.

3. Grid and Cells

This is a sample grid of (500m X 500m) and each cell is (100m X 100m). Initially no cell has any element placed.

4. Apply WFC

Entropy and entropy propagation: higher the entropy, higher the uncertainty. In this case, we tag entropy to each of the cell. At some point during the map generation process, some cells have elements assigned, and some still empty. A cell with an element puts some constraints on its adjacent cell. So, the cell reduces entropy (==uncertainty) of its adjacent cells.

We initialize the cells with an entropy value of 8. Once a placement is done in a cell, the entropies of the surrounding cells decrease by 1.

Element compatibility: A placement also adds a constraint on the possible configurations of Direction Intersections in the empty cells around it. For example, if a cell has an intersection that has 1 incoming lane in its top quadrant, the cell on top must have an intersection that has at least 1 outgoing lane in its bottom quadrant. So, the invariant of the algorithm is - adjacent cells must have compatible elements (either intersections or empty spaces). Empty spaces are compatible with any elements. In the figure below, A cannot be placed on top of B, but the reverse is a valid placement.

So, the WFC process takes a grid and a set of Direction Intersections as an input. And it continues to place intersections in the grid cells until of the conditions are met:

1. No more intersections to place.
2. No more empty cells.
3. Maximum tries reached.

At each step, a new placement is done by the following process: