User:JJFMJR/sandbox

Procedural Road Generation is the algorithmic creation of roads across some terrain in a virtual world. The problem is that given some terrain, create a road from point A to point B in the most realistic and cost effective manor. There are many proposed solutions, however the problem remains an active area of research.

This article is inspired by the work of E. Galin, A. Peytavie, N. Marechal, and E. Guerin : Procedural Generation of Roads

File:PRGVisual1.png

File:PRGVisual4.png

Problem Statement

Procedural Generation of Roads is a difficult problem for computer scientists. The goal is to automatically create a road from point A to point B across a terrain. This problem is particularly challenging considering the various parameters of the terrain, such as vegetation, slope, and bodies of water. A solution must be automatic, controllable, and provide realistic and believable results. Computational cost may be large for modeling reasonably-sized terrain, and there is often a significant trade off between controllability, automation, and realism. In result, an 'ideal' solution is dependent largely upon the requirements of its host application.

The task can be divided into two sub-problems. First, a 'shortest' path must be calculated across the terrain from point A to point B; the Anisotropic Shortest Path problem. The path may be shortest in terms of distance, financial cost, or some other metric. It may cross rivers, remove foliage, or tunnel through a mountain, and the path chosen must minimize some cost. Once a path is defined, the road must be procedurally and graphically modeled to fit the path. The terrain must be terra-formed along the edge of the road to model the flat shoulders of a highway. Bridges must be modeled over bodies of water or large ravines, and tunnels must be created to cut through large rock. Each of these requires manipulation of the base terrain and further complicates the road generation problem.

Applications

Procedural Content Generation has many applications across various disciplines. Automatic content can significantly reduce production time and cost for creating a graphical environment. When the content is generated automatically, fewer man hours are needed to build a scene, and the production team may focus on other challenging areas of building a graphical environment. For outdoor scenes, roads are particularly important. They add realism, immersion, and often play a crucial role in transportation for interactive systems.

The Entertainment industry has largely adopted procedural generation of content and roads. For instance, Electronic Arts' SimCity makes heavy use of procedurally generated roads when a user designs his/her own city. Procedural generation of roads is also prevalent in the movie industry, training applications, real-life simulations, and path planning systems.

Anisotropic Shortest Path

File:PRGCurvedGrid.png

The Anisotropic Shortest Path problem is core to solving the Procedural Road Generation problem. The task is to determine a path from point A to point B across some surface, in this case a terrain. Anisotropic is a particularly important word, and it elevates the difficulty of this problem; Anisotropic for this problem means that the shortest path is dependent upon the velocity and acceleration of travel. For instance, traveling around a steep mountain may be 'shorter' than climbing it, because the velocity will be drastically reduced when trying to scale the steep slope. An isotropic shortest path would ignore this, and travel any possible path from point A to point B over the mountain.

The anisotropic path problem can be quantified in the following manner. We wish to minimize a cost function from point A to point B, where the cost function takes into account the gradient of the terrain and natural obstacles such as foliage, lakes, and rivers. A steeper gradient, more foliage, and lakes and rivers will all increase the 'cost' of some path. The path from A to B that has minimum cost will be the ideal road trajectory.

Finding the Shortest Path

Formally, consider the set Ρ of all possible paths from A to B. Each ρ ε Ρ is a parametric function such that ρ(0) = A and ρ(1) = B with cost C(ρ). At each time t along path ρ, there is some cost c(ρ(t), ρ′(t), ρ″(t)), which determines the cost of position ρ(t), velocity ρ′(t), and acceleration ρ″(t) along path ρ at time t.

${\displaystyle C(p)=\int _{0}^{T}c(p(t),p\prime (t),p\prime \prime (t)),dt}$

The continuous weighted anisotropic shortest path problem consists in finding a path ρ* that minimizes the function C(ρ).

${\displaystyle C(p*)=\min C(p),p\in P}$

This formal expression captures a few key ideas. First, there are many paths from A to B that must be evaluated. A cost value can be calculated for each path (Equation 1), and we are interested in finding the path p* that has minimum cost (Equation 2). Additionally, the first equation calculates the cost of a path by summing the cost at each step along the path. Each step is evaluated anisotropically based on the position of travel p(t), the velocity of travel p′(t), and the acceleration of travel p″(t).

File:PRGGridSize1.png

File:PRGGridSize2.png

File:PRGLimitDirection.png

Discretizing the Space

Solving the anisotropic equations on a continuous domain presents many problems! For one, it's computationally infeasible. In order to solve the problem, the terrain must be discretized. The most common way is to divide the terrain into a grid. A path through the grid is defined as a series of neighboring nodes that, when traversed, lead from point A to point B.

Once the space has been discretized, the weighted anisotropic shortest path problem is reduced a graph. Graph theory solutions can be applied to determine the shortest cost path between points A and B. One such algorithm is the A* search algorithm. Given a graph G and grid points A and B, A* computes the shortest path from A to B over graph G.

File:Grid Mask.png

The Limit On Direction

This conversion to a discrete space also introduces some challenges however. For instance, there is an explicity loss of information related to the resolution of the grid, and because this problem is anisotropic, neighboring grid points may not give an accurate representation of the optimal path. This is called the Limit on Direction Problem. Figure X highlights this in detail. Here, we see that considering paths between a small number of neighbors does not cover all possible directions leaving a soure point. The paths are limited to a small subset of possible options, because there is a limited number of nearby neighbors. The first grid has four neighbors per node (graph connexity), and consequently an angle resolution of 90°. The second grid has a connectivity of 8 neighbors and an angle resolution of 45°. While increasing the connexity of the grid betters the optimal path, it also drastically increases computational complexity.

E. Galin, et. al. provide an interseting solution to this problem in their work Procedural Generation of Roads. They allow each grid point to neighbor all points within an increased distance, such that the connexity is greatly increased. They also provide a means for removing redudant information and calculation through a specialized data representation. Please read their work for more information! Figure X highlights the change.

Calculating Cost

In order to determine the shortest path, each path must have an associated cost. All possible point paths within the grid are evaluated by the cost function. At each point on the terrain, key features of the land are evaluated to determine the cost of building a road. These features must be examined from a surface road, bridge, and tunnel perspective. The cost function for each grid point is of the following form.

${\displaystyle C(p)=\int _{0}^{T}c(p(t),p\prime (t),p\prime \prime (t)),dt}$

File:ProceduralRoads Surface.png

File:ProceduralRoads Bridge.png

File:Procedural RoadsTunnel.png

The cost function is implemented as a weighted sum of 'feature functions', where the feature functions change for surface, bridge, and tunnel roads respectively. The weights for each feature are tuning parameters to the system, and can be modified to change the behavior of the algorithm. For instance, curvier roads can be reducing the weight of the curve-cost feature function. All features for each type can be tuned likewise.

Surface, Bridges, and Tunnels

For Surface Roads, the key features to consider are:

1. The slope of the terrain in the direction of the road
2. The curvature of the road
3. The density of nearby vegetation
4. The height of nearby water

For bridges, the key features to consider are:

1. The slope of the bridge
2. The curvature of the bridge
3. The height of the bridge
4. The depth of water bodies that the bridge crosses

For tunnels, the key features to consider are:

1. The slope of the tunnel
2. The depth of the tunnel to the surface

Procedural Generation of Models

The final steps are to create the graphical representation of the road. In order to do so, the discrete shortest path from A to B is first converted into a piecewise clothoid spline. These curves are more representative of real-world roads. Next, the path is segmented further into pieces, where each piece is designated as surface, bridge, or tunnel, based on the optimization from above. Finally, the terrain and vegetation are modified along the path via excavations and embankments. Generic procedural road mesh models are inserted piecewise along the modified terrain.

File:PRGSurfaceMesh.png

Road Models

The mesh models for the road are also created procedurally. The parameters that define a road are the curved path C, the width of asphalt r, and the blending region R of the nearby terrain. Surface, bridge, and tunnel models are then generated along the path to meet the prescribed parameters.

File:PRGTerrainExcavation.png

Terrain Excavation

The blending region parameter allows for the modification of nearby terrain. This parameter describes the shoulder width, that is the distance outward from the edge of the road that should be modified to fit the terrain. First, the terrain is leveled to the road height and vegetation is removed, wherever the asphalt lies. Next, the terrain in the blending region is interpolated to match the flatness of the edge while retaining its earlier slope. Figure X hilights this algorithm.

File:PRGWaterCost1.png

File:PRGWaterCost2.png

Controlling the Algorithm

Controlling the road generation functions is an important area of research. This work provides a number of tuning parameters as described in Calculating Cost section. These images highlight the different paths created from tuning the parameters, particularly the cost of crossing water. The first image will try to avoid vegetation and has low cost for bridges, while the second image will avoid crossing large bodies of water. Consequently two very different paths are created.