Ok so this is something that i have been thinking about quite a lot recently.

now in yer "traditional" game - the story can and probably should be linear - the writer is in direct control of what players will discover, when, and how.

but in open world games, this is not the case.

Personally I have yet to see an open world game - that has a genuinely "open world story".

Even in games with open worlds, it appears the story is very much written in a linear way.

which makes me wonder - is it even possible to really write a truly open world story?

to compare to a book - a standard game would have a story where you start at page 1 - then read till page 100.

an open world story - would be a book where you read the first 3 pages in order, but can then read pages 3 to 97 in ANY order you chose but still have the story make perfect sense, be immersive and engaging.

is this even possible?

for the variables alone will surely become exponentially complex.

In open world games - the world is open, but the story is not.
you can for example go to the super secret hideout where the final battle takes place - but it will probably be a deserted, empty, shell

we don't see this as immersion breaking per-se because we have it as an established flaw in open world games, we accept it.

is it possible for me to kill the final boss at the start of the game (no doubt on 2nd playthru ) and still be able to enjoy the rest of the story?
The story / game world would have to adapt to this.
It's an extreme example - about as extreme as it could get,
what would the rest of the story even be?

Well, simply put, yes it is possible.

The story of the character and the story of the game are very different aspects. You seem to consider the game's story as the main story, and understandably so; the game is started and ended by it. Without a game there is no character to continue the individual story.

However, consider the ending of Fallout 3. Just an announcer recapping everything that the character had accomplished in his journey; what he did here, what he did there, and the consequences of these choices. These were not solely the events that moved the game's story along (such as visiting Galaxy Radio or the decision to purify/poison the water), but were also sidequests and sometimes just the outcomes of events in certain areas, sometimes even acknowledging that the character had failed to go there and have an impact on that particular story. In this case the character's choices regarding the main story are overwhelmed by their other choices throughout the game.

I doubt this is exactly what you were looking for as this is more a collection of self-contained stories that are forcibly interwoven, and yet thats all any story is. Just like every person every NPC has their own story, they just happen to be sidelined by whoever the camera follows, its how we interact with them that influences theirs and our own stories.

Btw,

Look into the works of B. S. Johnson

The problem with this is just the sheer amount of reaction you'd have to give each character.
If you've already smited some great evil, then a lot of your other quests would be killing one dude, and then everyone else just running away. You'd have to make every deed influenced by every other deed, in a way that is not arbitrary or unbelievable (people will have different reactions).

Maybe 'finishing the game' would actually close off a lot of missions. You're the saviour of the world, can't be delivering messages for the milkman anymore. Maybe there would be a degree of prestige involved, so you have to earn the trust of lords at the beginning, but once you're well known you would be requested to resolve all manner of issues from diplomacy to all out war.
If it's truly open can you be evil? Will you be refused work if you've betrayed a group before?

Finally, could you do all that, and still make the story engaging?

The only way I can see it working is if each conflict within the land is engaging and influential enough that over time entirely new plots can form (I.E you help a town so much it undergoes a great economic growth, dissents from the capital, fractures the state, and ultimately overthrows the king, but it's not one individual mission, it just happens because of each bit before it.)
OR
You make the game abstract. The game is about who you (or your character) are, rather than what they do. It's a series of somewhat connected events that slowly cause the protagonist to realize different things, and the ending comes once they are swayed into a particular position. (I.E the death of a loved one could cause one to go mad, saving a kingdom could cause them to retire, losing might drive them down an evil path, etc etc) but this wouldn't really be sandbox, it would be a linear ending to a sandbox game.

Your choices are unbelievable complexity, or a game where you can sway back from good to evil, and never learn anything as a character.
You could overcome this by having the character refuse certain actions (If you've been objectively good the whole game you can't suddenly be evil) but then it's not as open as it could be.

At the end of the day, even if you could make the story open, the player would have to follow self-created rules or else they'd ruin the plot. A saviour who tea bags old ladies and feels no remorse is a pretty shoddy saviour, especially if no one complains to him about it.
So it's maybe doable, but you'd have to show your player a lot of faith.

See the thing is I can see a way of it working - on a small scale.

in a small open world.

the game world is a Hotel

someone has been murdered - the game starts as you find a body - there are lets say 5 other people in the hotel and yourself.

there are also 5 "clues" you will need to find to know 100% who the murderer is.

equally you can at any point go up to any suspect - and interrogate them with the clues / evidence you have so far.

in this way - the beginning is set (there is a murder - you find the body) the ending is also set - you catch the murderer / he gets away.

but regardless of the order you find the clues / information in - still tells the same result.

so perhaps you find out he is a wealthy billionaire first - and that he was visiting a prostitute in the hotel 2nd

or the other way round. - you still get the "revelation"

now - would you be able to apply it to something other than a murder mystery?

See, that's a non-linear story, but it's not an open world. You still only have the one mission, and your impact never carries from one mission to the next.

I attempted to design a death note game some time back, and for all intents and purposes it is a semi-non-linear open world game, and the reason I can't work on it is how staggering creating that was. Essentially you could lose in any mission, or shoot yourself in the foot for a mistake you made near the start, and the end was dependent on all of the variables in the entire game. I knew the options and story, but keeping track of it all was like writing 100 different games at once. It was like Mass Effect, but the ending actually mattered

Like I said, it could be done, but the effort you put in wouldn't work in respect to the result you get.
In a linear game you just make the one path, in a non-linear game you have to make every path, which means more work per hour of gameplay.

Perhaps, and this is a stretch, a game could be made that generates events and missions based on previous actions. The technology exists to do this, and it would be much easier to do (for a very skilled team, mind) the only problem is whether the plot would still be involving. It could end up feeling cut and pasted, where you do virtually the exact same mission, or see the same cutscene, or have the same dialogue, and the names and places have changed as if someone has madlibbed you previous exploits.

OR, it could be a small open world. If it's small, it's easier to do. Basically, the less impact the player can have, the less you need to make the world react, and so the easier it is to do.

It might be a better idea to design a smallish world, and then think of how to make it non linear and open, but still engaging. Keep with the detective thing maybe, but have multiple cases. Track how many cases are successful. Unsuccessful cases might come back later. Have the chance of a certain character experiencing a crime be tracked by a variable, but every character could die. This could be a world where the 'main' villain is killed off in act II by some random mugger, and you spend most of a quest just going "holy fuck, this guy was evil, good thing he got stabbed for a rolex"
Again, it would have to be 'madlib' style missions, where names and motives and weapons are swapped out, but you'll often be feeling like you've done it all before.

Basically, difficult, not impossible. Build a world, then address whether it would be possible or not, and to what degree. You'll never get perfect open non-linearity, but you can approach it.

The issue with a non linear game, is that you need to think of EVERYTHING. You need to think AS the player, you need to think outside the box. As not all gamers do things in the same way. What you are describing above is similar to Dishonored. In which you have open world within a single Level. It is RATHER difficult and you have to consider all the options for it to be truely non-linear. I wish you luck

It could also work in a horror game.
An open path horror game is usually a whole lot more unnerving, especially if the focus is on escaping, not fighting. Make the player question what is real, keep it abstract. Their world flashes between real and horrific. Walls are often intangible, hiding secret paths to new locations, providing escape routes, new characters to meet (who can hinder or help you). Keep it loose. The player doesn't always die from not performing perfectly, so you can keep lots of different paths open.

Again, pulling together a plot would be difficult, but not impossible. That's really in the hands of the writer.
Anyway, the less impact the player has over other people's fate, the easier this is to do. Keep the world open, small, and low impact.