Desert of Shifting Sands

- Head to the Library of the Ancients and pop inside. Cid and Mid will be here, assuming you’ve visited Crescent, and they’ll tell you to head to your next destination. Leave the Library and walk west, through the mountains, until you come to a desert. You’ll be sent to the next ‘dungeon’ area upon entering, and now that you’ve spoken to Cid and Mid you can actually wander around - though first you have a boss to fight. Kind of a reverse, facing the boss first, but there you go.

Sandworm

Not terrible, but bad if you have a poor setup. The Sandworm is accompanied by three Holes, and it will jump from Hole to Hole, occasionally smacking you or using Sandstorm to inflict a small amount of damage to everyone. While doing so it will take damage as though it were always in the back row, making magic or long-ranged weapons a must - but if you use magic on the Sandworm, or accidentally attack any of the Holes, one or more of your characters will be hit by Gravity and lose half of their current health. Consequently, you’ll find this battle to be one of gradual halving. This is especially bad if Sandworm uses Quicksand to inflict sap on your characters to eat away at their quickly-reduced HP.

Nevertheless, magic - specifically, the Blue Magic spell Aqua Breath - is probably the best way to win, as the Sandworm is weak to water attacks. One hit may kill the thing. Water Scrolls from a Ninja are also quite good, and will allow you to target the Sandworm alone. Barring these it will be a battle of attrition over time, though not an amazingly difficult one as long as you can heal.

- Beat the Sandworm and you’ll have a path to the south. This will allow you to hop onto the sand streams leading around this area. This looks like a complicated, promising area… but, in truth, there are no items to be had. Hop on the sand streams that will spirit you west, staying in the north until you reach the far west, then head south as far as you can go. To the east is the exit. There’s a pyramid in the middle of this area, but you can’t access it yet, so don’t bother trying.

- You’re done with the Desert. Head south and you’ll find a small town.

Gohn

- This town seems empty at first glance, but if you head north and then back to the southy ou’ll see a figure walking around. Follow him east to spot him a few times, then back west and north, up the central staircase.

- You’ll wind up getting dumped into a basement. Watch the cut scene and head west. A teleporter here will send you zipping across the world, and after more cut scenes you’ll be free to explore what is called the Catapult. The path splits when you head upstairs; you can sleep in a room to the south. 

- In the far south, through the west room, is a switch on the wall that has a note. This will send you to a few different places - the planter in the sleeping room, the notebooks in the right room, the left urn in the left room, the book that falls down as a result - then back to the switch. Hit the switch to unlock three nearby chests containing two Shurikens and the Mini spell.

- In the northern room is another switch on the wall, beside the northern door. Hit it to open the door in the north. Through another room you’ll find a dock - and the dock leads to not only the Fire-Powered Ship you thought you lost, but an airship. Once you’re on the deck of the ship, though, you’ll come under attack.

Cray Claw

Honestly, an easy fight. The Cray Claw is capable of reducing your characters to single-digit HP with its attacks, but it’s slow in delivering - and seems to like attacking the same character with the same attack, which is basically a waste of its turn. Use electrical attacks (Thundara, Spell Knight attacks, Lightning Scrolls) and you’ll waste it in no time. You’ll earn a Frost Bow for winning the fight…

… and you’ll have control of the airship. to boot. You can use this vehicle to reach virtually every area on the map. You can also return to the Catapult, if you want, and dock up to restore yourself for free. One crystal left!