How about mapping by thermal landmarks? The species could be temperature sensitive, and developed its mapping system according to general temperature changes over the landmass. Perhaps combined with some form of topographical element.