Why Are Rivers So Complicated?

Why Are Rivers So Complicated.md

Update

You can now read this document / article, at https://alcatrazescapee.com/rivers/. It will be updated further there. The original content is still here, below

---

Why Are Rivers So Complicated?

Let's narrow that down a bit. This document will try to explain some of the difficulties, limitations, and possible ways to generate rivers in Minecraft. There have been many papers, articles, and other medium which have generated realistic rivers to great success. So what makes Minecraft so much more difficult, or what makes these other methodologies so difficult? And what methods have found success?

Requirements

In order to answer the main question, we need to define what we want out of rivers. At their very basic level, rivers are best thought of as some form of graph structure (although rivers need not be generated from such a structure). Here are a few features that one would like to see in a realistic river generation method:

1. Self-similarity - rivers should have a fractal like appearance, with extensive curving parallel to the primary direction of motion.
2. Directionality - rivers have an obvious direction of flow.
3. No cycles - they should be able to be interpreted as Directed Trees*.
4. Source and Drain - rivers should begin at a source location (either a body of water, glacier, spring, or other natural source), and travel to a destination, either a larger body of water or ocean.
5. Flow accumulation - rivers should increase in size (width) as they flow from source to drain, and should also increase in size upon connecting to branches.
6. Height - rivers should generally flow down slopes.

*While rivers in realistic situations are not strictly directed trees, and more so resemble directed acyclic graphs, due to processes such as bifurcation, the more restrictive definition is a good one for the purposes we are looking for.

Constraints

And before we get into various river generation methods, it is useful to understand a few constraints imposed upon us by Minecraft's terrain generation. Minecraft terrain is procedural, unbounded, and chunk based. What this means: each chunk (a 16x256x16 area of the world) is generated independently of all other chunks. There are ways to stretch this limitation, but in principle, in order to know the height at a given position, you will need to generate (part of) the chunk at that position. Allowing this can quickly lead to runaway generation, thread deadlocks, or horrible performance sinks.

In order to generate rivers, any world generation method must define what level of context it requires, of which I will group methods into Context Free, Bounded, and Unbounded methods. So, what do these all mean?

Context awareness (or locality):

• Context Free methods are those which do not require any information about the world (context) in order to generate. They are generated completely independently to terrain, which makes them perfect for the style of infinite, procedural chunk generation used by Minecraft. This encompasses any method that starts with noise (e.g. simplex or cellular) and any possible transformations (ridge, domain warping, octaves, etc.) in order to generate rivers.
• Bounded methods are those which require some context, but the distance away that they require context is both finite and bounded. This includes generation methods such as biome generation - each step is only aware of some amount of neighbors, and there are a finite amount of layers, resulting in a maximum distance away that one pixel could influence another. This is doable within procedural, unbounded generation by simply acquiring the required context to generate any given location, and is used all over Minecraft, from caves, to structures, to features, to terrain height.
• Unbounded methods are those which require context from a distance which cannot a priori be determined. This describes methods such as "from this point, traverse until you reach an ocean". That step introduces a fundamental problem for Minecraft, due to the fact that we cannot put an upper limit on the distances to the nearest ocean. This can create situations where there may be context that we need in order to generate this chunk, that we don't have access to. This typically leads to features that are cut off at chunk borders, incomplete, or half generated (as we cannot retroactively generate back into already generated chunks!). Any river generation that falls into this category will not work for Minecraft.

So, it's clear that in order to create any form of river generation, it must be either a context free, or bounded algorithm.

Vanilla Rivers

You might be saying at this point, "But Minecraft has rivers!". So, how do Minecraft's rivers generate, and how to they satisfy the criteria above?

Vanilla rivers are biomes, and are generated in a Context Free manner, using various noise techniques. So how do they rank up against our list of requirements?

• Due to multiple octaves of noise, vanilla rivers exhibit good fractal like patterns. (1.)

And that's about it. They have no direction (2.), cycles are common (3.), rivers are homogenous on a large scale and don't have well defined sources or drains, (4.), since they have no directionality they have no flow accumulation, (5.), and are all at sea level (6.).

Image: Vanilla Rivers, 4km width.

(Other) Noise Based Rivers

There are a whole bunch of variants on the above simple principle: take noise, apply transformations, output rivers. These methods are quite clearly Context Free. However, despite a lot of expertise which can go into crafting very complex and beautiful outputs, they tend to be difficult or impossible to meet a lot of the "realistic rivers" criteria. There are many possible techniques:

• Take simplex or other smooth noise, and take the absolute value, or separate out particular bands of output values.
• Start with some form of cellular noise and mark the edges as rivers.
• Use F1/F2 (or other) transformed Worley (cellular) noise.

However despite the differences, all the above methods generally have the following traits:

• Octaves of noise are by definition self similar, so (1.) is satisfied, and decent looking river shapes can be teased out of noise with effort.
• And everything else is unachievable. The definition of context free excludes the possibility of 6., unless the height generation can also be done context free.

A Different Approach: Constructing Rivers

It should be clear that any form of simulation of real world river creation methodologies is no simple task. Rivers are influenced by many factors, including land height and composition, climate, and erosion. Simulating river generation using a combination of these factors is infeasible, even for world generators not restricted in the same way Minecraft is. So as in the case of most world generation, the goal is to come up with something that is able to generate believable rivers, through some other mechanic.

One method for simulating rivers in a finite-world context involves some form of water map traversal. This is a fairly simple concept: start with a pre-determined amount of water at every location on your map, and simply move the water down slopes (bonus points if this also erodes the surface height). If your terrain is representative of natural terrain height variation, you will get natural-looking rivers to form as water accumulates and finds it's way towards the lowest points, which either are occupied then by lakes or oceans. This is method detailed in a series of blog posts about Undiscovered Worlds.

A slight modification to the above idea, is to pick designated starting positions, and then again, traverse downslopes, drawing a river as you do. This is the technique described by the Polygonal Map Generation by Red Blob Games (Article).

These methods also generally classify into two options: Source to drain, and drain to source methods.

1. Source to drain methods start by generating the source of rivers, and build river like shapes by traversing downstream, in the direction of the supposed river flow.
2. Drain to source methods start at the drain, or outlet of rivers, and build shapes by traversing upstream, in the opposite direction of river flow.

The differences and major pros and cons of both methods are illustrated in the below table:

Drain to Source	Source to Drain
Traversing upstream needs to be careful to not cause upstream intersections or crossovers with other rivers.	Traversing downstream naturally causes rivers to join together and form larger rivers.
The drain of a river is always well defined.	The drain of a river needs to be found, resulting in either unbounded searching, or the in-progress river being discarded.
Branches and tributaries can be explicitly formed during upstream iteration.	Branches are difficult to do explicitly and have to be formed by intersecting rivers.
(For height based methods) Heuristically traversing up slopes may not reach ideal source locations.	(For height based methods) Traversing down slopes will always reach oceans or other local minima, the latter which can be used to create lakes.

Both of the above methods are quite clearly Unbounded, and also result in another difficulty when applied to Minecraft, which is requiring context knowledge of the height of the terrain at an arbitrary (possibly un-generated) position. So, in order to apply this to Minecraft, we need to find a way to bound it, or explore other methods for river generation.

In general, the above methods are capable of meeting most if not all of the realistic river requirements:

• With appropriate techniques (more on this later), rivers can be made self similar. (1.)
• The construction of rivers naturally gives them direction (2.), avoids creating cycles (3.), and naturally creates both drains and sources (4.)
• With some methods, river flow can be controlled with the generation of branches (5.)
• And finally, if the height of the terrain is possible to be generated a priori, rivers can be made height dependent. (6.)

Partition Methods

Fundamentally, given a well defined method to generate rivers in an unbounded fashion, if we define some form of partitioning the world up into deterministic and finite chunks, then those same methods can be applied but now in a bounded fashion. As an example, consider the drain to source method described above, but with an additional condition: only traverse upstream within a specific local area. All of a sudden, this method is now bounded. Notably, it does impose a natural constraint: rivers will be local to a given partition, and will never interact across the partition boundaries. In most cases, this is an acceptable constraint.

There are many examples of partitioning based methods which employ various other techniques in addition to some form of partitioning. As a few examples:

1. The unfinished TerraFirmaCraft 2 by Bioxx (Video, Source Code).
   • World generation was changed to generate finite, bounded "islands", and rivers were generated local to a given island using a source to drain method.
2. The Streams mod by Delvr (Mod, Source Code, Explanation)
   • Rivers (streams) are generated (at most) once per square 16x16 chunk region, and can only extend into that region.
3. TFC-TNG by AlcatrazEscapee (Source Code).
   • The world is partitioned into "watersheds", emergent from early stages of world generation, and rivers are generated locally to each watershed.

Partitioning is an important first step in generating rivers via this method, but it is not the only hurdle to overcome. Many partition methods have sizable limitations imposed upon them which may make or break the river generation itself.

Limitations of Scale

The main constraint in all the above methods is one of scale. Ideally, partitions are constructed as large as possible, in order to reduce the effect of partition boundaries, and allow rivers to generate on a large scale. However, rivers need to look good on a small scale (Requirement 1.) as well. Solving these issues almost always takes some form of fractal, but often generating the fractal in such a way that preserves the desirable properties of the river generation is difficult.

Considering the above three examples, and how they each handled this problem of scale.

1. TerraFirmaCraft 2
   • Instead of standard Minecraft terrain, TFC2's terrain generation used large scale hexagons, and closely resembled the Red Blob Games' polygonal map generation.
   • These hexagons meant that TFC2 could generate rivers at a fairly large scale, and map them straight down to hexagons. In addition, it allowed the rivers to be height based, as the discretization provided by the hexagons meant calculating height along the river paths was feasible (6.).
   • This notably did not solve (1.) as such, and sacrificed it (and the overall terrain) for other properties of rivers.
2. Streams
   • Streams uses a very small (16x16 chunk, or 256x256 block) partition area. This area is small enough that calculating height along river paths was feasible (6.), and that generating rivers immediately at block-level resolution was doable, reducing the need for a fractal-like solution to (1.)
   • As a result, Streams' are decently self similar, although long time users of the mod will recognize particular river patterns, as they are assembled from a finite pre-built list of river "pieces"
3. TFC-TNG (1.18)
   • Rivers are generated on a very large scale (on the order of thousands of blocks), and so cannot incorporate height into river generation.
   • River segments are then fed through several iterations of a midpoint bisection fractal, in order to create good fractal like patterns (1.).

Images: TFC TNG (1.18)'s rivers, 4km width.

Conclusion

So, are rivers impossible? No. Are they as easy as the vast multitude of research, blogs, and papers on generating rivers in a finite bounded terrain simulation make it seem? Absolutely not. Are they complicated? Oh yes.

Reference Implementations

Below is an (uncomprehensive) list of various river generation algorithms, along with explanations, source code, or demonstrations where possible. I have also made an effort to evaluate each one against the criteria listed above, to see how each method stacks up.

If you're a modder and you have implemented an interesting river generation that you think would be worth mentioning here, let me know and I'll be happy to add it!

Vanilla Minecraft (Before 1.18)

• Rivers generated using a fractal-like cellular automata as part of biome generation.
• Explanation
• Requirements:
  • Due to a sequence of fractal zoom operations, rivers exhibit good fractal-like patterns (1.).

Vanilla Minecraft (After 1.18)

• Rivers generated using various noise techniques.
• Requirements:
  • Due to octaves of noise, rivers exhibit good fractal-like patterns (1.).

TerraFirmaCraft 2 (Bioxx)

• Video, Source Code
• World generation was rewritten to use hexagonal based, finite islands. Rivers were generated local to an island (partitioning), at a scale that was feasible to use height based generation.
• Requirements:
  • While the rivers themselves exhibit decent large scale patterns, the hexagonal nature of the world is a severe limitation for (1.).
  • All other requirements are met.

Streams (Delvr)

• Mod, Source Code, Explanation)
• The world is partitioned into 16x16 chunk regions, or 256 blocks, and a single river is generated per region using a drain to source method.
• As a result, rivers are quite small, but the size allows them to generate directly with no need for fractal or other zoom methods, and incorporate height into the river generation.
• Requirements:
  • This meets all requirements, with the main caveat that the rivers themselves are significantly limited in size and rarity.

TFC-TNG (1.18) (AlcatrazEscapee)

• Source Code
• During early generation of biomes (using a cellular automata method), the world is partitioned into watersheds along plate tectonic boundaries.
• Rivers are then generated using a drain to source method into a single watershed, with multiple rivers permitted per region. A series of mathematical restrictions are present (line and point intersection, two line intersections), to avoid unwanted river intersections.
• Finally, river segments are zoomed into using a midpoint bisection fractal technique: A segment is split into two along it's midpoint, then the midpoint is moved slightly, and the process is repeated with smaller segments.
• Requirements:
  • The fractal techniques exhibit good self similarity (1.), and the rivers have directionality (2.), the generation method avoids cycles (3.), and the intersection avoidance maintains the graph like structure (4.).
  • Due to the large scale, it was infeasible to incorporate height.
  • Flow accumulation was possible but at scale was unnoticeable due to the resolution of some of the fractals used.