Last issue I discussed how you can see a Story game as a particular kind of Dungeon. Of course, you can also see the dungeon as a particular kind of story. Even better, you can combine the two different game types - sparking one of the other.
You might already be doing this of course, putting story elements in your dungeon, or perhaps little dungeons in your story. Even if you do, doing this consciously can make it much easier running your game.
Quests: a Story in your Dungeon
If you are more comfortable with dungeon, endless corridors with dangerous denizens, and fiendish subterranean complexes, you'll probably want to start there. Your party would explore a mythic under-earth place, perhaps with some sort of overall goal in mind - perhaps not. Often, you'll just delve toward the deepest level like in a game of "Dungeon Hack" or its modern variant "Diablo".
Stories typically enter such a setting as little "quests". In a room you may chance upon a patron asking your services, or on a dying creature with a treasure map, or even an enemy demanding something special before you may pass. Each of these encounters may spark off little stories, or puzzles, depending on how you use them. These are quests.
Quests only become stories once you also insert scenes. Computer games do this all the time, as "cut scenes" between the action. But these are seldom giving any choice to the heroes, or their players. What you want in a game is some freedom of choice, and choices that matter.
Scenes are a kind of Encounter
Your quests will be small stories, with a beginning and an end, and some developments in between. Each development is a scene - and each scene, is a kind of encounter taking place somewhere. A story can take different paths, and you might want to think up new scenes as you go along - but they can all take place in your dungeon. You just need enough space to have your story in.
Suppose your heroes encounter a band of orcs, who have a prisoner. That's your opening scene for the quest - a encounter with the orcs. Once the heroes freed the prisoner, and either killed, captured or chased away the orcs, the prisoner is very thankful and reveals he was searching a treasure here. He had a map, but he had to hide it while the orcs were chasing him - that's scene two. The heroes may now navigate to where the map may be or first do other things. But once the heroes get to the point where the map is, you can trigger scene three: it's now guarded by a horrible wandering monster, or perhaps it has fallen down a treacherous chute. Once the heroes have the map, they will be able to study it, and this might be scene four. It could be for example, that the heroes now recognize the area of the map, and realize it is a very dangerous area they have run away from before. This may spark of an interesting discussion of whether they want to go there at all.
And so you could spin your little story on further, while in between your scenes the heroes explore the dungeon and have their regular encounters. You may find that your players live up every time a new piece of the story appears, and that it gives new direction to your adventures.
Scenes are Challenges
Each new story element should pose some sort of choice, or challenge. Perhaps the heroes find that the prisoner they freed was part of a team he betrayed, and that that team is also out looking for the treasure. Suppose they now encounter that other team - whose side will they choose?
Also, each scene could end differently, and the story could bend in many ways. The map could end up damaged, or stolen, the prisoner wounded mortally, the orcs might return later in greater force. You don't have to tie down the storyline beforehand (better not!), and you don't have to be strict about where things should take place either. You can also insert a new development of a quest whenever you feel the game slows down, or the players need some change of pace.
An Overall Storyline
Once you are comfortable with quests, or perhaps before, you may want to have an overall storyline to your dungeon too. This may be a main quest, that drew the heroes into your dungeon in the first place. Perhaps they look for a long lost treasure, a long lost race, or a prisoner that was taken in deep. Perhaps they want to defeat an ancient evil that hides on a deep level, and now sends out it's minions to terrorize the world above - this is naturally the classic dungeon theme.
An overall storyline would have at least one opening scene - but you might have one for each new session you start, just to remind your players why they are there. An opening could be an encounter with the minions of the evil mastermind - an assault, a surprise attack, or even a negotiator, or a victim.
During the game, you would have developments. The heroes might beat an important minion, or lose a good friend. They might find a special weapon to fight their enemy, or discover a map proving a new route to his lair. They might befriend new allies in their quest, or free prisoners with new information. Each of such scenes will not only add spice to your dungeon, it will give direction to your game and your players. Most importantly it will enrich your game and make it more fun.