Skill challenges are one of the thing I like the most in 4th Edition. They allow DM to have a framework to assess the success of something other than combats without having to get into detailed minutia, and still leave the players free to role play as much as they want, and the DM to adjudicate based on how your group prefer to handle things.

One of my group is more "technical" minded, and will readily go for the rolls, without trying to put flavor around them, while for the other group is approaching the skill challenge with more flavored description of what they attempt to do. In both cases, skill challenges are handy..

Anyway, back to the point, here are the Underdark traveling rules I use in my campaign.

Traveling in the Underdark

General information: Unlike the world above, the underdark is a place of tunnels, caverns, chasms, darkness and dangers. It is regularly changing through the natural forces of the earth, as well as the interaction of its denizens (especialy the burrowers), and as such there is no real set "route" map for underdark travel.

Underdark maps refers to area or landmark type that help guide a traveler from one point to the next, but travelers will each time have to take a different path to reach the same point, because of the changes always happening in the tunnels patterns.

Distances: In the Underdark, you go from one destination to another through waypoints. Each destination is given by the DM a distance estimate that matches the skill challenge difficulty factor.

A destination close-by will have a skill challenge of 1, whereas a distant destination will make the skill challenge difficulty 5. Every check in the skill challenge will cover roughly a 6 hours walk time, so this is roughly 1 day walk for close distances, and 4-6 days for distant ones.

A distant location is still within the same region in the Underdark. For longer travel, the DM should set multiple intermediate destinations, distant from each other. If someone wants to travel through Middle Underdark from a location below the Sword Coast to a location below Thay for example, assess the number of intermediate destinations by the general distance between these areas on the overland map, assuming 4 days of walking per intermediate destination.

There are three Underdark layers, the Upper Underdark, the Middle Underdark and the Lower Underdark. A destination in another layer will have two distances set by the DM, one for each layer area (the crossing to the next layer becoming a waypoint of its own). This represents going deeper, and each layer has an increasing factor of difficulty and danger.

Gather Information:

One of the key to Underdark travel is that the players should gather the knowledge of the waypoints before their trip. So to travel in the Underdark, they must chose a specific destination, then they need either a guide, a map, or have already been traveling between these two points before. These ensure that the players don't venture blindly in the Underdark.

As it is not very fun to have a group lost in the Underdark, make plenty clear to your player that they will get lost without one of the above. If they still insist, do not kill your party.. you can arrange for them to be captured and sold to the drows for example, after having a few good encounters and communicating the feeling of aimless wandering...

Light:

One of the main thing with Underdark is the lack of natural light, and normal day/night cycles.

To know if there is light at a given moment, roll a d6 depending on the layer they are in
 

Upper Underdark : 1-5 = lowlight, 6 = darkness
Middle Underdark: 1-3 = lowlight, 4-6 = darkness
Lower Underdark: 1= lowlight; 2-6 = darkness

Low light can be provided by glowing mushrooms, phosporecent mosses or glowing minerals... Use your imagination to describe the source. Light occurence changes randomly in the underdark, and I usualy do this check at the beginning of a 6 hours check. Ask the players how they organize themselves when they are in full darkness (who carries the torch in particular).

Encounters:

Every 6 hours, ask the group to roll for an encounter after rolling for the light. It is a straight d20 roll, and encounter occurs if they roll low.

Upper Underdark : DC 2
Middle Underdark: DC 4
Lower Underdark: DC 3

I add + 2 to the DC if they are traveling with light in full darkness (+4 if it is bright light).

When camping/resting, I do request a difficult dungeoneering check first to set up camp. If they pass, the DC is 1 less for this 6 hours time.

As a DM, prepare a few encounters ahead of time based on the layers they are in. get these encounter out when they fail the encounter check. Also prepare a difficult encounter for them to face off, as this will be the consequence of failing 3 skill checks.

Skill Challenge:

The Primary skills used for the skill challenge are Dungeoneering, of course, Endurance, Athletics and Stealth.

In the Middle and lower Underdark, add Intimidate to the primary skills, representing the capability of the party to act and look tough, thus discouraging unseen creatures to even engage them or come close to them.

I recommend using the DMG2 rule stating that one single skill can't have more successes than the difficulty of the skill challenge.

Furthermore, I do grant a free success to the skill challenge when the following happens:
- All the players in the party have had one success in one of the primary skill
- The Group had a success with each Primary Skill

The Skill Checks are linked to the layer of Underdark they are in:

In Upper Underdark,  ask for 3 moderate and 1 difficult check. As a DM you can alternate the hard skill from one route to another, representing slightly different challenges between different places. By default, Dungeoneering should always be the hard check in the Underdark.

In Middle Underdark, 3 moderate difficulty and 2 hard checks

In Lower Underdark, 1 moderate difficulty and 4 hard checks.

If the group has already travelled between these two destinations, one way or the other, transform one Difficult Check into a Moderate one to account for an easier way through already familiar territory.

Check Failures:

An Underdark travel skill challenge failure does not mean they are lost. It means they arrive to the destination without gaining any experience from the skill challenge itself. Succeeding on the skill challenge grants them twice the normal experience value of a skill challenge.

Furthermore, 3 failed checks do not end the skill challenge. Each group of 3 failed checks trigger a difficult encounter prepared by the DM for the group to face.

Once the encounter is resolved, the group continues their skill challenge checks until they have as many checks as the number required by the skill challenge difficulty.

Each individual check failure is cumulative.

Failed Dungeoneering: +1 DC to all subsequent checks for this skill challenge

Failed Endurance: Character rolling loses 1 healing surge, then have all the characters including the one failing roll another endurance check with DC-2 from the initial check. Failure means loss of one healing surge

Failed Perception: Character rolling loses 1 action point. Then have all the characters including the one failing roll another perception check with DC-2 from the initial check. Failure means loss of another action point (if any is available)

Failed Athletics: Character rolling loses 1 HP per point under the DC of their roll. Then have all the characters including the one failing to roll either Atletics or Acrobatics check with same difficulty but at -2. Failure means loss 1 HP per point under the DC of their roll.

Failed Intimidate: Increase one of the the monsters' level for next encounter by 1 per failed intimidate.

Remember that each check is a 6 hours time, and you should account for sustenance for the group during their travel. Also, the group needs 12 hours to pass between two extended rests.

Secondary skills suggestions:

These can only be used once during a given skill challenge. They do not take time, but failing those does increase the next skill check DC by +1.

Acrobatics (same as Athletics DC): grants a +4 to the next Athletics check.
Arcana (Difficult): Reroll the next failed check once.
History (Difficult): Grants a +1 to all the Dungeoneering checks for this skill challenge.
Heal (Difficult): Prevents the next HP or healing surge loss by the character rolling the skill check (does not prevent the loss from each character check happening because of that failed skill check).
Perception (Difficult): Give them a surprise round during their next encounter (random or following three failed check, whichever happens first after the perception check was made).
Nature (Difficult): Reduces the sustenance need (meals/day) by half for the whole trip, as the group gather consumable food on their way. They snack on mosses and insects, mostly...

Help another:

The help another action can be used during the skill challenge, but the DC is one difficulty less than the required skill check (and not DC10), the help another does uses 3 hours of time and does not count toward the number of checks to success. Help Another checks need to be made before the check to be helped, and failure provides a -1 to the skill check, while success provides a +2.

This is a great post with plenty of tips!!!!

I particularly want to emphasize each player preparedness when their turn come. You should have planned your action and be ready to go when it is your turn to act. A combat round is 6 seconds time, and to keep the combat fluid and moving fast, we have to keep you players deciding on your action pretty fast, once your turn is on..

This was immediately an excellent read for me, and I decided that I needed to have it into my campaign. The main reason was that this adventure is really open ended, and provided a wealth of information for an area that was at the edge of the underdark. Because I already knew I wanted to have the second part of my group's heroic tier spent in the Underdark, this came as a God-send! imho, this adventure will become a classic...

My groups started in the Silver Marches, in Silverymoon, so I immediately thought about putting the Minotaur's gate entrance in a remote valley of the Nether Mountain, 50 miles or so South East of Silverymoon. This is certainly an excellent place for one of the entrance to the underdark.

The two groups were at different stages, and I had to stretch a bit to get them where I wanted them to go, and of course make it fit in the campaign arc.

*spoiler warning*

My first group at the time was stranded into a Drow city, Maerymidra (before the events depicted in the City of the Spider Queen adventure). I already knew that this was happening before the Arch Mage unleashed the hordes on the Drow City, so I built in an elaborate plot by one of the lower drow house to regain strength by allying with the arch-mage and providing weaponry technology for the upcoming onslaught. Gendar, in the 7 Pillars Hall ended up being the perfect contact, and the rogue mage Paldemar would be the drow's tool to unravel the mistery of the Bronze Wardens and sell those mighty war machines and the amulets to control them to the Drows forces. This became the background plot that both groups stumbled upon. Of course, I still needed a way to bring this first group in 7 Pillars Hall, so I added a teleportation portal between the basement of House Myett and the central teleport circle in 7 Pillars itself, allowing the drows to come in and teleport out with their own scroll. Thus when the group decided to leave House Myett after having the Hidden recover the sword Mirthuvial for them, they just stepped through the portal.. and voila.. they were straight where I wanted them to be, and spent many sessions roaming through the various adventures hook of H2. 

For the second group, as I already had the background plot described above, I used the Bloodreaver slavers thread that starts the H2 adventure part. The Bloodreavers had been kidnapping folks around Silverymoon, and the Church of Moradin had noticed. As it wanted to extend its influence in Silverymoon, it decided to send a fighter squad led by a Moradin Paladin to try to find where the orcs came from. Before they could discover the remote vale where Minotaur's Gate was, they got attacked by the Orc warband that had noticed them and were captured (the group unknowingly came upon the orcs as they were ravaging the dwarven Monastery were they were resting). Because the adventurers already had contacts with the Church of Moradin, they got asked to rescue the captured Paladin and finish the job. Thus, they ended up finding the Minotaur's gate, and step into 7 Pillars Hall. The twist for this group was that one of the player's character (Lokius) had just died, and the player was rolling for a new character, while two other players decided to leave the group during that time frame. Another player was interested to step in... So two characters became NPCs (Bjarni, and Fulgrum, triggering the lost sword quest (i'll write another blog post about this later), while two new characters stepped in (Garrel-Kai and Unsung, his body guard). Because of the timing of their step in, I set their background to be already knowledgeable about 7 Pillars hall, Garrel-Kai being the owner of the House Azaer trading post, which allowed me to run the two groups in the same area with fairly different objectives and approach. 

Liking the result of having a character being involved with the location they are in, I later used that approach again when a new player joined the first group, and came into play as Curia one of the mage apprentice of the Mages of Saruun, investigating rumors of a slaver ring, and deciding to get herself captured, then later being found by the party as they were in the Horned Hold slave pits area.

I also ended up creating a whole new area where the army of golems was to be found, to give some depth to the war technology buying thread. Only the first group found this place though.

Note that all this story-thread was not fleshed out in a day. The occurence of when a new player coming in or leaving happened, as well as where I wanted to go with some of my early heroic tier thread (like the lost sword quest) played a large role in shaping the story above.

As a DM, I think player's events need to be woven into the story. If a player leaves the group, I will use his or her character in future threads as a NPC and play upon the common history they have lived though with the party. When a player joins the group, or a player's character dies and the player rolls a new character for the very next session, it is up to me to insert that occurence into the story flow, and adapt the player's background to fit in that particular moment of the story. There is no character dropping from the sky, I want it to make sense wherever the group happens to be.

I also found out that having players join the group and have their characters have information about the location they are in is a good way to immediately throw them in the middle of the story. They can then use the information I provide them as they wish.. It sometime triggers interesting behaviors and role play within the group... It is also interesting to see how new players catch up with the ongoing larger storyline that the group have been involved with before they come.

The most challenging player introduction I had to do in the campaign was Ceiled. The player joined the group as the party was deep into the Tomb of Khelb. Because of the storyline, and the character's class (Druid) there was no way this new character could have been part of the raiding group led by Xeron, and no way the character just happened to be there.
But there was an encounter with a fossergrim incoming in the session, so Ceiled ended up being a prisoner of the fey, held in captivity in a small planar space within a snow globe owned by the fossergrim, and as a mischievious and lonely fey living deep down this foreboding tomb, the fossergrim offered the snow ball and its prisoner as an exchange for one of the party's member favors...