# Procedural Cave Generation

In our post about generating terrain, we talked about how the terrain within each cave will be generated procedurally. The same concepts apply to actually creating the caves as well.

The way we do this is using an algorithm called “Perlin Noise.” Perlin Noise is pseudo-random, and as such has two important features that we use:
1) one seed will create the one result: so no matter how many times you re-generate, as long as you use the same number to start, the result will be the same. That means that if we want to create a huge length of cave and can only do so in pieces, the pieces will fit together.
2) Perlin Noise can generate noise infinitely, in every direction, forever. If we want to, we can extend our cave system in any direction we want, and each cave will still be new.

So the way we actually create the caves is by following this guy’s suggestions. To paraphrase, we start with a solid cube of many many voxels. From there, we run it through a Perlin Noise filter, getting something awkard like the image on the left.

Next, those awkward lumps get subtracted from the solid, so you get something that looks like the image on the right: a solid area riddled with caves and things you can explore. As a note, he has added hills and such on the top of this area – we don’t do that because the player spends his/her time inside the caves.

So above are images from the walkthrough (seriously, check it out – he covers it really well), and below are some of our own results, as shown from inside the caves.

From here, we’ll be able to manually
modify the caves so they work better for our puzzles, and then we will apply the smoothing algorithms, then the same noise algorithms to the surfaces themselves to give the cave a rough, natural look.

More on that later!

# Generating Terrain

In this post I’ll try and describe how our terrain generation works. We want the level designer to be able to carve out a rough shape for their cave; we do this using voxels (voxels are like 3D pixels – where a pixel is a small portion of a flat picture, a voxel is a volume element that represents a section of space, traditionally in cube form). With a couple of small hints, we hand the rough-cut level off to the procedural phase. During our procedural phase the following will happen:

• We’ll apply noise to randomize and warp the surfaces (because cave walls aren’t smooth).
• The surfaces will get subdivided so that they can be pulled in, pushed out, and generally messed with to smooth the edges of the noise – so the cave walls look natural and lumpy, rather than perfectly smooth or awkwardly jagged.
• Using a new modeling algorithm/simulation, speleothem will be generated (more on that later).

What we’ve got working is the voxel editor, and recently the smoothing.
I spent my time over the holidays implementing Catmull-Clark Subdivision. This is a process where a mesh is subdivided into smaller meshes, while smoothing out the corners. On the right, you can see our smoothing algorithm at work – instead of the sharp, 90 degree edges you’d expect from a voxel, the edges are visibly rounded.

Speleothem is a word I enjoy saying, and do so on a regular basis (to the annoyance of others).
Speleothems are formations created through the accretion process; accretion is the process where water passes over a surface, leaving something behind. Examples of speleothem are stalactites and stalagmites. As the water flows over the surface it leaves behind trace amounts of minerals, that build up into those formations. We have a nifty algorithm that will simulate this accretion process, and we’ll be implementing it soon.

Of course once the terrain is generated, objects, crystals, and characters are dropped in at the next stage of level development. The level is playable (albeit not that pretty) in the voxel mode, so the level development will probably leave the generation phase for when the levels are done.

More on this stuff later.