How hard would this be? It would pretty much do what happens in A Link To The Past.
1. Link plays the flute/ocarina (With a playing sprite)
2. Bird/whatever swoops down, picks him up with another sprite.
3. Switches over to a selection screen, where Link can choose to warp with the name on the screen, with a basic map of the world.
4. Select a spot, and Link is transported there.
Perhaps another thing would be that certain parts of the map are blocked off with cloud or something, until you get to/past that area. And Link would activate the warps by going onto the same screen as where he would be warped, or by interacting with something on the screen.
Would this be terrible difficult?

