Ok, I am developing a game that focuses around being in caves. For my caves I would like them to be limited but generated randomly. To fit my game’s “Pixel Art” style of graphics I would like the caves to be made of small cubes. Would you recommend any algorithms to generate a cave. I looked in to cellular automata but I am not sure if that is my best approach.

What kind of caves do you need for your game?

Well I would like caves which are 3 dimensional. I need my caves to go downwards the farther it goes and branch off every so often. I do not mind if I have small caves as my overworld will connect multiple caves together. I would like to be able to roughly influence max depth into the earth as I will have more precious metals in the deep.

Is it the random cave layout you struggle with or how to them carve them out in a pleasing way?

A bit of both. I could probably calculate a random two point connect via line of blocks. then choosw to turn a bit and do the same thing. Making them look “natural” is another problem. I could randomly pick a width and transition between them. Then sometimes make a fork in the cave. Then stopping generation after a predefined depth. I havn’t tried these strategies yet. But I don’t think they would look very “natural” but look more like a man made machine dug it out. Of course ore population isn’t accounted here but should be easy enough to implement after the cave generation portion of code is written.

In Mythruna, I get pretty realistic caves that are fun to explore using a sort of inverse isosurface approach. (Think subtractive metaballs and rods.)

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

The structure:

Each “point” is like a metaball. It has a strength and a cutoff radius. For any 3D point you can determine the “strength at that point” as a function of distance to the point… except outside the cutoff radius it’s just 0. It’s not strictly necessary to have a clip radius but it can be worthwhile in optimizations.

Each “cave” is like a metapipe… it’s a line with a strength and radius. It works similar to the point except instead of calculating a distance to a point you are calculating a distance to a line segment (JME has methods for this in the LineSegment class, as I recall.

So once you’ve laid out your caves randomly using the algorithm above, you merely sample all points in the area to find out if they are “inside” or “outside” the caves based on a strength threshold. Cell strength is the sum of the strengths of all points and lines that affect the point. This creates very natural transitions. On the wikipedia page you can see examples of how two balls that aren’t quite touching can still create a smooth transition using this method: http://en.wikipedia.org/wiki/Metaballs

…adding in lines just improves the “caveness” so you get long twisting caverns depending on how your algorithm decides to assign branching randomness. (For example, in my case if the cave radius is small then the change of another only 1 or 2 branch point is high… with the small odd chance of another larger point.)

Optimization:

If your world is broken up into zones then you can optimize this part by sorting the points and lines into affecting zones based on their clip radius. That way you don’t have to check all points and lines when calculating the cells in a particular zone.

That will make very smooth caves with smooth transitions. And if the caves back up on themselves then the joins are very nice. You can also use the signal strength at a given point to affect the randomness. For example, if your signal strength is within threshold and threshold-someValue then you can randomly choose to keep or remove the point using threshold-someValue as a multiplier.

If you worry about floating blocks you can keep that someValue really narrow or post filter the results.

Mythruna actually has a few more structures than just points and lines but those are enough to make pretty cool cave systems. The nice thing is that it’s also really easy to manually define some cave structures and still have them look rough and natural.

…another side benefit is that using negative strength points and lines you can carve rock into empty space, too. Could potentially be used for adding back things like natural bridges, stalactites, or stalagmites.