Simplest free algorithm for generating caves and ore in 3D voxel game

Question

I'm trying to find an algorithm that does not require giving any form of credit to use (like perlin noise) and can be used for generating caves under a height map that can make holes in the terrains surface.

The algorithm or a separate algorithm is also needed to generate ores by count of how many ores can be found in a vein and how frequently to place them(They can replace everything previously). I kind of also need the location of dead end(s) of a cave if possible to generate a structure attached to large enough caves.

I've thought about randomly generating points and trying to collide ores with the caves radius but maybe there is a neater algorithm than doing that to make caves more interesting to loot. The algorithm has to be seedable so it is the same every time the same seed is used.

• Theraot: Perlin was designed for 2D, never patented. Simplex is n-dimensional, and there was a patent for 3D covering it (it expired, so it is no longer an issue). And OpenSimplex was created to circumvent the patent. So you can use any of those. However, I think you are mixing things: you do not need to worry about attribution or any other author rights regarding algorithms (only patents). However, you need to worry about author rights of implementations not created by you, including third party libraries you might use. I can't recommend a library, but you want free and not copyleft.
• Theraot: For caves, consider implementing perlin worm. There are questions on this site covering it. I'm also going to recommend you look for talks about using noise in GDC vault, I can't look myself right now, but I'm confident you can find something useful.
• DMGregory: Did you search past Q&A on these topics? We have existing answers describing strategies for generating caves and distributing ore. Even if the existing Q&A doesn't give an exact solution to your case, it can often give useful inspiration or jumping-off points. If you find you still need to ask for help, you can contrast the solutions you've found against what you need, to focus answers on the unaddressed gap, and avoid getting repeats of the same old advice.
• DMGregory: I'd also say you're worrying about proprietary algorithms more than you need to, and it's holding you back. It seems like you're operating under the belief that game development is a minefield of patented algorithms, and that bog-standard techniques that are widely used in games and explained in tutorials are things you need to avoid for fear of requirements to licence/credit it. As Theraot pointed out above, this isn't the case here, and I'd go further to say it's not the case in general. Very little in games gets patented, and many things that were are now free. So, stress less about this.😉
• Opengraphicspros12: I've been reading and watching a lot of content, I forgot to mention I want to do this by chunk if possible so I can keep the speed of the game as fast as possible. Cellular automata and perlin worms are frequently talked about here. I wonder what would make the smoothest cave systems without being too slow to implement or damaging to the terrain

Answer 1

The very simplest approach would be to randomly set each voxel to either a wall, empty space, or ore at the relative percentages that you desire.

float roll = random01()
if roll < 0.3 {
 // Wall
else if roll >= 0.3 && roll < 0.9 {
 // Space
} else {
 // Ore
}

That will result in a bunch of disconnected voxels floating in space though.

So, one simple way to fix that is to start from one of those chunks:

1. Pick the walls and ore that you want to keep, perhaps based on the walls from a previously generated chunk, or just what touches the edges of the chunk. Flood fill from there and keep track of the voxels included.
2. Pick one of the previously generated empty spaces and flood fill from there keeping track of the voxels included.
3. Every voxel that hasn't been tracked already would now be either floating voxels that we want to get rid of, or empty space, so set them all to empty space.

This will often produce jagged edges to the caves which may not be what you want, but it might still make a good starting point.

• DMGregory: Can you clarify what kind of selection rule you have in mind with "based on the walls of a previously generated chunk"? It seems like this algorithm would be sensitive to the order in which chunks are visited. Imagine two players playing on the same world seed, each eventually exploring the same distant chunk. But because of the different routes they took to get there, one encounters the chunk from the north, with no previously-generated chunks to the south. The other encounters it from the south, with no previously-generated chunks to the north. Could they potentially see different contents?
• Ryan1729: @DMGregory I was thinking of basically matching up the walls to the adjacent chunks You raise a good point, this would be sensitive to the order things are generated in, unless some adjustments are made. Off the top of my head, a way to do this would be to have larger super-chunks with predefined edges and a super-chunk is generated all at once. But I suppose that gets rid of most of the advantages of chunks in the first place. I think I'm realizing that avoiding this issue is a major benefit of noise functions.

Answer 2

You want to generate terrain, with caves, and random objects. And you do not want to have to step over the terrain or worry about neighbors.

That means your main tools are going to be n-dimensional noise. Either smooth like perlin/simplex.. Or not like hash-based noise (FNV-1a, SuperFastHash, Murmur3, etc), although I'll not use them for this answer. Which you can query using a seed and the coordinates on the world.

I'm going to recommend you this talk: Noise-Based RNG.

Now, let us take it by parts:

• Use a height map as cutoff: The simplest way to use perlin/simplex as a height map.

  The issue with that is that it result in terrain that is very monotone. There is about the same density of variation of height everywhere.

  A simple workaround to that is to have 3 2D noises: one is high density, another is flatter, and the third is used to interpolate between those two. And that will give you areas that are mostly flat and areas that have a lot of height variation. You can continue to combine noise in this fashion to make something more appealing.

• Cave generation...

  You can use 3D noise and use a threshold to decide what to fill and what not to fill the result from perlin/simplex is more like a sponge, because there will about the same density of holes everywhere. The same issue we had with height but in 3D.

  In 2D you can do a bit better by defining a narrow band between two thresholds. That is going to define contours around the areas of low and high value of the noise, which will be like paths (although results in a very connected cave system). However in 3D it does not result in caves.

  I had to look up what to use for this. And - while I haven't tried it - Curl Noise looks promising. But my proposal is to use Curl Noise.

  To use it - there might be a better way, but this is how I understand it -We are going to need 2 smooth 3d vector fields. So, that is six 3D noises (X1, Y1, Z1, X2, Y2, Z2). Then we compute their cross product. And take its length. Then you apply a threshold over that length to decide what to fill and what not to fill.

  Curl Noise is often used for fluid simulation, so looking it up that is mostly what you find. Here the idea is to use it make winding paths. As I said, I haven't tried, so I hope it works.

  There is also a chance that the best solution is combine these methods. Perhaps two thresholds in Curl Noise is better? Perhaps you should take the idea of interpolating two noises to have different density areas? Try and find out.

• You also said you want to know where caves start and end, which is a problem since your are not advancing your caves. However, you could for each point check the surroundings. This kind of operation can be slow in CPU, but it parallelizes well (in fact, you might have the GPU do it).

• Finally placing things. The simples solution is use a very high threshold on perlin/simplex so only a few spots remain, and place things there. This approach should sufface for placing ores (using 3D noise), or placing trees on the surface (using 2D noise).

  For ores, you probably want to have different densities by height, which you can accomplish by making the threshold a function of the height.

  I also want to bring up that placing ores could be both more realistic and more interesting than Minecraft. Sometimes minerals are found in long layers, because sediments (you could use the same approach to pick the height map for the terrain, but use it to select the elevation of the layer, combine it with another noise to limit it to small pockets). And sometimes they are in columns because volcanic activity (you could use 2D noise to pick the position of the column, and combine that with another noise to generate ore only in those columns).

  By the way, for placing things on a surface, it is also possible to Poisson Disk Sampling per chunk (you might use noise to pick a random starting point for the chunk).

  For structures, similarly, I'd expect them to have different rules depending what structure they are. But hopefully some of what I said helps.

At the end it is up to you to find something that both appealing and performant. However, I hope I have gave you the tools to do so.

Addendum:

I think I get what you mean by damaging the terrain. So here is an idea: take the idea of a threshold based on height to limit the caves that get near the surface. Or use a noise as input for the threshold of the other noise so it can reach the surface but only in some parts but not in others.

I guess too many noise calls are an issue for performance. I recommend you read how perlin/simplex work, because there are shortcuts you might take knowing how you are going to use it (e.g. instead of interpolating two noises, you might manipulate the octaves).