Ages ago I started work on, not so much a game, more an "interactive storytelling experience" (here I go wanking away) called Fork, which was based around the "gameplay" of a Japanese-style visual novel. The idea was, you had to make 6 choices, and each choice branched the story. The player was given as little detail as possible at the start, and each choice of action they made added detail that altered the context of the events. For example, you started off in a hospital reception area, and the first choice was whether to sit down and wait or walk down the hall to explore further. Choosing to sit implied that the player character understood the hospital to be functional, and would lead to the stories involving visiting sick friends, seeing a doctor or identifying a corpse. Choosing to explore implied that the player character was more confused about their situation, which led to stories in which the hospital was abandoned or closed, and you were there for various illicit reasons.
I never finished that project, partly because it would have involved writing 64 different stories, partly because the very fact that I was making a visual novel made the game designer part of my psyche want to tear itself out of my brain and throw itself into the fireplace. But I'll tell you what Fork definitely wasn't: it wasn't non-linear storytelling.
I hate when people bring up the whole concept of "non-linear storytelling," because there's no such thing. Stories are linear by nature, it's like asking for a cat with opposable thumbs. Fork would have just been a choose-your-own-adventure book you had to read 64 times to see all the content.
In my review of Heavy Rain I mentioned that I'd gone through the game expecting the plot twist of the killer's identity to change depending on what decisions you made. Because, damn it, that's what I would've done. Silent Hill 2 did something like this (and Silent Hill: Shattered Memories apparently does it even more, but I would remind my bothersome correspondents that third party Wii titles always seem to have legendarily long localization times and isn't out in Australia 'til some time in April) - which ending you got depended on subtle differences in actions throughout the game that implied different things about the protagonist's state of mind; running around with frequently low health made it more likely to get the suicide ending, etc. It's a great example of marriage between gameplay and storytelling that also heightens the player's paranoia once they realize the game is wordlessly judging them, which suits horror games down to the ground.
Getting back to Heavy Rain, though... I guess I just don't see the point in this kind of interactive narrative if the choices we can make are merely altering specific events rather than the actual context. Surely the whole point of having the story play out differently depending on player choices is to add replay value, and once I realized that the important twists of the story are always the same, then what reason was there to play again? Going back to watch the alternative outcomes of certain scenes feels more like watching the extra features and alternative endings on a movie DVD.