Get the Map
In the first room of Wing Dungeon, the owl tells you that a good defense is the best offense against spikes. Get your shield ready and go to the next room. (If you don't have a shield, go find the Deku Scrub who sells you one for 10 rupees to get the best deal, as described in Western Woods.)
In the next room, use your shield to make the Spiked Beetles flip over. Then kill them with your sword. Go through the door on the left that opens.
Push the block right three times, down once, left once, up once, then push it to the left until it lands on the black tile and the door opens. Go through.
Push the middle block up and the block to your right to the right. Use a bomb on the cracked wall in the bottom-right corner of this screen. Go through.
Kill any keese in the way and open the chest to receive the Dungeon Map.
Get a Key
Go back to the last room and kill any Ropes in the way. Exit to the northwest, then deal with the keese and exit west.
Be careful of the Sparks. They move along the wall and you can't kill them with your current equipment. Exit to the left.
Kill the moblins and keese in this room to make a small key drop down.
Get a Second Key
Go back the way you came until you are in the room with some blocks blocking the southern exit. Push the upper left block down and the upper right block down, and push the middle one to the side, then exit.
Return to the room with the Spiky Beetles. Get rid of them, then unlock the door to the right and go through.
Be careful of the Ropes in this room. Bomb the crack in the south wall and go through.
Go down the stairs. Be careful of keese in this area. They are hard to see. Use the hanging ladders to get onto the middle stationary platform, then step onto the moving platform on the right when you can. Exit to the right.
Hop down to the lower level and approach the Thwomp to make it fall, then run past when it is rising back up. Use the moving platform to go up the ladder on the right.
Kill the ropes that attack you and then open the chest to get a small key.
Get the Compass
Go back the way you came to reach the room with ropes and holes in the ground. In the upper-right corner, kill any Ropes in the room, then push the lowest block to the side (it won't move until the Ropes are gone), then open the chest to get the Compass. Then exit to the north.
Reach the Mini-Boss
Kill the sword moblins and go through the locked door on the left.
Hop into the rail car. The cart automatically kills any monsters that get in its path, so you don't need to worry about hitting them.
In the room where you end up, be careful of the green Zols and exit north.
Now you need to defeat the mini-boss, Swoop. It will hover over you, then when it flaps its wings quickly, it is about to drop down to the ground, so run out of the way. When it lands, it will break holes in the floor. However, if you get it to land on the blue tiles around the edge of the room, those tiles can't break.
If you fall into a hole, you will land on the floor below. Go east and up the stairs, then west to return to Swoop's room.
Hit Swoop with your sword when it lands. After inflicting a lot of damage on it, Swoop will fly more quickly. When he does this, it means that he will bounce two or three steps toward you when he lands, so run away until Swoop stops bouncing, then hit him.
Get the Roc's Feather
After getting rid of Swoop, go through the upper-right door and go down the stairs.
Avoid the Whisps that float around. If one touches you, you will not be able to use your sword for a while. They are invincible. Go through the south exit.
Be careful of the Shrouded Stalfos in the center of the room. They will throw spears at you. Go to the east exit, being careful of the Green Zol that appears near the door.
Kill the two shrouded stalfos. The owl in here says "with the blue wing, soar over the colored heights." Go up the stairs in the upper middle of the room.
In this side-scrolling area, make the Thwomp drop down, then run past it when it is going back up. Go to the right and get the Roc's Feather. When equipped, you can use that button to jump.
Get a Third Key
Go back to the last screen and use the Roc's Feather to jump on top of the Thwomp. Then when the Thwomp goes back to the upper part of the screen, jump to the left to get up on the ledge and get the 30 rupees on the left side.
There is a ledge to the right of the Thwomp, but there is nothing there. If you want to confirm this, stand on the Thwomp and wait for it to be at the same level as the ledge on the left when you jump.
When you're ready to leave, go to the left and climb down the ladder to return to the room with the owl statue.
Go down to the yellow tile, but don't stand too long on the floor here, because it will collapse. Jump over the yellow tile until it turns red. This will unlock the door to the right. Go through.
Using the Roc's Feather, jump over the gaps to reach the mine cart on the right side of the room. Step in.
Hit the yellow switch as you go past to change the tracks on the right side of the room, allowing you to stay in this room. Use a bomb on the cracked wall to the right and go through.
Kill all of the monsters in here to make a chest appear. Open it to get a key.
Get a Fourth Key
Back in the room with the rail car, push the block to the right once, up once, left once, and up once to open the gate. Get into the rail car.
You can kill the peahats in here when they stop moving. Jump over the tiles on the right until they match the colors on the left. Do this by jumping over the left tiles once and the right tiles twice. A small key will drop down. Get it, then exit to the left.
Get a Gasha Seed
Go up the stairs on the left. Then walk through the key block to the right to unlock it. Go down and hop down from the left side of the ledge, then exit through the south door.
Jump to the right and jump over the colored tile until the gate unlocks. Go north one screen, then left one screen, then use the upper right exit and go up onto the ledge that had been blocked by the key block. Go down and step into the mine car.
In the room where you end up, be careful of the spear moblins. Jump down over the gap to reach the chest, which contains a Gasha Seed. Jump back up and go through the north exit.
Get a Fifth Key
You must use one of the pots to push onto the switch, so throw away all but the upper-right pot, then push it one tile above the hole on the left. Use the Roc's Feather to jump over the gap and get behind the pot, then push it all the way to the right. Again using the Roc's Feather, jump the gap to get behind it. Push it down so it's lined up with the button on the floor, then jump behind it and push it to the right to open the door on the right. Go through.
Go through either of the two south exits. Kill the moblins and the green Zol near the middle of the room.
You have to move the statues on the right side of the room to match the pattern of the statues on the left. The colored tile below the lantern controls which of the statues on the right can be moved. It's red now, so you can move the red statues. To make it easier, switch the tile to yellow and push the yellow statue to the center. Then switch the tile to blue and push the blue statues in place, then switch it to red and push those into place. Get the small key that appears. Go through either of the north exits.
Get the Boss Key
Unlock the east door and go through. There are different colored Gels hiding on the floor here. Jump over the center tile to change the color of the floor and reveal the hidden Gels so you can kill them. They are invincible when they match the floor color. They gradually change to the new floor color, so you will have to keep jumping over the tile to get rid of all of the gels.
Once all of the gels in the room are gone, a chest will appear that contains the Boss Key. Exit through the west door.
Reach the Boss Room
After leaving the Boss Key room, unlock the north door and go through.
Be careful of the Keese and Sparks and unlock the boss door in the right wall and go through. The owl statue here will say that "the red face dislikes smoke." You should equip your bombs and the Roc's Feather because your sword can't hurt the boss. Go up the stairs to start the boss fight.
This boss can be very tricky and frustrating. You have to throw a bomb into the top of the head. If the bomb enters its head when its face is red, you will damage it. If the bomb falls in when the face is anything other than red, it will shoot out flames or rocks and will not get hurt.
If the green face shows after you throw the bomb, stand at the top of either ladder. If the purple face shows, climb down on the ladder and wait for the attack to finish. If the blue face shows, stand on the middle ledge next to either ladder.
If you run out of bombs, Head Thwomp will throw bombs out during its fireball attack.
Try throwing the bomb while falling from the top left or top right ledges on the sides of the room.
Just don't panic in this battle and be patient with getting the proper timing.
Get the Essence
After defeating Head Thwomp and taking the Heart Container, go down the ladder on the right side of the room and exit to the right.
Go up to the altar to receive the Ancient Wood.
Outside, the baby Maku Tree's seeds will float by and she will say that the next essence is on Crescent Island in the South Sea. She says that you can get there from the town's coast.