Walsh did a very interesting presentation on the techniques for storytelling that he used for the latest Prince of Persia game.
If I can manage to summarize it, the idea was basically to have several different layers of narrative, only one of which was obligatory. All the others lurked in the background, waiting to be discovered by players who cared about them. The writers and developers referred to this as storytelling using "ondemand" dialog or ODD. As I recall, the layers basically approximated:
A minimal storyline that the player could not ignore. This was presented in a series of "signposts" -- primarily cutscenes or in-game scenes (like HL2). This story represented the absolute bare minimum necessary to be able to finish the gameplay.
Within each mission or level, certain events opened the possibility of a brief ODD with the player's love interest / accomplice, Elika. For instance, in passing a ruined building or temple, a conversation would have been written that concerned the history of that site. However, if the player was not interested the dialog would not be heard, because that type of conversation could only be triggered by the player pushing a button. Hence the term "ondemand". These ODD chunks had to be independent of time or place or previous dialogs; they had to be discrete and therefore applicable regardless of the player and their play style. Due to the fact that the game environment is 90% lethal, they also had to be a) extremely short, and b) take place on flat ground...
Again within each mission/level, further information that could be drawn out if the player desired it. For example, a line of obligatory NPC dialog could be extended into a conversation by talking to that NPC. Conversations could be launched at any time with Elika; these conversations would be specific to the level and to the story events of that level (unless overridden by the current situation. The game was smart enough not to start explaining the details of how the evil vizir came to power if the hero was in the middle of battling several enemies).
Once a player passed a certain point, these conversations -- whether or not they had been triggered by the player -- were no longer available as they were no longer germane.
Another storyline existed; this was the tale of the the Prince and his relationship with Elika. This one had a beginning and an end, but could be played at any time throughout the game. Basically, if there was a free moment and the player was not fighting, or passing an object of interest, or already discussing a key plot point, the dialog button would pull up the next piece of dialog between the Prince and Elika.
Because the designers and writers could not control when and how the player would accesses the story -- other than the main and unavoidable storyline-- there were a number of difficult constraints:
The dialog had to be worded so that it could be restarted at any time (after the next fight, or six months later when the player picked up the game again).
The only control that the writers/designers had was when they opened or closed access to elements of ondemand story. These had to be carefully chosen and carefully written.
In the event that a player liked the dialog and story, there had to be enough there to keep them from hearing repeated lines even if they were spamming the dialog button. For this reason there were numerous levels of Narrative ODD (OnDemand dialog), Relationship ODD, Ingredient dialog, Fight Taunts, and Foundation dialog.
Many technical (in particular) AI issues had to be overcome to deal with the ODD system. For example the direction that the player's avatar was facing could affect the dialog as could the current relationship and emotional status, and any level scripting; plus the animation had to adapt to these cues as well.
For me this talk was one of the highlights of the AGDC, and I think that there are a lot of interesting techniques and lessons that I can use. Thanks Andy!