Note: This post and the next will reference the faults and plate tectonics described in my tectonic research post. I’ll also assume you know the basics of simplex noise. I posted a quick rundown of some noise terms earlier.
Mountain formation from faults involves some pretty complicated 3D physics. This video starting at 1:28 has a simple sand demonstration of mountain formation. The pattern is similar to compressive material failures like crumpling paper or buckling metal. I have no idea how to put that into equations. From what I know, those equations are very complex and simplifying them removes the crumpling patterns.
I’m trying to say that analytically generating a global elevation map is hard. Therefore most approaches are empirical: the heightmaps are judged by their appearance while the generation methods have little physical meaning.
Why Not More Noise?
The fully empirical approach to terrain generation is to use multiple layers of fractal noise. There are some aspects of this approach I don’t want for this project. Coastlines and terrain features look similar at different levels of zoom. The noise is too regular. There’s a lack of claim to scientific features such as faults, and there’s no way to come back later and incrementally increase the scienceyness.
These problems can be fixed by adding additional noise layers finely-tuned to fix specific problems or to add specific features. But that approach hurts my simulation dreams too much. It’s too arbitrary. As John von Neumann said, “With four parameters I can fit an elephant, and with five I can make him wiggle his trunk.” Masses of arbitrary parameters indicate a failure of the model to do its job, and I want some sort of model to underly this project.
Instead I’ll take an intermediate approach, with hardcoded designs for the structural “bones” and noise layers to cover artifacts and obvious regularities. There still will be an enormous number of input parameters, but many of them will have physical meaning. I’m striving for a maximal amount of non-random, non-noise, logical (and even scientific) underlying structure to everything, then I’ll clean up appearances with a minimal amount of noise.
The Goal
I often refer back to this image when thinking about terrain. It’s not exactly my dream goal, mostly for aesthetic reasons, such as mountain size and seafloor features, but it’s a useful reference. Some aspects I’d like to include are: continental shelves, the sharp drop offs to the sea floor, coastal and internal continental mountain ranges.
Overview
In this post I’ll take the Voronoi cells (representing tectonic plates) from my previous post and develop continents, oceans, and coastlines.
- Randomly assign the plates an age and average elevation.
- Noise the plate boundaries to get nicer looking faultlines.
- Rasterize this information onto a tile map, using a line-drawing algorithm and breadth-first-search floodfills.
- Give the coasts smooth slopes using a modified bfs algorithm
- Create coastlines using more noise.
Plate Assignment
The plates are randomly assigned an age. From the age I calculate whether it is oceanic or continental (oceanic plates are younger). Then I calculate the plate’s average elevation (all plates tend to sink over time). I also assign each a random velocity which will be used in the next post on fault features.
Better Faultlines
Right now each cell edge is a straight line. I want to noise the lines into more organic faults. That’s pretty easy with 1D Simplex noise. I can simply perturb my fault lines with 1D Simplex noise functions perpendicular to the faults.
However, there’s one caveat: with that approach, the starting and ending points of my faults will also move. That means my faults will no longer intersect, as each fault’s end points could move in a random direction. Then tectonic plates are no longer guaranteed to be divided by faults, which could cause problems down the road. Instead, I want my noised faults to still start and end in the original start and end points; that is, I don’t want the fault intersection points to move.
The best way to do this is to sample 2D Simplex noise in a circle.
- Sample noise in a circle from a 2D noise function
- Pick an arbitrary point on the circle as the cut point
- Normalize the noise values on the circle so that the noise at the cut point is zero
- Map the cut point to both ends of the fault line
- Map the rest of the circle noise to the rest of the fault line
This method guarantees that the noise function is zero at the beginning and end of the fault line, yet it is still continuous and smooth throughout. Now my fault intersections will not move, but the faults themselves can be nicely noised.
Note: This method extends to similar situations in higher dimensions. Later on I’ll need to use a 2D noise function on my entire map. Since my map wraps around on the left and right boundaries, I’ll need to sample a cylinder from a 3D noise function to ensure the noise continues smoothly around the map boundaries.
Rasterization
So far, I’ve been storing maps as lists of points and edges. Now I want to transfer to a tile map so I can start applying functions on large swaths of terrain. First I must translate the list of faults onto the tilemap, then I fill in the plates between the faults.
Line Rasterization
There are many ways of rasterizing lines. I’ll originally used Bresenham’s line drawing algorithm, which is efficient and has predictable behavior, but I ended up using a much simpler naive line drawing algorithm because it was two lines of code and worked.
Basically, I step along the line from start to end. At each step, I cast the current coordinates to integers and index into the tile map.
As long as I don’t care about hitting the same tile multiple times (I don’t), I just have to make sure my step size is small enough that I don’t skip a full tile. I use a step size of sqrt(2)/2 (with a tile size of 1). It’s possible that a step size closer to 1 would work; I didn’t bother testing to find out.
To get from faults to rasterization lines, I break everything up into parallelograms. I then break the parallelograms into parallel lines spaced out by sqrt(2)/2 again. Remember that a line with width is just a parallelogram.
Note: The “best” standard algorithm for rasterization involves breaking up parallelograms (and all shapes) into triangles (as always) with at least one side of each triangle being horizontal. Then you can traverse the triangle using horizontal lines. The horizontal lines can be converted directly into ranges of tiles in a row.
Breadth-First Search and Floodfill
Breadth-first search is well documented so I won’t cover it directly here. I will cover the customizations I used in my BFS/floodfill algorithms.
To fill the continents, I start from the center of each tectonic plate (the original point I built Voronoi cells around) and floodfill the tilemap until I hit tiles that have already been written to or the edge of the map. Since I’ve already rasterized the faults, and the tectonic plates are guaranteed to be divided by faults (courtesy of the circular noise function), I am guaranteed to stop and not intrude onto other plates.
I am not guaranteed to fill every plate, though. Why? Some of the plates’ centers are not on the tilemap! Specifically, some plates near the top or bottom of the map have centers above or below the map, respectively.
To fix this, I’ll run through the map a second time, initiating a floodfill algorithm when I hit an empty tile. The floodfill will seek out the nearest written tile, take that elevation, and fill in the “hole.”
Creating Coasts with a Modified BFS
To form continental shelves, the edges of continental plates have to be below sea level (50-200m below to be precise). In order to form these and the gradually sloping coastal plains that generally appear (when coastal mountains aren’t involved), I want to start every continental edge touching water (faults between continental and oceanic plates) to start at -150m and gradually slope up to the continent’s average elevation.
I’d like to introduce the concept of a fault feature here. In this project, a fault feature is a terrain element that propagates more or less parallel to a fault. The continental shelf and coastal plains slope up from the fault line to the continent’s average elevation, so it is a fault feature, although it only propagates on one side of the fault. In the next post I’ll cover many more fault features, such as subduction, mountain ranges, and continental rifts. Since fault features have many aspects in common, I’d like to draw them all using a similar mechanism.
I first tried a simple linear algorithm that drew perpendicular to the fault. It was similar to how I first rasterized the faults onto the tilemap, except thicker.
Here is an picture from a very old iteration where I used such a linear algorithm to draw all sorts of fault features.
The main issue with this approach is the straight line and corners that bookend the faults. They are extremely regular and noticeable and create issues wherever the fault features overlap. Considering I wanted to draw more fault features besides shorelines (mountains, rifts, etc. will be covered in the next post), I knew I needed to fix these artifacts.
I tried tapering the ends of the fault features but that still looked bad.
So I switched to a modified BFS. Instead of drawing straight out from the fault, I start a BFS queue with all the tiles on the fault. Then I randomly shuffle the queue to prevent directional artifacts and then conduct a limited breadth-first search.
In the next post I’ll expand on this BFS/floodfill algorithm for fault features and add some additional capabilities.
Back to the continental shelves: I apply a set linear upward-sloping profile from the fault in the direction of the continental plate.
Finishing Coasts with More Noise
Now it’s time to hide all of the obvious regularities with a bit of noise. Given how shallow the coastal slopes are, just a small amount of noise (amplitude of +/-300m vs max average continent elevation of 1500m) should believably disrupt the coastlines.
Now we have believable coastlines, continental shelves, and a steep (vertical, actually) dropoff to the main seafloor.
Next Up: Fault Features
I’m going to finish up terrain generation with more fault features, including mountains, trenches, oceanic ridges, continental rifts, and some final noise functions.
TODO
- My current algorithm makes it very hard for archipelagos to form. That is one realistic feature that fractal noise is very good at creating which I have lost by using very little noise. I plan to consider different methods for adding archipelagos if they don’t resurface in the next post.
- The seafloor looks like a patchwork quilt. I suppose it’s visually interesting but very unrealistic. I’d like to use a blurring algorithm to smooth the transitions. On the other hand I doubt I’ll be using ocean depth for very much so it’s probably not worth the time right now.
- The continental shelves should have a minimum width.
- Some day I’d like to do full tectonic plate modeling. There are a few projects out there that have done it with interesting results, but you can definitely get interesting features like island chains and the characteristic patterns of oceanic ridges.