The roaring flamefest in one of the other threads got me thinking about something that has been bugging me the past few nights of playing Uncharted 3. Does the flow of a game at all affect whether it is "non-linear"? Could a game like Metro 2033, which was linear in terms of layout and progression, count as non-linear if it gives the impression of having freedom of choice and finding your own path? Uncharted is almost the definition of an interactive movie. But, when done correctly, it truly feels like you are exploring an ancient ruin and finding your own way. All the hallmarks of a "non-linear" experience.
For the first example, let's consider the concept of hidden secrets and side rooms full of equipment. There is still one main route to the end, but there are a lot of branches that lead to dead-ends or more gear. This allows the gamer to have a sense of exploration while, with proper cues, not interfering with the flow of the level. On the one hand, this still involves funneling and there is only one real route, but it provides a sense of options and choice.
For the second example, let's consider The Bioware Formula of Video Games. Also commonly referred to as the fork-join model of parallelism :p. On the one hand, you have plenty of choice on what to do first and in what order. On the other hand, you still need to do everything and you need to complete everything to proceed past certain checkpoints. Is this a linear game?
For the third, let's consider "multiple paths". You have a single warehouse you want to get into. You have three ways in: Shoot the guard at the front door, talk to the guard at the front door, or use the vent out back. All that changes is how you get into the warehouse, nothing else. Is that non-linearity? What about the same example, but with a bit of dialogue that changes during the debrief?
And finally, something I have been thinking about the more tightly knit open-world games. In particular, the old Fallouts. Yes, those were open worlds that you could do in (almost) any order you wanted to. But the story and progression definitely do their best to railroad you into a specific path with a specific order. Generally, these only "feel" non-linear if they have particularly weak stories that you don't care about (or really good sidequests).