I’ve run almost exclusively non-linear dungeons for several years. Exceptions might include like a defensive installment meant to funnel invading forces through a choke point, but I usually consider that part of a dungeon (in that case, an ancient city). So yes, I have ran non-linear dungeons with multiple interlacing spaces, both on the same dungeon level and between levels. Since this is my thing, hopefully I can help a bit here!
First, the purpose of a non-linear dungeon is to be playable space. Just as in Dark Souls and related games, the environment is a core component of play. Do you go left or right first? Are there any signs that suggest what is down each passage? Do you have a rogue that can use their climbing tools, scale a rock wall, and lower the rope to unlock a shortcut for the party? How are you going to get past the flame trap without alerting the ghouls nearby? How much further can you go before you need to fall back due to resource depletion?
If you do fall back and need a few days or weeks to rest, recover, and resupply… what do the dungeon inhabitants due to reinforce their home? And so on.
So, the drama comes from hard choices within the dungeon and the roll of the dice (torches burning out, limited spell slots being used for a light spell that is about to expire, random encounters, saving throws versus traps, massive damage received from monsters). Indeed, the role of the dice is to inject drama through uncertainty. Make the rolls count.
If your players do not want to explore and play the space, they probably won’t have a good time. Set expectations beforehand.
Second, you cannot run a non-linear dungeon as if it were a linear dungeon. Do not expect every choice to be a dramatic one! I believe that the modern obsession with DRAMA at every turn in a TTRPG session actually undercuts such efforts. When a scary movie is nothing but jump scares and gotchas, they lose their potency. You need the empty rooms. You need the random encounter rolls that result in NO ENCOUNTER. You can’t force the “standard story structure” of 5 room acts (see: 5 room dungeons), it’s plastic and unbelievable. If every wing of the dungeon is a layered story, it’s confusing and drowns your players in useless crap.
Your non-linear dungeons need white space. Let things breath. The narrative is emergent, it comes from play. It comes from you having a rotting library with no encounters keyed. Suddenly, you roll a random encounter. It’s 3d4 goblins. What are they doing in the library? Most of them can’t even read. Do your GM brain thing and figure it out. Now in the fight, what if their guide is killed by an errant goblin arrow. What was supposed to be a safe, steady trek through the fens is now a serious challenge - their guide is dead! Drama. And you get to be surprised, too.
I’d like to respond to some of your comments, too.
You said, “It seems like the more info you give … it really makes their choice making process faster, but also it feels like it diminishes exploration aspect … Almost like exploration … and tactics … are diametrically opposed because you can’t plan for something you do not know.”
You need to stagger your information. They enter a dark, webbed library with rotten wood tables. They can smell mildew and spoiled meat (zombies hiding under overturned bookshelves). That’s all you tell them. Of course they want to know the dimensions of the room, how it’s laid out, what else they see, etc. Give them the opportunity to ASK you! Now you’re not just describing the room - now, they are exploring. Their tactical toolkit will expand as they interact with the environment. (exploration leads to tactics)
You said, “For example, if a group has a set destination and there are two main ways to get there: Troll cave and Ooze tunnel, then that choice is mostly mechanical: which one will be easier to go through? … If I have two cool encounters ready, than there is absolutely no reason to not put them one behind another in a linear fashion: more cool content for the players. … If I have a really fleshed out troll encounter and the ooze one is kinda meh, than why would I not just drop the ooze encounter and vice versa? … If I have no good ideas for these encounters … I would much rather make it a skill challenge or something to that effect and be done with it as fast as possible to get to the interesting part.”
The choice shouldn’t be purely mechanical, it should be nested in the established narrative. But, even if it were purely mechanical, we are playing a game and the mechanics are agents of drama. You noted that there were two main ways to get there. Great! But what about other ways? Yes, they have to go through the troll cave or the ooze tunnel. How else might they get into the troll cave other than the main entry? What if the ooze tunnel is much longer but, unbeknownst to the players, has some valuable magical items they will need later? What if they know that and now have to decide: do we have the resources and time to try and get those magical items?
There are several reasons not to put them one behind the other. Verisimilitude is one, and often overlooked as a buzz word. Give that careful consideration. Pacing and player agency are others. If your ooze encounter is meh, fix it. If you design something and you don’t think it’s interesting, make it interesting! And remember the cost to the players: hit points, spell slots, arrows, potions and scrolls, torches, random encounter rolls, time limits, and very importantly… REAL TIME LIMITS. The players have you for four hours today. If they go down Path A, they may not get to experience Path B until next week. Make sure they have some information, most of the time, to make that an important decision for them.
The major hurdle to running proper non-linear dungeons is the preparation required. If you’re like most of us, you simply don’t have enough time between sessions to do that amount of preparation. Take a tip from the older editions, and front-load the strain into generation tables and gameplay procedures. Once you’ve made or found them, you can use them forever and they pay immense dividends.
PS: See attached image for one level of a dungeon I designed. Three entries/exits from the level, looping passages within and between wings, multiple lines of sight and elevation (not noted on the map). Many areas are “designed” and keyed ahead of time, others are empty, others still have things that are inaccessible or unusable for now… I used my generation tables to make 10 random encounters ahead of the game, and I will roll D10 on that list anytime an encounter is rolled during play. It’s fun!