Road Generators
- Create some intersections - to do
- Convert intersection to Direction Intersections by identifying incident roads in direction quadrants (top is North, left is West, bot is South, right is East)
- Create a grid and cells of it.
- Apply WFC to fill cells with Direction Intersections
- Adjust the original intersections' positions based on their direction counterparts' positions. - to do
- Connect incident roads based on their placement on the direction quadrant - to do
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.
This is a sample grid of (500m X 500m) and each cell is (100m X 100m). Initially no cell has any element placed.
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.
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.
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:
- No more intersections to place.
- No more empty cells.
- Maximum tries reached.
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.
At each step, a new placement is done by the following process:
- Find the empty cell with the minimum entropy. But there are multiple such cells, choose one randomly.
- Find the set of compatible intersections for the cell. Each of these candidates is compatible with the elements of the adjacent 8 cells.
- Place one of the candidate intersections in the cell.
- Decrease the entropy of each adjacent empty cell by 1.
Now, the output of the previous process is the cell positions of each Direction Intersection. In this step, we place the intersection corresponding to a cell in the middle of the cell.
One idea would be to keep the positions of each intersection fixed, and create new connection roads, and export everything to a single OpenDRIVE file. Another idea would be to create geo-connection roads between adjacent intersections which hold the intersection together and then readjust everything.
From direction quadrants, we identify the incident roads to be connected in adjacent cells. There are some cases where 2 or more roads may lead into one. We need to solve that