Exposition Expose.

From the opening screen of Spelunky, everything is randomly generated. The story too, although it is only three lines of setup.

It goes to show how little story is actually needed to make a good game great. Three lines transforms what might have been a fun little pointless platformer into what feels like an epic story, and the three lines aren't even related to what happens in the game, other than for exposition.

The exposition in Spleunky works through all the old movie cliches. Fate guiding one's steps, father's last words, mysterious voices, native guides, and so on. It fits the game's feel, diving into an underground tunnel to search for buried treasure so well that it makes this game feel like an old action movie - indiana jones in particular.

One procedurally game I particularly like is ADOM, Ancient Domains Of Mystery, and while the game is fantastic in many ways it's exposition is one of the simplest of them all, a fixed bit of information tied to a randomly generated story filled in with bits from your character creation. You were born in X, you grew up Y, your parents were Z. You trained to be a fighter and left for the draklor chain where chaos was threatening to destroy the world. A great story, and simple.

Procedurally generated games without any in-game story, like rogue or nethack always feel lacking. They become a world, and while adventuring through them is a number of rewards in and of itself, it's never quite satisfying. Why did you go into the Dungeon? Who were you before? Are you a champion of justice, a madman, or a greedy delver? Nothing is answered without just a touch of exposition.