Pseudo-ramdom procedural roads¶

Suppose one wishes to describe a road between A and B in terms of segments

$$ \text{straight, turn left, straight, turn right, straight} $$

Let's see how we can create a random road of length $L$ from a pre-determined set of prefabs.

Random apportionment of total length¶

Suppose we want to build a road of length $L$ out of $K$ segments. The total number of waypoints $N$ depends on the step size $\Delta s$:

$$ N = \frac{L}{\Delta s}. $$

Let $\left( p_1, p_2, \dots, p_K \right)$ represent the proportion of $N$ that each prefab will be assigned, where $\sum p_i = 1$. One useful distribution here is the Dirichlet distribution, which is parametrized by a vector $\mathbf{\alpha} = \left(\alpha_1, \alpha_2, \dots, \alpha_K \right)$. The special case where all $\alpha_i$, the scalar parameter $\alpha$ is called a concentration parameter. Setting the same $\alpha$ across the entire parameter space makes the distribution symmetric, meaning no prior assumptions are made regarding the proportion of $N$ that will be assigned to each segment. $\alpha = 1$ leads to what is known as a flat Dirichlet distribution, whereas higher values lead to more dense and evenly distributed $\left( p_1, p_2, \dots, p_K \right)$. On the other hand, keeping $\alpha \leq 1$ gives a sparser distribution which can lead to larger variance in apportioned number of waypoints to $\left( p_1, p_2, \dots, p_K \right)$.

Expectation value and variance of Dirichlet distribution¶

Suppose we draw our samples for proportion of length from the Dirichlet distribution

$$ (p_1, p_2, \ldots, p_K) \sim \text{Dirichlet}(\alpha, \alpha, \ldots, \alpha) $$

with $\alpha _{0}=\sum _{i=1}^{K}\alpha _{i}$, the mean and variance are then

$$ \operatorname {E} [p_{i}]={\frac {\alpha _{i}}{\alpha _{0}}}, \; \operatorname {Var} [p_{i}]={\frac {\alpha _{i}(\alpha _{0}-\alpha _{i})}{\alpha _{0}^{2}(\alpha _{0}+1)}}. $$

If $\alpha$ is a scalar, then $\alpha _{0}= K \alpha$ and the above simplifies to

$$ \operatorname {E} [p_{i}]={\frac {\alpha}{K \alpha}}={\frac {1}{K}}, \; \operatorname {Var} [p_{i}]={\frac {\alpha(K \alpha -\alpha)}{(K \alpha)^{2}(K \alpha +1)}}. $$

We see that $\operatorname {Var} [p_{i}] \propto \frac{1}{\alpha}$ meaning that the variance reduces with increasing $\alpha$. We can simply scale the proportions

$$ (N \cdot p_1, N \cdot p_2, \ldots, N \cdot p_K) $$

to get the randomly assigned number of waypoints for each prefab. We now have a distribution which can give randomly assigned lengths to a given list of prefabs, with a parameter to control the degree of randomness. With a large concentration parameter $\alpha$, the distribution of lengths will be more uniform, with each prefab getting $N \cdot \operatorname {E} [p_{i}]={\frac {N}{K}}$ waypoints assigned to it. Likewise, keeping $\alpha$ low increases variance and allows for a more random assignment of proportions of waypoints to each prefab segment.

Random angles¶

Suppose a turn of a pre-defined arc length $l$ made of $N/K$ waypoints. If one wants to create a random angle, one has to keep in mind that the minimum radius $R_{min}$ depends on the speed of the vehicle and the weather conditions:

$$ R_{\text{min,vehicle}} = \frac{v^2}{g\mu}, $$

where

• $v$ is the velocity of the vehicle in $\text{m/s}$,
• $g$ is the gravitational acceleration (about $9.8$ $\text{m/s}^{2}$), and
• $\mu$ is the friction coefficient (about $0.7$ for dry asphalt).

A regular turn (not a U-turn or roundabout) should also have an lower and upper limit on the angle, say, 30 degrees to 90 degrees for a conservative estimate. In terms of radii, it becomes

$$ R_{\text{min}} = \max\left(R_{\text{min,vehicle}}, \frac{l}{\pi/2}\right) $$

and

$$ R_{\text{max}} = \frac{l}{\pi/6}. $$

We then sample

$$ R \sim \text{Uniform}\left(R_{\text{min}}, R_{\text{max\_angle}}\right) $$

and obtain a random radius for a turn of arc length $l$ with limits to ensure the radius is large enough given the velocity of the vehicle. Finally, the curvature profile is related to the radius by

$$ \kappa = \frac{1}{R} $$

which means that the curvature profile of a turn is simply a vector $\mathbf{\kappa} = (1/R, \dots, 1/R)$ with a length of $N/K$ waypoints.