Using some GPDL scripting and $SetWall(), it's possible to generate random dungeons, at run time.
There are many methods to do this - I'll start off by describing the "drunkard's walk" method
http://www.roguebasin.com/index.php?title=Random_Walk_Cave_Generation, which builds cavern like dungeon maps.
To mark a square as having been dug, I set the background to something non-default.
First, decide how many squares you're going to dig for your cave. Pick a square and dig there.
(1) Take one step in a random direction to a new square
(2) If the square is not already dug, dig it and add 1 to the count of squares dug
(3) If we haven't met the goal for number of squares dug, return to (1)

This gives us rough looking maps, like caves connecting cavern, although the effect is lessened by the relatively small number of squares visible from the first person perspective in this sort of game.

It also guarantees that every part of the dungeon is reachable.
Wall based maps like dungeon craft's need a post-processing step to put walls between the solid rock and the caves.
So loop through every square on the map, and if it's dug, then check each direction to see if the neighboring square is solid rock - if it is, put a wall between the two.
