Interactive stories are hard. I'm not talking about stories with interactive challenges, a la Uncharted, Metal Gear Solid, Half Life, or countless others. Nor am I talking about "story machine" games in which non-scripted stories emerge from the gameplay, such as The Sims or Civilization. I'm talking about scripted stories in which the player's decisions and actions actually influence the events and, often, the conclusion of the plot. There are many games that attempt this at a surface level, such as Infamous, Fable, and Mass Effect, though very few attempt truly interesting interactive narratives.
In Jesse Schell's book The Art of Game Design and in his game design class, he identifies five big challenges of interactive storytelling that make telling interactive stories really hard. I'll briefly summarize each challenge and then provide some possible ways to tackle the challenges.
1. The Combinatorial Explosion. That is, every time the player makes a choice in the story it branches into two possible paths, and every choice after that makes the story branch again. So a story that is completed after five choices would need to have thirty-two different paths scripted and implemented by the storytellers. That's a ton of work for a story with only a handful of choices, and that's assuming each choice is between only two options, which is rarely the case in real life.
One such possible solution is to make the branches merge back with each other, which would greatly reduce the total number of paths that would need to be implemented. Unfortunately, this makes the individual choices much less significant since it is likely that both options ultimately lead to similar or identical conclusions. While this may not be apparent on the first play-through, anyone playing multiple times will quickly realize that the choices aren't significant and the story suddenly becomes much less compelling. For example: The recently-released game Heavy Rain has a scene in which the player can either befriend or offend a non-player character. But after that scene, the player then defends her from an abusive boyfriend, thus cementing a positive relationship between her and the player. This essentially nullifies the choice to befriend or offend her in the first place. Being a curious player, I played through these scenes multiple times and was ultimately disappointed by how meaningless the original choice was.
The better solution, I think, is to use chapters in which the choices made in one chapter only affect the outcome of that chapter and not any other chapters. For example, let's say that we're making an interactive narrative with nine choices. Normally, that would be 512 total paths required. But instead, let's make a story with three chapters, each with three choices. That's eight paths per chapter, which works out to 24 total paths -- a far more manageable number. Dragon Age is a good example of this system in action: There are multiple storylines running throughout the game, and the choices made while playing any one storyline usually only affect the outcome of that particular storyline.
The potential downside of this latter solution is that the choices will still be less significant because most of them do not affect the ultimate outcome of the story. But if the individual chapters can be made compelling stories in of themselves then the choices therein will still be compelling, even if they do not affect the outcome of the entire narrative.
2. Good stories require unity. That is, a good story is tightly woven with a beginning, middle, and end that work together as a cohesive whole. The challenge here is in creating an interactive story in which every possible path through the story works as a cohesive whole. This problem is related to The Combinatorial Explosion in that, while it may be feasible to make each of a few paths cohesive, making all of a huge number of paths cohesive is impractical.
Since this challenge is so similar to The Combinatorial Explosion, the solution is also very similar: Use chapters that each have few choices and can be made individually cohesive.
3. Multiple endings disappoint. Jesse argues that this is because players viewing one ending will feel like they aren't viewing the best or intended ending. This is certainly part of the disappointment, though I think that the feeling of having experienced an incomplete ending is more important. In a story with multiple endings, both endings are thought of as being part of the story, not just the ending chosen by the player. This reasoning can also be applied to multiple game paths in general -- picking one path over another will cause a feeling that part of the story is being missed. I had this feeling after finishing BioShock for the first time: BioShock has two endings, and the player views one depending on how many little sisters he saves or harvests. Since saving and harvesting the little sisters occurs throughout the whole game, viewing the other ending requires playing through the entire game again.
The solution, I believe, is to make it easy to "rewind" the game and explore the multiple paths and outcomes. Do not force the player to play through the entire game again -- let them load the game to just before making a critical decision. (And please auto-save at that moment.) Ideally, the player would be able to access a branching tree of all the significant decisions in the game and the outcomes that have been explored, and they would be able to easily jump around the story to try all the possible outcomes. In that way they can experience the whole story without wasting time replaying parts, and they won't feel like they're missing any part of it. One of the games that comes the closest to this ideal is Pheonix Wright: The court room scenes in the game are interactive and allow the player jump around in time to try out different sequences of actions in an attempt to produce the desired conclusion.
4. Time travel makes tragedy obsolete. That is, the conclusion of a story will lose its its inevitability if the player can simply travel back in time and change the ending. There's really no way around this problem other than being aware of the kinds of stories that don't work well as interactive stories -- that is, pretty much any story with whose drama relies on its ending and in which the characters have the power to affect this ending. For example, Romeo & Juliet would lose its power if the player could alter the course of the story to prevent the tragic deaths of its protagonists.
But stories in which the ending is not crucial to the drama could indeed be very compelling interactive stories. For example, Hamlet may actually work well as an interactive story. Changing Hamlet's decisions and exploring the consequences of those changes could be really interesting. Hamlet may work better than Romeo & Juliet because the drama of Hamlet comes not from its tragic ending but from the series of interesting choices that Hamlet makes.
5. Not enough verbs. That is, in any remotely-realistic interactive story it is nearly impossible to fully implement all of the choices and actions a character may make. Classic adventure games, which make the most explicit use of verbs to perform actions, typically have a very small number of verbs that the player can use to control the actions of the character. Even text adventures, which attempt to interpret the text typed by the player, can only understand a limited set of verbs.
The solution is not to implement a huge number of possible verbs, for at least several reasons. First, implementing a huge number of verbs is technologically infeasible. Second, The Combinatorial Explosion problem will rear its ugly head if they player is given the freedom to do just about anything he chooses. And third, a huge number of verbs will confuse and scare the player out of playing the game.
The best solution, I think, is, in any given situation, to present the player with a few possible actions that are more compelling than anything else the character might be able to do in that situation. For example, let's say that the grass in Bob's lawn is way too tall. In real life he could buy a lawnmower or pay someone else to mow it, but in a game, why would you choose to do either of those things if you are given the options to either torch the lawn with a flamethrower or let a heard of triceratops graze it into submission?