You can get the Sukimap(スキマップ) from Chen, who is in the abandoned village, east side of Youkai Mountain.
I, personally, am really amazed that you went through everything by, um, bicycle.
Unlike its Pokemon counterpart, this 'Fly' works even in caves and buildings.
With this, you can even do things like fight Yuki, gap back to Makai, then fight Yuki again for easy grinding.