It's not easy to find another route. Regardless of alternate routes, I'm terrible with directions, so I wouldn't easily find my way between Galadon and Hamsah without using Eastern.

So... I take a deep breath while outside whichever town I'm near, and run into town, out the gate, and down the road. Always alert, but moving quickly, and hoping to avoid an ambush.

There are a few other alternatives. One, taking the fights as they come and winning. Two, magical means: teleport, gate, potions, etc. Three, just plain avoiding half of the world for most of your time.