From what I recall, Phoenicians (whose capital fell in 332 BC and their civilisation stretched back to 2500 BC) navigating Mediterranean and Atlantic used the sun, Polaris (yes, our North Star), and the entire Ursa Minor (Little Dipper) constellation in conjunction with landmarks to navigate both at night and during the day. I added the dates to give a reference to the circle in my above post: Polaris wasn't exactly their North Star, but it was both visible and, mostly, good enough.

During the last night-time orientation run, between thick forest and cloudy weather, couldn't even see the moon most of the time. I used the memory of "where the dirt has more calcite stones" or "how this mountain's silhouette would look if I was at <place I knew like the back of my hand>" or even "the air is very moist, I'm walking windward". You don't need exact reference points, just orientate well enough to get the gist where you are and which direction roughly points to your destination. Anything will do. North Star is convenient, but isn't much on its own.