Generation

At the start of the game, the terrain is generated with one start biome of fixed length. After that, a new biome of the same fixed length is generated whenever the hiker gets close to the right border of the currently generated terrain. This is done concurrently to not disturb the playing experience. Similarily, whenever a biome is no longer visible it is removed from the terrrain.

The basepoints used to specify the ground of each biome are generated in an iterative manner. The overall form of the ground in a biome is specified by the terrain phases $ph_1, ph_2, \dots, ph_n$ of this biome as well as a special starting terrain phase $ph_{s}$ that determines the first few point of the ground. Here, each terrain phase has the following format: $$ ph = (\delta v, r, m)$$ Where:

$\delta v \in\R^2$: Average vector to be added to the last point to generate the next one.

$r \in [0,1)$: Randomness, specifies how much we can rotate the average vector to generate the next point.

$m \in \N$: Number of points to be generated using this phase before selecting a new phase.

To generate a new point $p_{i+1}$ using the existing terrain up to point $p_i$ and a terrain phase $ph = (\delta v, r, m)$, we first determine the angular range $[min, max]$ in which generation of a new point is allowed. Then, we generate a new point by adding $\delta v$ rotated to a random angle in the range $[min , max]$. If the angular range $[min, max]$ is empty, no such point can be generated. Therefore, we need to retrace some of the already generated points and try to generate the terrain starting from an earlier point.

Calculating the angular range

The angular range in which generation is allowed is defined by a $min$ and $max$ angle which are determined using a bisection method. More precisely, we iteratively determine these angles by trying different angles and checking whether the terrain would fulfill the constraints if the new point was generated using the current angle and terrain phase. If so, we can try a larger angle in case of $max$ and a smaller angle in case of $min$. The delta angle $\delta_a$ in between tried angles is halfed for every successful try. If $\delta_a$ gets small enough or we exceed a fixed limit of tries, we return the best previously found angle if one exists or that there is no suitable angle.

Determining $min$ and $max$ in an example case is illustrated in the following:

Retracing

Although we check all constraints for every generated point, sometimes we cannot generate a new point from the existing terrain. Then, we need to retrace parts of the previously generated terrain. To do so, we remove a fixed number of points from the terrain. After that, the generation continues normally. Retracing is illustrated in the following Figure.

If we cannot regenerate all points that were removed before we retrace again, then we increment how many points need to be removed by a fixed number and retrace again. We also tried an exponentially increasing retrace count. However, that regularily lead to the entire ground being regenerated which took longer overall. Therefore, we decided to use the linearly increasing retrace count.