Non-linear stories within games

Non-linear story lines have been used in games for a very long time. There are 3 different types - branching storylines, non-linear level design and sandbox mode.

One example of non-linear game play is a game called Agarest: Generations of War. The various ways of playing the game can be seen in the diagram below - taken from here

As you can see there are various ways of playing through the first part of the game. Which ever way you choose to play you end up at the same point at the end. However, the way you play the game does affect whether you can reach the True Ending.