Interesting this topic comes up because I was just playing Cthulhu Saves the World for the first time yesterday and it's an overall fine game, but one of the things I was thinking about while I was playing was how confusing the maps were, especially if you're trying to get all the treasures, and how random encounters definitely don't help with that. Fortunately, each area only has a certain number of random encounters, after which point they stop, so I just grinded out the random encounters near the entrance of an area and then explored.
It's also fortunate though that both Cosmic Star Heroine and Cthulhu Saves Christmas, later games by the same developer that I had personally played first, are much, much better about this and I had no issues with the maps in either of those games.