We've certainly seen things like Oblivion where you've got all the side quests that make the world feel a lot better.
The Darkness touched on that a little bit as well, and quite a few games have elements of what you might call 'side gameplay' that help feed into the richness, but they don't fundamentally alter the story: games like Deus Ex where you had branching story, and there was some slight branching in games like Indigo Prophecy. So, I think all of those things are positive, but a lot of them felt, to me, like they hadn't done the trick.
The problem is, I felt they didn't quite deliver on their promise. Their promise is not actually the fact that you can play it through and have a different story, because that sounds fundamentally irrelevant -- you play a game through and think, "So what, I could have done things slightly differently". That's not the point. I find that once you try playing games in a slightly contrary way, you end up finding a lot of blind alleys, things that you just can't do, which I think is tragic. If you offer that promise, you've got to deliver on it.
So it's not so much the fact of the story being able to go lots of different ways. It's the fact that you can try a lot of different things and you'll find a way through. It may not be what you anticipated, but there is a way through. I think it's that sort of thing -- being able to experiment with the world in a fun way.
I mean, there's quite a bit of variability, not in the story, but in the way a level's played in Call of Duty 3. But if you embraced that and tried playing around, you'd find quite often -- it happened many times to me -- that you'd finish a level, and it wouldn't terminate, because you'd done the wrong thing last. I found that really frustrating. You'd just run around and find that you were stuck.