An exercise that I got a lot out of is to take an example of the medium which you know well and write out the structure, the'beats.' Like writing a synopsis of a book you've read.
What does the first shot tell you, then the cutscene, the first text on screen, the first environment, the mission. How long into the whole game does the story take a turn? Should it have come earlier? etc.. Find where the high points of drama are, and where does the plot change. A nice big whiteboard can helps for these notes
Choose a game you know well, of course, and you could probly find a complete let's play of it.
Personally I think of game fiction as either premise fiction (the mission never changes) and unfolding fiction (turns out YOU'RE the bad guy), and it sounds like you're going for unfolding.
Just sayin'