sometimes i think about how people refer to doom as "non-linear", and also about how people refer to castletroids (named after the famous series Nintendo Castletroid) as "non-linear", and how it doesn't quite mean anything.
or rather, it means too many things, and when you are trying to make video games of your own, that becomes inconvenient. so here are some of the things it means. also some crappy diagrams, where "progression" happens as you move to the right
leaves

i'm calling these "leaves" because it's what you get if you think of progression through some area as a tree, which is wrong for several reasons, but don't worry about it.
this is the classic hyperrealistic AAA experience (i say based on having played like 2 such games) — you reach a fork at the end of a corridor; one way leads to an item in a dead end; the other way is just the critical path. rinse and repeat.
pros: this is the cheapest way to make something feel nonlinear while actually being incredibly linear. the player still feels like they have options in some sense, but even if they pick the "critical path" choice first every time, they haven't really missed anything of substance, so you didn't waste all the time you spend building it.
cons: players catch on and may start to get the feeling that nothing matters and your whole world is an illusion, which is true, but they're not supposed to realize it. sometimes this leads to the annoying habit of checking both paths before settling on one to make sure you get the item down the dead end, because many games that do this also like to have points of no return right afterwards. also, absolutely no replay value, because the sequence of events doesn't vary much: you can get the item, then continue; or you can skip the item and still continue.
keys and locks

"key" and "lock" here are in the game design sense, where they really mean "basically anything". that ledge is too high and you have to come back with the double jump powerup? that ledge is a locked door, and the powerup is a key. 90% of video game design is trying to disguise the fact that it's all just keys and doors.
this is similar to a leaf, except for two key factors: (a) the player must visit the leaf first, and (b) the design often strongly encourages (or forces, if you're a coward) the player to traverse the critical path first, before they can actually continue along it. after all, it's kind of anticlimactic if you pick up a key before you even know there's a locked door. you didn't actually solve or accomplish anything.
pros: gives the player something to do! this is like the basis of all video games. usually the leaf part is a bit longer than suggested in the diagram.
cons: impressively, even less replay value than a regular leaf, because now the order of events is more rigid — you have to visit both branches, and the only optional part is whether you see the lock a first time before you get the key.
multilocks

now we're getting somewhere. this is an enhanced form of a lock, where you need (at least) two keys to open it, and those keys can be obtained in any order. depending on what else is along each of the branches, the order might significantly change the experience. it might even be a good idea to partially traverse one branch, stop, traverse the second branch, and then go back and finish the first branch.
pros: offers the player some genuine decisions without adding too much design complexity — worst case, you design it assuming they'll do the red key first, and now you've created an accidental (optional!) challenge for players who try to do the blue key first.
cons: a little trickier to design without ruining the illusion that it's just a door with a lot of keys, which can feel pretty arbitrary. (combining items is a fairly decent way to make it work, though.) everything is still mandatory, so the decision is really just which hoop to jump through first.
branching

i think this is what people imagine when they say "nonlinear": completely separate routes that are both viable, albeit not always equally viable.
pros: good replay value; player might do something completely new and different. players will describe your game as "nonlinear". whatever happens after the paths rejoin might play out differently depending on which path the player took, since you can put different rewards along each.
cons: players may remember having passed a fork and feel like they've missed something, especially if they're used to looking for leaves. if they then go back and try the other way, they will do twice the work for little gain. for players who only play the game once, you did twice the work designing twice as much space, and they didn't see half of it.
interconnection

what if branches, but more? now there aren't just paths, but several combinations of paths.
pros: lots of options and they can genuinely affect the experience. somewhat less pressure on you since the player can experiment and find what's easiest (or hardest) for them. it's cool as hell
cons: easier to get lost, since a player can easily choose a path that leads backwards without realizing it. if one particular route is significantly easier than the others, then it can be very frustrating to not find that route. again, for those (likely very many) players who only play once and take a linear jaunt straight through, you've done a lot of extra work without offering anything extra to them at all
sandbox

gone are the limitations of "walls" and "doors" and "keys". everything is out in the open, somewhere.
pros: it is the most nonlinear. look, i couldn't even draw it as lines. can be extremely good.
cons: basically directionless by default. very easy to get lost in. difficult to pull off graphically as well. i mean you've played botw you don't need me to spell out what's good and bad
and of course these can be combined arbitrarily, and they aren't the only structures. a leaf can have two branches. paths can go two ways. a branching path might take the form of a lock that takes either of two keys. and so on.
and now some doom maps
this is what i really wanted to do, was draw on some doom maps, sorry
downtown

this is MAP13 from doom 2, one that is much maligned by people who have incorrect opinions of downtown. it is the iconic doom "sandbox" map, being as it is a big open space with a bunch of independent buildings in it. i guess this doesn't mean anything if you've never played it, but here's someone on youtube 100%ing downtown without commentary.
this map is kind of a big fucking mess, especially with the extra presence of teleporters (poorly marked in green), but what's interesting to me is that the progression is completely linear, which is why i could draw it out in pink. no matter how you approach downtown, you must have the yellow key to reach the exit, you must have the red key to get the yellow key, and you must have the blue key to get the red key. i'm not even sure there are any other ways to reach the keys besides what i drew here, though some jumping is involved, so shenanigans might be possible.
and that's something that always sticks out to me: one of the most "nonlinear" maps in doom, seemingly very freeform, always requires you to do the same critical tasks in the same order. in fact every building i didn't draw a line through is completely optional! all that other stuff is just leaves. the true structure of downtown is this:

and i think that's beautiful. also i guess it's wrong because you don't need the red key to reach the yellow door but you know what i mean.
entryway
i'm going in the order i felt like drawing these, not any sensible order of ratcheting complexity. listen if i felt like doing editing i'd be putting this on my blog ok.

entryway is MAP01 from doom 2, which that same person has also played through. it consists entirely of leaves (darker purple) branching off of an extremely short linear path (lighter pink) (this was not a good choice of color scheme but now we're stuck with it).
the funny thing is, entryway is almost famous for being a great deathmatch level, which sounds funny for something that seems to consist of a lot of dead ends. but many of the leaves are still interesting — that room at the top has a couple pillars for hiding behind, and the part at the bottom right is a big outdoor area. plus, leaves are still forks, so there are very many places in the level where someone might approach you from any of several directions.
single-player as well, it's still enjoyable. it's short, it has several funny secrets (marked with X's) you can do in any order, and if you're sick of it then you can just skip it. maybe thickety nonlinearity isn't really all that necessary.
hangar

here is E1M1: Hangar, the very first map in doom 1. (youtube) the final map of episode 1 that romero created, specifically so he would've honed his craft before making the first thing a player would see. the pinnacle of his nonlinear level design.
it is basically a straight shot from the start to the exit. the record uv-speed time is 8 seconds.
at some point they added an extra switch which opened a door right by the beginning, so you could take the secret through the big central outdoor area backwards and skip most of the level. that's the dark purple path this time. apparently this was for deathmatch reasons, which is weird.
i dunno. i think entryway is a stronger contender than this, even if hangar has more atmosphere. it just doesn't have anything to do, really, and the secrets are very lowkey. (entryway gives you a rocket launcher!) kinda mid, john
refueling base

doom 2, MAP10, youtube. actually a cut map from doom 1 that was dusted off and finished for doom 2.
my primary anecdote about refueling base is that when i was a bright-eyed little fox, i took for granted that my parents were invulnerable, and i watched my dad play this map over and over and get absolutely steamrolled. somehow that cemented it in my mind as this terrifying insurmountable horror, and even the music seriously gave me the creeps for the longest time. i could not face this map at all. and then a few years ago i decided to just play through it and now it's like, fine
it's actually better than fine: it's really interesting. it's one of the more interconnected maps in the whole series. you can see there are like eight very distinct spaces here at least, and although the big circular room is kinda of central, it's not centered, and in fact you can avoid it entirely. the only locked doors are in the bottom left near the exit; pretty much everything else is accessible from the beginning, you just have to make it there.
and that's the tricky bit, especially from a pistol start. see, what's not shown on this map is the daunting number of monsters and the very particular arrangement of weapons and ammo. if you just go rushing through the level with nothing, you are very likely to get overrun just because you have no resources. if you came at this without knowing anything about it and without using a map and walkthrough, you might need to try it a number of times to figure out a viable route.
see, refueling base was finished by sandy petersen, the guy responsible for making just about half of both doom and doom 2. doom people will have very mixed opinions about his work, but i feel like it's not emphasized enough that he is primarily a tabletop designer. and this level feels like the design of a dungeon: oppressive and twisty and full of traps. it has goodies as well, but you've gotta route it out if you want them.
and all this is made all the more hilarious by how simple the actual progression is. you need two keys, and they're both very close together in the upper right. you can basically skip half the map, and you can even choose which half you want to skip.
there is a cyberdemon in the lower left who is trolling the hallway to the exit, but there's also a secret backdoor that lets you kill him easily, and it's also near the blue and yellow keys, which in turn lets you skip even more of the level.
wild.
i don't have a conclusion and i'm tired i just wanted to type a lot about video games thanks
btw if you are interested in better diagrams, there is a thread on doomworld with progression diagrams and analysis for all the maps in several doom games that i think is very interesting, but which i didn't look at while writing so as to avoid repeating whatever this person said. gonna go look at those now though
PS i keep thinking about downtown and how the "logical" progression is completely different from the player's impression of what the map is like, and how even though i've played it multiple times i still don't remember exactly how to get through it and just kinda fuck around until i start getting keys, and i think that's beautiful. i guess that is the other 10% of game design is disguising the overall structure as more interesting than it actually might be
