While I can't speak to any game specifically, my first instinct would be to approach this using a graph. It sounds like something you have started doing, by your use of "stages", though maybe only linearly.
For anyone unfamiliar with graphs as a mathematical and programming concept:
Conceptually, each node in your graph could have a set of flags like you were thinking. And each edge is some condition of the current game state.
To use an example from Zelda Link to the Past, you're supposed to collect all three pendants before being able to carry on. And for each pendants you collect, it should no longer be shown on the map as a current objective.
So we have 4 nodes in our graph of this simplified example:
- A: New Game
- B: Has Pendant 1
- C: Has Pendant 2
- D: Has Pendant 3
- E: Has All 3 Pendants
Then we create our edges between the states, with the conditions for moving along that edge.
- A -> B requires getting Pendant 1
- A -> C requires getting Pendant 2
- A -> D requires getting Pendant 3
- B -> E requires getting All Pendant
- C -> E requires getting All Pendant
- D -> E requires getting All Pendant
So with this, we have a branching structure, allowing the player to get the pendants in any order. But they won't reach the final state E without getting all pendants.
Then we attach our flags to each state:
- isPendant1Showing = true
- isPendant2Showing = true
- isPendant3Showing = true
- canProgress = false
- isPendant1Showing = false
- isPendant2Showing = false
- isPendant3Showing = false
To figure out then what state our game is:
- Start at A
- Set flags as they are in A
- Evaluate each connection
- If condition is true evaluate the connected node the same way, overwriting any flags
For save files then you just need to save the data that is relevant to the conditions for the edges.
For added complexity to a game, this method can be applied recursively or to individual elements of the game. The condition for an edge could be based on the result of another graph. Or the graph could exist per NPC, and the conditions are based only on the state of a specific NPC. Programming wise, I'd recommend that any graphs that are identical (same states, same conditions, same flags) exist once, and you simply pass the NPC to the graph to get a list of flags back.