TrailblA*

This project simulates the process of trailblazing by procedurally generating terrain maps and using a custom 3D A* algorithm.

Terrain Generation

Random terrain generation is a complicated problem with a variety of approaches. This project uses Perlin Noise combined with a gradient-based erosion simulation.

Perlin Noise

For simulating mountains with no erosion, I combine multiple layers of perlin noise to create a detailed height map.

I multiply each value in the image by a vertical scaling factor and treat each pixel as a height in order to make a 3D map.

Erosion Simulation

The issue is that perlin noise is very smooth, and even with several octaves, mountains have a very "lumpy" appearance; real mountains have sharp peaks and ridges caused by erosion. This may seem like a cosmetic problem, but it is actually important for the functionality of the A* algorithm that the surface and peaks of the mountains are sharp rather than smooth. I will explain this in the A* cost section.

One option for erosion is hydraulic erosion, which is a way of simulating the actual path of water over time as it erodes sediment in the terrain. While this yields really incredible results, it is extremely slow and unwieldy to simulate hundreds of thousands of raindrops over time, and for an A* algorithm, it is probably not necessary. If you're interested in hydraulic erosion, this video by Sebastion Lague is really interesting, but overall seemed to be too complex for this project.

For an alternative to hydraulic erosion, I took inspiration from this video and this article to to implement what I call gradient-based erosion. The concept is pretty simple: in erosion, water carries sediment from high areas to low areas, taking away sediment from peaks and moving it downhill where it is deposited in flat layers. By this logic, steep areas of the map will be eroded more because rain carries more sediment away from them, while flat areas will be eroded less because sediment is deposited in them. To represent this mathematically, I use the gradient of the map, or the x and y derivatives with respect to z. By calculating the x and y derivatives, we can find the slope of each point in the noise map.

Once we have the slope, $m$, we can use the equation $h_{eroded}=h_{initial}\times \frac{1}{1+m}$ to implement this. Steep slopes are crushed vertically and flat slopes remain mostly unchanged. In order to give some control over the level of erosion, this can be scaled with some constant strength factor, $k$: $h_{eroded}=h_{initial}\times \frac{1}{1+m\times k}$. This lowers the sides of mountains while keeping the highest peaks mostly unchanged, meaning that ridges and peaks are stronger and more defined.

This GIF shows the process of erosion, with the uneroded height map at the beginning and the eroded height map at the end.

Biome Generation

Real mountains also have different types of terrains based on environmental factors. I simplified these different terrains into 5 biomes: water, ice, forest, plains, and rock. Each pixel was classified into one of these biomes. Pixels below a constant water level were moved up to that water level and assigned to water. Other pixels were classified using a combination of temperature and moisture. Temperature was defined as $1-\frac{h_{pixel}}{h_{max}}$, where ${h_{max}}$ is the highest point in the map. This causes higher points to have lower temperatures. Moisture was defined using a random perlin map so that each point had essentially random moisture that was somewhat uniform with its surroundings. This is one area of improvement in the project because proximity to water probably should be a factor for moisture. I defined an "ideal" temperature and moisture for each biome:

Biome	Ideal Moisture	Ideal Temperature
Ice	0.5	0.1
Forest	0.6	0.5
Plains	0.3	0.6
Rock	0.3	0.3

Then, for each point, I can calculate a value that represents how well the point matches a certain biome by comparing the actual moisture to the ideal moisture considering some tolerance, $σ$, using the Gaussian Function: $score=e^{- \frac {(actual-ideal)^2} {2σ^2}}$, and calculate the same with the point's actual temperature and the biome's ideal temperature. Multiplying the temperature and moisture scores gives me an overall score for the biome. I generate a score for each biome and find the highest score to choose the best biome.

This image shows an environment with biomes: dark green represents forest, light green represents plains, blue represents water, white represents ice, and grey represents rocks. The colors are slightly blurred to look more realistic.

A* Algorithm

The goal of the A* algorithm is pretty simple: find the most optimal path between two points on the terrain map. Unfortunately, the "most optimal" part provides some complications: hikers don't always like to travel the absolute shortest path possible. For example, a hiker would go out of their way to avoid crossing water, but they also might take a much longer route to avoid having to go up a steep incline or cliff. The question of how to treat elevation gain and incline is the main complicating difference between 2D and 3D A*.

Standard A* Elements

A lot of the A* for this algorithm is identical to the standard 2D approach: it is a graph-theory based approach where each node has both a $g(x)$ (the actual cost to travel from the start point to that node) and an $h(x)$ (the predicted cost/heuristic to travel from that node to the goal point). The total estimated cost for each node is $f(x)=g(x)+h(x)$. To find the optimal path, we store all of the possible neighbors of the starting point as a heap nodes, then explore each of the possible neighbors of each of those nodes, exploring the ones with the lowest $f(x)$ first. I used this tutorial from DataCamp to implement most of the 2D elements.

Neighbor Function

A typical A* neighbor function takes a position in the map and returns every available neighbor of that position, usually including diagonals and horizontal neighbors but excluding obstacles. This is mostly the same in 3D A*, the only difference being that we do have to consider elevation when deciding which neighbors are valid. I did this by calculating the vertical angle or incline between each point and comparing it an angle threshold, initially 45 degrees. This rules out any neighboring points that are too steep. There is also a flag for traversing water; initially, water is considered an obstacle, but some paths are impossible without crossing water, so if a path cannot be found, the algorithm allows traversing water.

Heuristic Function ($h(x)$)

This project allows diagonal motion and motion uphill, so Euclidean Distance is most practical. The typical Euclidean formula $d=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$ does not account for vertical distance, but it is essentially the Pythagorean theorum so it can just be modified to $d=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}+(z_{2}-z_{1})^{2}}$ to get the three-dimensional distance between two points.

Cost Function ($g(x)$)

The cost function weights different types of terrain differently. Given two points, I first calculate the raw distance between the two using the same equation defined in the heuristic function. I defined a dictionary of penalties for each type of terrain:

Terrain	Penalty
Plains	1
Forest	1.5
Rocks	2.5
Ice	4
Water	10

I find the penalties for both points and pick the higher penalty. For example, if point A is in the plains and point B is on the rocks, the penalty will be 2.5, but if point A is on the rocks and point B is in the plains, the penalty is still 2.5. I then multiply the raw distance by the penalty to weight for different types of terrain. This strategy leads to pretty good paths, but I noticed that maps of real trails are often not as direct as the paths I was generating.

An image of a real trail in McCarthy, Alaska.

An example path generated by my algorithm.

Real trails have switchbacks and sharp turns in order to make paths less steep, covering the same altitude in a slightly longer distance in order to make the hike easier. I found I could replicate this by adding an angle penalty into the cost function. I calculate the incline/angle of elevation between the two points, $θ$, and have a constant angle penalty weight, $k$. I use the equation $penalty=e^{k\times\frac{θ}{45}}$ and multiply the weighted cost by this penalty to account for the angle. The stronger the angle penalty weight, the more switchbacks are added to the path.

A trail with no angle penalty.

A trail with a severe angle penalty. Aside from the path itself, it is useful to know that the grade (the elevation gain of the hike divided by the distance of the hike) is significantly lower, but the distance is significantly higher.

Installation/Usage

There are two main runnable files in the project:

1. Run the map_creator.py file to open the map creator interface. The interface features a variety of sliders to customize the map and biome generation, each labeled, on the left side of the window. In the bottom right corner is a small checkbox that will save the map to the maps folder under maps/map_{MAP INDEX}.pkl. In the pickle file is two NumPy arrays, the first being the height map and the second being the biome map.
2. Run the run_trailblazer.py file to test the A* algorithm. The red cone represents the starting point of the path and the green represents the ending point. The red line in between is the calculated path. There are two checkboxes in the bottom right for changing the start and end points. When the start checkbox is selected, clicking anywhere on the map changes the starting point to that point. The same goes for the end point. You can control the amount of switchbacks by changing the angle penalty slider on the bottom. In the top right, there are four statistics: total distance ("dist"), altitude gained ("alt"), the maximum angle of elevation (kind of like the steepest point) on the path ("angle"), and the grade, which is the altitude divided by the total distance, or the slope, of the path ("grade").