Funnily enough I ran into this exact problem (and I mean exact) some time back. Tunnels were represented by a connected graph. The map itself was a plane made up by a fairly dense grid of vertices. When a tunnel was added, I swept along the path from origin node to the new node, deforming the plane's vertices in a half-cylinder with a touch of randomness to avoid perfectly smooth walls and with a taper as it reached the end. This was done gradually as ants arrived at the "dig" site to "grab" a small piece of dirt to haul it to the surface.
In my case I didn't need a collision mesh as ants would always take paths connected by nodes and never ventured outside of those paths. You could create one as you constructed tunnels fairly easily though.
If you're looking for a two-dimensional solution, one easy way (and the way I started out initially with HGE before switching to Ogre3D) is to create two layers. One layer represents "dug" tunnels, the other a "cover" layer showing dirt. As you create tunnels, erase parts of the cover so that the bottom layer shows though. I've actually got a screenshot of that version: