Most other RPG's tend to have some kind of compass, or alignment of screen with N.S.E.W.  But why not have a quest at the beginning to gain a compass - maybe in tutorial.  this could then be part of say camera, so as you turn etc it shows you direction of movement or vision.

I have seen other RPG's that often have a "discovered area" type map, so why not have a map that "grows" itself as you discover somewhere - or you click "save journey" in order to draw your route.

In order to get this magic map, this could be in the form of a spell/glyph you could buy or win as a quest.

Just an idea....