Modular Adventure Design
If you want to run non-linear games where players can make meaningful choices that result in the outcomes even the GM can not predict, you should try using Modular Adventure Design.
Modular Adventures are the polar opposite of railroading - instead of designing a plot (a pre-planned sequence of events the players have to go through in order to achieve their goal), you create a box of toys for the GM and the players to play with.
Design the key elements of the story
- The important problem the players will face, the obstacles that make it difficult to solve, and some potential solutions.
- The antagonist, the goal he's trying to accomplish, his evil plan, and the resources he can use to get his plan back on track when the players derail it.
- Some important characters that will aid the players on their adventure or stand in their way.
- The setting and some important locations where the adventure might lead.
- The clues - key pieces of information the players will need to learn about the story.
But do not pre-plan the plot. Create an interesting situation, but don't define the series of steps the players need to take to reach the resolution, or the resolution itself. You will create those together with your players, as you're playing the game.
Instead of creating the path for your players to follow, you create a map for them to explore, which can take them to many possible destinations in many unpredictable ways.
Integrate these elements into your story as you play
Establish the problem your players need to solve during the adventure, and then let their ideas drive the story forward, let them find their own path to victory.
Don't plan how you'll use the elements you have prepared. If the story goes in an unexpected direction - just reskin the element and adapt it to the story you have:
- If the players don't find the clue written in a note in someone's desk, they can get the same information from a witness in an entirely different location.
- If the antagonist's minions fail to capture the players, he can set up the ambush for them later.
- The monster your players would've encountered in the dungeon might as well be waiting for them in the forest.
- If players don't go to stop the dark ritual at the ancient cathedral, they can have a very similar scene on the rooftops of the city.
Let the players pursue their goal, put obstacles in their way, and see where the story takes you.
Be flexible, build on top of the players' ideas, act as the antagonist executing his plan, react to players' actions, let the story evolve organically, play to find out what happens, and be as surprised by the resolution as your players are!