A while after you complete Underground Pass, a King's messenger will come, giving you a message from King Lathas. As soon as you get the messenger, you will have started Regicide.
After you've started the quest, go to King Lathas. He will tell you that the Well of Voyage is complete, and that he managed to get a letter to the elves. They agreed to help a little, and that King Tyras is camped in the woods south of their city.
The troops you were promised are also unavailable, so you'll be going solo. He also asks you to find an easier route to the western lands.
Head into the underground pass, with all the items you brought for the Underground Pass quest. Head across the swamp, talk to Koftik to receive a damp cloth. Use on an arrow, then light it on fire. Fire at the guide rope to make the bridge fall.
Go north, grab the plank, the follow the path south and east. Use rope on the spikes to cross. Go across the Grid the same way you did in the quest (hopefully you wrote it down). Open the portcullis, and go west - Remember the traps! Climb down the well.
Go into the south-east cage, dig near the mud in the back of the cage. Cross the ledge then the stone bridge. Follow the path south, go through the pipe. Go past the Paladins, use the plank on the flat rock, and enter the door. Reach the center of the platforms.
The path with the shortest number of bridges to cross is on the west side, third from north. If you fall, you can talk to Kamen at the dwarf camp to get some food to heal without wasting your better food.
Climb into the Well of Voyage.
As you exit, you'll be approached by and Elf, Idris. But, two more Elves will come out and kill him. They tell you to speak to Lord Iowerth, as he will help you track down Tyras.
The above map shows the route to Lord Iowerth.
From the Underground Pass, follow the path west until you come across a leaf trap.
Leaf Traps are pits that have leaves over the top of them. To get past them, click on them, and your character will attempt to jump over them. If you fail, you will fall into the pit. To get out, click up the protruding rocks on the side.
After jumping over the leaf pit, head south-west from the musician, and look for a stick trap between two trees.
Stick traps have a bunch of spiked sticks one one end. To get past them, click on them, and your character will attempt to walk over them without setting them off. If you fail, you will be hit for 80 Life Points and knocked back in the direction they are facing. If you're not careful, you could accidentally activate and be hit by this trap over and over, losing LP very quickly, and possibly die.
Once past the stick traps, follow the path north/north-west until you see another leaf trap. Click to pass over it, then go north past the ponds, and cross the log bridge going across the river. Speak to Lord Iowerth in the center of the Elf Camp.
Lord Iowerth tells you to seek out one of his Trackers. He can be found at Tyras' old camp site.
The above map shows the path from Lord Iowerth to the Elf Tracker.
Go back across the river with the log, and south across the leaf trap. Follow the path south, past where the stick trap is, and you'll end up at Tyras' old camp. Look for the nearby elf tracker.
He will think you are on of Tyras' men, but you'll say that Iowerth sent you. He won't believe you. Return back to Lord Iowerth. He will give you a crystal pendant, as proof that he sent you. Return back to the Elf Tracker.
He'll tell you they moved a few days ago, and tells you to search on the west side of the camp. Go west, and look for the dense forest. Right in front of it, there are some tracks on the ground. Try to follow them, but you are unable to.
Report back to the Tracker. You are now able to enter dense forest!
Dense Forest requires 56 agility to pass. Temporary boosts such as Summer Pie (+5) and Agility Potions (+3) allow you to go through as well. To pass through, simply click on each part of the Dense Forest.
As you pass through the Dense Forest, a level 110 Tyras Guard will appear and attack. After the Guard is dead, go west and look for trip wires slightly north.
Trip Wires are thin lines between some rocks. To pass, carefully click on them. If you fail, you will be hit with arrows dealing 100 LP, and will be poisoned.
After crossing the Trip Wire, go through the dense forest. Follow the path west into a clearing, then south through some more dense forest. Look for General Hining, and speak to him.
You will learn there is no way to see the King.
Return to Lord Iowerth.
Iowerth will give you a book: Big Book o' Bangs. Grab the empty pot spawn while in one of the tents too.
Head east out of the Elf Camp, through the dense forest. Follow the path north, the hug the wall east, and follow the path to the limestone mine. Mine some limestone, then head back to Tyras Camp. Take a barrel from around the camp.
Return to where the Elf Tracker is, except go all the way south. Take some of the yellow sulfur lying around. Then, use the barrel on the tar to get a Barrel of coal-tar.
Go to Camp Tyras. While wearing gloves, use the limestone on the small furnace on the east side of camp (if you don't wear gloves, you'll be dealt damage). You will make some quicklime. Now leave the elf lands. It is HIGHLY recommended to use the charter ship at Port Tyras to leave, as you'll then be able charter back to there, bypassing the Underground Pass.
Take about 10-15 coal from your bank, the Book, sulfur, quicklime, the barrel of coal-tar, and a pot to the chemists house you went to in Biohazard.
Talk to the Chemist about your quest. Ask about the naphtha. Then go outside and use his distiller. Use a barrel of the coal-tar on it. Start by turning the Tar Regulator all the way to the right.
When the Pressure is in the green or orange, turn the Pressure valve right one until the pressure indicator. If it's in the orange move the Tar regulator valve left one until it's in the green, then move it back right. Then, add about three coal so that the heat indicator is in the green. The Total Distilled bar along the bottom will start going up. Each time the heat goes down past green, add another piece of coal.
Once it is fully distilled, exit out of the window and you will get a barrel of naphtha.
Use a pestle and mortar on the sulfur to get some ground sulfur. With a pot in your inventory, use a pestle and mortar on the quicklime. Mix the pot of quicklime dust with the Naptha to get a Naptha mix. Use the sulfur dust with the Naptha mix to get a barrel bomb.
Now you just need a fuse! If you don't have the strip of cloth yet, to make one, take four balls of wool to a loom (one is located in Falador farm house). Use the strip of cloth on the barrel bomb, and you're ready to go!
Don't forget a tinderbox!
Go back to the elf lands (either by Chartering if you chartered out, or by going through the Underground Pass). Go back to the area the elf track is, and look for some rabbits. Chop down a tree and light a fire (if you don't have an axe, there is a fire at the Elf Camp), and cook the rabbit.
Talk to the Tyras guard next to the catapult, north of Tyras Camp. Use the cooked rabbit on him. He will take a break to eat it. Use the Barrel bomb on the catapult.
You will launch the bomb and destroy the tent that Tyras was in, killing him. Return to Lord Iowerth at the Elf Camp. He will give you a letter for the King as proof. He will also give you access to Arandar pass.
You can choose to teleport out, or use Arandar pass. If you leave by the Pass, use the above map to help you get there. The path exits south of the Tree Gnome Stronghold.
Returning Home... a hero?
As you are about to head into a castle, an elf will appear. He seems to know everything that's going on so far. He'll open the letter and show you what it says, and what is really going on...
He'll ask you to be a spy on the inside, saying that the war for all life is at stake. If they open a portal to Zamorak's world, then all is lost. Deliver your message as if nothing happened.