16
$\begingroup$

I know a few algorithms to build an elevation map for a planet, but most of them do not take into account the underground aspects of the planet (caves, tunnels, ...).

Are there any algorithms to take care of this? Are they used only after an initial elevation map has been created or could they be used jointly to create a cave/tunnel network more efficiently?

Any pointers to algorithm descriptions, surveys or working libraries are welcome!

|improve this question
$\endgroup$
  • 2
    $\begingroup$ Aren't caves based on underground rivers, as well as weak rock where water erodes the rock away? So there wouldn't really be an algorithm. $\endgroup$ – DonyorM Sep 22 '14 at 12:39
  • $\begingroup$ Not only, some caves are created by tectonic movements... But, my point is not really to be as realistic as possible. I would like to know what are the existing methods (so, erosion is one as you suggested). $\endgroup$ – perror Sep 22 '14 at 12:43
  • $\begingroup$ Glad I didn't post an answer. I move to quickly sometimes. Always good to learn! $\endgroup$ – DonyorM Sep 22 '14 at 12:50
  • $\begingroup$ As you noted there are several different types of formation types, and the features of each vary depending on the type of rock they are created in. I doubt you are going to find an algorithim that manages to encompass all of that on a planet wide scale. $\endgroup$ – Chad Sep 22 '14 at 13:11
  • 1
    $\begingroup$ This answer on stack overflow might be useful as a starting point for someone looking to write an answer, as a starting point for research. $\endgroup$ – trichoplax Sep 24 '14 at 21:47
10
$\begingroup$

This sort of thing can very easily be "fudged", there is no need to simulate the world and erosion as you care more about things looking good.

There is a simple example here: http://hub.jmonkeyengine.org/forum/topic/how-to-approach-random-cubic-cave-generation/

Basic algorithm:

  • start with a random point and random radius using some scale factor.
  • calculate a random number of branches of some random length and random width based on the scale factor
  • create points at the end of those branches with random size and scale factor based on local scale factor
  • recurse to a maximum depth

There is a long and very informative GPU Gems article here talking about procedural terrain generation:

http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html

The details are too long to pull out into this answer but the root idea is that it combines different noise functions to dynamically and procedurally generate terrain like this:

Example 1 Example 2

|improve this answer
$\endgroup$
  • $\begingroup$ Extremely interesting technique (that I wasn't aware of!). Thanks for sharing ! $\endgroup$ – perror Sep 26 '14 at 13:15
4
$\begingroup$

You might be able to use a cellular automaton to simulate cave formation, not in the simple Conway's Game of Life sense, but by programming the automaton to simulate earth of varying densities which are randomly placed in a 2D or 3D grid, fluid, which might be water or magma, and air.

By setting the rules correctly, water would come from above at random intervals and areas and erode the earth, weakening each cell until it disappeared, or it could cause rock deposition in empty spaces (stalactites and stalagmites). If you had a 3D simulation, you could also add gravity, requiring that water always move horizontally or downhill unless the rate of flow was restricted at some point (at which point it could rise upstream of the blockage), or unless it got sufficiently hot.

Gravity could also be used to determine collapses - if insufficiently strong earth is asked to span too great a distance without support, it would collapse.

Magma would come from beneath, originating from a hot spot, whose intensity and position of maximum heat may vary over time, and magma might solidify to form hard rock, or subside again to leave cavities (depending on the type of the hot spot and/or random factors), and it would also heat water, making it rise.

This wouldn't necessarily be quick to program, and wouldn't be particularly quick to run, but done properly, could produce very realistic results.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ At the other end of the scale, for generating very basic map views of caves, there is a very simple cellular automata approach here $\endgroup$ – trichoplax Sep 26 '14 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.