>Perhaps this is just a fantasy thing, but how did we get to the point where dungeons are typically underground mazes? Building underground is always going to be more difficult than building above ground level, or rather ground water level. If people did build underground, was it mainly as a way to store food because we did not have refrigerators back then?

This might have its origin in catacombs as found under Rome and Paris, which are quite labyrinthine but not built to any central plan.