I did something similar recently. My players needed to cross through a war zone. I wanted to get the danger and uncertainty of the setting across, but I didn't want it to devolve into a series of staged or random encounters they would feel they were just being subjected to, either by the dice or by me. Here's what I did:
1. The Atmosphere
I created the feel of the environment through the narrative of the surroundings: magic-torn battlefields, the distant sound of weary soldiers singing as they trudge through the nearby woods, etc.
For your module, you'll likely want to add sensory elements that reinforce the nature of the labyrinth. For example:
Clues that this place is trapping you on purpose:
looking behind and seeing changes to where you've been,
encounters with other trapped creatures who are standoffish because of the tricks the labyrinth has already played on them
Clues that passages are opening and closing just out of sight
the sound of stone-on-stone grinding,
changes in echo-quality,
sudden smells or changes in drafts blowing through, etc.
Clues that trying to mark your path is hopeless
small arrows drawn in chalk or blood near intersections
a blood-stained passage where someone or something was killed, leaving only a few bones and a broken piece of chalk
the corpse of an extremely old person, recently deceased, with scribbled
journal indicating they'd been wandering this labyrinth for years,
living off rats and lichen, etc.
2. The Encounters
Rather than left-right choices, I gave my players sensory clues at each decision point that foreshadowed the consequences of each choice. For example, at one point they could either turn uphill and travel along the ridge top, or go down and cross a burned-out valley where a magical battle had happened. If they went up, they suddenly came face-to-face with a contingent of hobgoblins. Both groups had been masked from each other by the hilltop and vegetation. If they went into the valley they faced a skill challenge where they had to use Nature, Survival, and Athletics to get through without anyone getting hurt.
This made them feel like they were making some level of informed choice and deciding their own fate. Sometimes they correctly anticipated the challenge down a certain path, other times they completely misjudged it, but they always felt the clues were at least consistent with the results, if not fully predictive.
For your module I'd do something similar. For instance, they come to a junction and
down one hallway it is perfectly quiet and the hallway is empty of
the dust and minor debris they've noticed previously (that leads to
the gelatinous cube's stomping grounds)
while the other way is a long hallway with a flickering light barely
visible in the distance (where will-o-wisps lure the unsuspecting
into pit traps)
etc.
You can play off of sounds they hear, things they see in the hallways, smells, even things they feel, like that "sudden chill that runs down your back when you look down the left tunnel."
Lastly, where I could I came up with 2 completely different foreshadowing clues for each encounter. That way, when I gave them the choice of the ridgetop or the burned out valley and they chose the valley, I could later still use the encounter they hadn't chosen (the hobgoblin surprise), but next time I would foreshadow it as an area of dense fog with a thick bed of pine needles through a small copse of trees (again, a reason for the groups to not see or hear each other for the mutual surprise). That way I only needed to create half as many encounters, because I could use the unchosen ones over again by just slapping on a different front end and not repeating any clues.
It really gave my session a unique feel, and my players had a lot of fun with it. They were quite proud of themselves when they anticipated the clues correctly, and there were some good-natured "I told you we shouldn't have gone into the swamp. Never go into the swamp!"-type moments as well.
3. The Labyrinth Generator
The labyrinth generating system provided requires die rolls to randomly generate it, but the OP expressed a fear that revealing the randomness will diminish the experience. If you don't want to give away that this process is random, make a bunch of die rolls ahead of time (or use a spreadsheet to generate them) and just have a long list of them. Then check them off as you use them. You can fit hundreds on a single sheet of paper and you won't be seen constantly rolling dice.
Secondly, the module's maze creation system generates hallways and doors, but doesn't appear to give guidance about what's behind the doors. A few ideas come to mind:
- You could have doors open onto an empty hallway, then continue to use the maze generator regardless of whether they go through it or continue on.
- You could have doors be fake, and either locked with a lock that doesn't open, or the doors open onto a blank wall.
- You could use the Random Dungeon tables on page 291 of the DMG to roll up a list of door results, then check them off as you use them.
- You could ignore door results on the module's random table and just stick to passageways.
An finally, one of the random encounters is necessary to the progression of the game. The OP expressed concern about how to integrate that into the maze generator.
A single encounter required for progression is called a "choke point". If you leave the timing of a choke point up to the dice, you could be in for a sudden and abrupt end to the situation (if you roll the final encounter too early), or in for a long slog (where you can't seem to roll the right combination to end the labyrinth). In the second case you either keep rolling until you get what you need, or you bail out and just make it happen through DM fiat despite the dice rolls. Neither of those outcomes makes for a particularly smooth session. My recommendations regarding a required encounter like this are:
- Hold your required encounter separate from your random table and drop it in when the timing is right. Since your labyrinth is re-building itself as it goes, there shouldn't be any problem with putting the hook for that encounter in when it's appropriate. You can even make it the only path forward at that time. You can plan ahead of time that this will be after 3 other encounters, or 5, or whatever feels right, but leave yourself the ability to set that timing according to what happens at the table so you can pivot as necessary.
- Be sure the characters have multiple ways to succeed in the encounter. They don't have to win, but there needs to be an opportunity for the game to move forward regardless of the outcome of that encounter. For instance, if there are riddles and a riddle-giver that gets them to the next part of the adventure, be open to them getting what they need even if they fail miserably at the riddle challenges. If they botch the riddles, maybe they can convince or trick the riddle-giver into helping them anyway (through Persuasion, Deception, Intimidation, etc.). Failing that, maybe they can secretly follow the riddle-giver after they leave and find their way out despite not getting its help (through Stealth, Survival, etc.). Or maybe, ultimately, they could actually defeat the riddle-giver through combat, and either earn enough respect to be moved along, or figure it out for themselves from whatever's left on the body. Just be open to allowing reasonable approaches a reasonable chance to succeed.
- For inspirational reading, I recommend Justin Alexander's essays, specifically the "EXTENDING THE THREE CLUE RULE" section of his Three-Clue-Rule essay. It's got some great advice on dealing with choke points.
