Hitch a ride on the sesame cart between the three of the main locations: Dog Fort, Altar of Cats and Pirates.
Set Malcolm to nice mode when he talks to the dog driving the cart.
Note that the bottom of the screen is usually the direction you came from.