After some more research I encountered the Marching Cubes algorithm.

This take the input as a 3d grid of density values and generates a smooth surface where the density crosses 0. It is much more robust than my height field inspired implementations.

This demo just takes 3d perlin noise as the input for the marching cubes algorithm

Ill upload some binaries later ...

I spent a lot of time designing this version. The main feature I wanted was to allow multiple layers of tunnels which means moving away from simple heightmaps.

I spent a fair amount of time on the idea of having multiple heightmaps but ran into all kinds of problems when trying to seamlessly connect two of them together.

This version uses the idea of heightmaps but does not use a contiguous plane.

Geometry is added with a 'brush' which is a sphere in this case but could be any convex shape. The mesh is quantised in the x and z axis to make the the mesh simple

so I didn't have to deal with splitting polygons. There are still some bugs with this though.

This was my first attempt at a procedurally generated 3d cave system.

It uses two heightfields for the ceiling and floor and the geometry divided into cells. The generation algorithm creates a line that the tunnel will follow which uses a 'wander' steering behaviour for the smooth randomness. The walls are then set at a pseudo random distance from this line.

The path also has a branching factor, and occasionally creates larger caverns.

The main problems it encounters are to do with the fact there can only be one ceiling or floor, so when path cross at different heights you end up with a chasm effect. It can create some interesting rock formations where there are a few paths in proximity.