At the simplest level, procedural content generation can be used to change the door codes and other individual puzzle elements to prevent a user from getting the information off of a game FAQ website or other source of information. But many game plots are little more than dependency graphs, which a sequence of actions must be performed in a particular order. Puzzles can be extended by making multiple parts of the dependency graph randomly placed (e.g. moving the key that opens the door to a random accessible location) or by changing the shape of the dependency graph completely.
Procedural techniques can be combined with Natural language processing to create plots and stories. But human imagination will create a plot out of a sequence of events without necessarily having an underlying plot. This may mean that the complexities of NLP may not be required for many games, as evidenced by the number of Day in the Life posts featured on roguelike newsgroups.
PCG Wiki References
External Links
Procedural Puzzles And Plot Generation defined in The Death of the Level Designer.
Using strategy game AI to create plots - in the The Death of the Level Designer.
Roguelikes and OD&D - John Harris argues that pre-written narratives are not a requirement for storytelling.
Coding Self Contained Reusable Plots - Article and code examples (in Lua) on how to generate random plots.
Tips for Random Story Generation - Joe Hewitt author of GearHead on how to create random story lines.
Procedural Game Narrative - But Do Players Care identifies procedural generation of narrative as one of the top trends of 2008.
