In the wastelands, go down the steps to the exit from the sad-looking area where the portal took you. If you look down the exit, this is SOUTH. It's very easy to get lost here, so keep your map handy. I'll be using the compass a lot. The exit leads to a ledge with brown serpents on an opposite ledge. Be very careful in this level; avoid standing on those piles of dirt on the ground... Now take the descending passage on the left and this takes you to the area between the two ledges. Enter the tunnel on the left (EAST). The tunnel will fork into two; take the right one. This goes on for quite some time. As you go on, watch for an exit to the right (SOUTH) -- you may miss it if you're not looking.
This exit leads to what I call the Two Portals room. It has a closed portal and a blocked teleport. You need the Cave Key to open these two; if you don't have it, go back to the tunnel and continue down the tunnel. This time, keep an eye on the LEFT (NORTH) wall. Somewhere along the way you'll see a square wall with a different texture from the tunnel walls. If you reach an open area before you see this, you've missed it: go back into the tunnel and look for it.
This square wall is a revolving door. Open it and enter. Watch for the brown beastie waiting on the other side, though. Go up the winding path to a big open area. Go left (EAST), and you'll find a narrow walkway with lava on both sides. Go to the end of the walkway and you'll find the Horn Key. Note that once you get the key, the walkway breaks into pillars. You must jump from pillar to pillar all the way back if you don't want to fall and get burned by the lava.
If you ever fall into the lava, simply follow the walkway until you reach the beginning, and pull the switch. This lowers a platform to take you out of the fire.
If you're following my order of getting the keys, go back to Shadow Wood now (retrace your steps through the tunnel, and back to the starting room).
(Alternatively, after pulling the switch at the base of the tower, run to the rising pillars and get on one of them. This way, you can reach the high area without getting hit by the traps. This may not work with the Mage because he's too slow to get to the pillar before it's too high to reach. Thanks to Jeff Rife for providing this tidbit.)
There's a switch on the high area that raises steps to go up the tower. Jump to the base of the tower (don't drop down to the swamp; it's just a little too high and you'll get hurt). Now climb up the tower and pull the switch. Now the portal beside the swamp is open. This portal takes you to the Darkmere.
Smash down the rotten trees in front of you when you first enter the Darkmere. Enter the building and go to the room flooded with muck. Now, look for a piece of furniture that is different from the rest (you can find out what it is yourself, I won't spoil the fun here). Go up to it and activate it. This opens the door next to it. Activate the switch behind the door, and the other door in the room opens.
Enter the door, and go left. At the end of the corridor, open the door and activate the switch inside. Now go back and take the corridor opposite the door. The first switch has opened a room here; go inside and activate the switch. Now go along the last corridor which leads outside to the swamp.
Go into the porch of the small building here, and activate the switch there. If you look into the window, you'll see the Castle Key which you need in order to get to the Swamp key. However, the door to the building is not open yet, so follow the current of the muck and you'll get to a big open area with a castle. Don't drift with the current now; the muck flows into a very deep chasm and you'll get killed by the fall. Go to the front of the castle and pull the switch. This lowers the bridge into the castle. Don't fall off the bridge as the monsters come charging out! Go inside the courtyard, and look for the room with a well.
Jump into the well and activate a switch. This raises the water level so that you can get out again, and at the same time, it opens the door in the small building with the Castle Key. You need the Castle key to open the room at the top of the tower in the courtyard, so go get it now. Climb up the tower and open the door. There is a hidden switch here: see if you can find it! Hint: vandalize the room! (ie., smash everything you can). This switch opens the door to the lower level of the castle.
Go to the lower level of the castle (the entrance is somewhere in the courtyard of the castle), until you get to what looks like a dining room. Note: if you have the Horn Key, you can reach one of the six puzzle switches from here. Now, look for where a fireplace is supposed to be but isn't. Open the secret wall behind, and a secret passage will be revealed. Go along the passage and pull the switch at the end. This lowers an elevator that takes you to the room with the Swamp Key.
As you approach the key, walls will rise and block you, and the masks on the wall starts shooting poison darts. You cannot avoid getting hit by the darts, so run as fast as you can along the zig-zag walls to minimize the damage. Now get the swamp key. The walls will re-arrange to form three rows, two rows with fireballs spewing from the ground and the last row with the poison darts trap. One of these rows is the one you must run through to get out; if you run through the other two rows, you'll be teleported back to where the Swamp Key was. Note that this is randomly picked, so you've to try it out each time you play the game. (This time this had better be correct... I've changed this about four or five times by now.)
If you're following my order of getting the keys, go back to Shadow Wood now, using the portal beside the small building with the Castle key.
Hold it there! Don't be greedy! Carefully step into the room and stop. Floors and ceilings will start to move; some pillars will crush down from the ceiling. Deep pits will form in the room. When things have calmed down, you can follow the right ledge, which will lead you to a room with the portal to the Caves of Circe.
Alternatively, follow the left ledge (you need some jumping around for this route), until you come to a switch on the wall. Activate this switch, and the deep pits will be removed, partially restoring the room. (Thanks to Michael W. Daniels for telling me about this switch!) Now you can walk around the room and collect the goodies here. After collecting the goodies, look for the room with the symbol of Korax and step into the portal.
This takes you to the Caves of Circe. Turn right and jump down from the ledge where you start, and turn right again. Jump down the hole with bats flying out. Now you are in what I call the Ettin Cave (you have to put up with my silly names because I'll be referring to them when giving you directions). There are three exits from here; take the leftmost one, which leads to Skylight Cave. I call it that because you can see the sky through the big crack in the ceiling. Turn right when you enter the Skylight Cave, and jump into the hole at the end of the passage (or fall into it if you didn't see it!). This is a small cave that opens out to a corridor. Go out on the corridor and turn right. Take the first left turn. This takes you to what I call the Middle Cave. The Cave Key is here.
Note: you must jump into that small cave before the Middle Cave opens, even though there are many ways of reaching the Middle Cave from the Ettin Cave. Sorry for the mistake I made in the previous version of this walkthrough, when I thought that you can reach the Middle Cave without going to the small cave.
If you have the Horn Key, you can reach one of the six puzzle switches from here. If you have the Swamp Key, you can also get to another puzzle switch from here.
If you don't have any of these keys, here's how to get back to Shadow Wood: Go back to the Ettin Cave. This time, take the right exit. You'll get to a cave with a bright open area at the far end overlooking a deep chasm (this is not the pit with water flowing down the sides). Walk along the ledge on the left, and make your way across the chasm. There's a Porkalator along the way... see if you dare to get it :) At the end of the path, there's a room with some goodies and a teleport. This teleport takes you to where you started when you came to the Caves of Circe. Step into the portal there that takes you back to Shadow Wood. To get out of the room under the temple in Shadow Wood, find a switch in the room. This lowers an elevator that takes you back to the main floor of the temple. Now you can get out.
Note: some people have written me about problems with gaps in the magic blue bridge. I've finally found out what's the cause of this problem. In this room, the magic bridge appears after you kill a certain number of Afrits. If you kill the last Afrit when it's flying where the bridge would appear, then when the bridge appears, there will be a gap where the Afrit is. So far, I don't know of any solution to this problem, unless the gap happens to be somewhere that you can jump over. You probably have to reload a previously saved game and try again. So, my advice is, stay away from where the bridge will appear when you kill the Afrits.
Now, go down the bridge and enter the exit at the bottom. Climb up the passage to the top and open the door using the Cave Key.
There's a fast-flowing river on the left. Beside this river is a door that needs the Swamp Key. Open it and climb up the passage. Take the first left tunnel, which leads to a room with the puzzle switch. The other tunnel leads to a portal that takes you to the Darkmere.
Keep going until you reach a place where the path splits into three (this is after a dead-end tunnel on your left). Kill the centaurs here and a large swampy area opens nearby. Go to the far end of the swamp and climb up the stairs. Open the door with your Swamp Key. Go inside and pull the switch in the farthest room. This opens a large temple-like place near the swamp. (The long path with centaurs is actually the perimeter of this place; this switch lowers the entire right wall of the path to reveal it.) Go up the stairs to the main door in this temple-like place. Open the main door. (Hint: you may need to push it hard and try to open it at the same time). Go inside the building and go behind the portal. The puzzle switch is there. The portal here takes you to the Darkmere.
The portal will take you to the Hypostyle. There's a four-pointed star in the centre of the Hypostyle. One of the points will be raised: this points to which room you should enter next. Note that the order that the rooms are opened is random, so you must always follow where the star points. There are four possible rooms:
Note: if you're playing the fighter, the second part of your fourth weapon is in this room.
Note: if you're playing the cleric, the second part of your fourth weapon is in this room.
Note: if you're playing the mage, the second part of your fourth weapon is in this room.
Now, to avoid getting hit by the traps that also activated, press one of the other panels. This teleports you to the door directly. (Actually, this is intended as a punishment to those who didn't look at the symbol; because if you didn't press the panel with the correct symbol, the door is still closed and you'll have to run through the fireball traps to get to the panels again.)
Here are some tips on fighting the Death Wyvern, for those of you who are having trouble with it: