River Generation in Procedural Terrain

Introduction:

Rivers are a crucial element in creating natural and immersive worlds in procedural terrain generation. However, integrating them seamlessly into a deterministic noise-based terrain generator presents several challenges, especially when trying to maintain consistent river paths across multiple chunks. This document explores these challenges and outlines a sophisticated approach to river generation that incorporates erosion-based pathfinding, deferred carving, and an understanding of the "discoverability paradox."

Terrain Sloping and River Length Considerations:

For rivers to achieve a natural length—potentially spanning hundreds of blocks—the surrounding terrain must accommodate this by providing a gradual, continuous slope. The challenge lies in avoiding abrupt changes in elevation, such as "cheese holes" (pockets of air or gaps in terrain) and local minima (low points where water could stagnate).

Key Points:

• Slope Gradation: The terrain should gradually slope downward along the river's path. This requires the generation process to be aware of large-scale elevation trends over long distances, beyond the immediate area of any single chunk.
• Avoiding Cheese Holes and Local Minima: To prevent rivers from getting stuck in local minima or passing through unrealistic voids, the terrain generation process should smooth out these features, ensuring a more consistent flow channel.
• Erosion Step Necessity: Since most noise-based deterministic terrain generators do not inherently produce natural flow channels, an erosion step during terrain generation is necessary. This step can simulate natural erosion processes, helping to carve out realistic river paths by lowering terrain in accordance with the simulated water flow.

Propagation of River Sources and Deferred Carving:

To generate rivers effectively, river sources need to be identified and propagated from their initial candidate locations until they reach their respective sinks (such as lakes or oceans). This propagation defines the path of the river and determines which chunks will be involved in the river's flow.

Key Process Steps:

1. Source Identification: During the erosion step, identify candidate river sources based on droplet paths or other indicators of potential water flow. These sources should be at higher elevations where rivers typically originate.
2. Path Propagation: The river path is traced from the source, chunk by chunk, until it reaches a sink. This process involves creating a continuous flow path and ensuring that the river does not terminate abruptly or flow uphill.
3. Deferred Carving: Rather than carving the river immediately, the process identifies the chunks involved and defers the actual carving until after the terrain surface has been generated (buildSurface) but before any additional modifications are made (applyCarvers). This allows the terrain to be adjusted with the river path in mind, ensuring seamless integration.

The Discoverability Paradox:

Rivers must be constructed in their entirety and not simply inferred from local context due to the discoverability paradox:

• Scenario:
  1. The player enters an area where a chunk with a potential river source is generated.
  2. The player ventures away from the area and returns later, expecting to find a river.
  3. However, the river is missing because the generation intent was never propagated beyond the immediate neighboring chunks.

• Resolution: To resolve this paradox, river paths must be fully constructed when first identified, rather than being generated only as needed. This ensures that when the player returns to any part of the river, the entire river path has already been generated, preserving consistency and discoverability.

Tendrils of Chunk Generation:

The concept of "tendrils" of chunk generation refers to the necessary extension of chunk generation beyond the player's immediate surroundings. This is crucial for ensuring that river paths can be traced and generated across large distances without interruption.

Generate the Drainage Graph for a Chunk:

• Each time a chunk is generated (via noise or some other procedural method), construct the drainage graph for that chunk. This graph will represent all possible water flow paths within the chunk based on the terrain's elevation.
• The graph should include:
  • Nodes: Corresponding to each grid point (or a set of points) in the terrain, representing their elevation.
  • Edges: Representing the possible flow between nodes, where edges are directed from higher to lower nodes, mimicking the flow of water.

Stasis Mechanism for Chunk Population

After fillFromNoise() has been called, the chunk enters a "stasis" state where no further population occurs (e.g., trees, ores, or structures). This prevents unnecessary generation when the player is far from the chunk and improves performance during initial chunk loading or pregeneration.

Once the player comes within render distance of the chunk, the population phase (adding features) is triggered, and the chunk is fully populated based on the terrain generated by fillFromNoise().

Find a River Path in the Chunk:

• Occasionally, after generating the drainage graph, attempt to find a river path that fits certain criteria, such as:

  • Steepness: The path should follow the steepest descending slopes.
  • Length: Ensure the path is sufficiently long or continuous through the chunk.
  • Connection: The river path should either connect to a neighboring chunk’s river or terminate naturally at a local minimum.

• Use algorithms like steepest descent or lexicographical order to determine which path in the drainage graph fits the river criteria.

Dump the Graph Data:

• After the river is carved, discard the graph data for that chunk. This avoids unnecessary memory usage and ensures that only the carved terrain is retained.
• This is especially important in infinite worlds, as holding onto graph data for all chunks would quickly become computationally infeasible.

Pregenerating Terrain Efficiently

When pregenerating chunks (e.g., a 2x2 region area consisting of 1024 chunks), the mod only generates terrain up to the fillFromNoise() stage. This keeps the rest of the chunk generation in stasis, minimizing the time and resource cost. Based on typical performance:

• Average chunk generation time (up to fillFromNoise()): ~100 milliseconds per chunk.
• Estimated time to pregenerate a 2x2 region (1024 chunks): ~6 to 8 minutes, depending on noise complexity and hardware.

This approach allows world generation to be deferred for chunks that are far from the player, reducing the overall impact on server performance or world loading times.

Delayed Feature Population

• Once the path is selected, stage the river for carving along that path using the river carving algorithm (e.g., inverse bell curve, parabolic channel, or another custom function).
• Adjust the terrain along the path by modifying elevations, removing certain blocks, and filling with water blocks as necessary.
• Once a chunk enters render distance, the rest of the population (including biome features, structures, and vegetation) is triggered. This lazy loading mechanism ensures that resources are not wasted on generating chunks that might never be visited by the player.

---

Contributing

Feel free to submit pull requests for new features, optimizations, or bug fixes. Contributions are welcome!

License

This project is licensed under the MIT License - see the LICENSE file for details.

---