We know that Polaris (the North Star, alpha Ursae Minoris) didn't always point towards North (nor will it do forever).
So how did ancient people find their way around in an absolute way (I'm not just referring to going "upwards" from, say, a town for X amount of days to find another town), before they could use Polaris as a signpost? Otherwise put, how did they locate North, or any other direction, when they were exploring (/stranded in) a new place? I'm thinking specifically about the night-time, e.g. in navigation and the like.
They still used the sky, even though they couldn't be so accurate. For example, in the Odyssey, which was written when Polaris was eleven degrees away from the Pole, Odysseus navigates by the also-non-polar Great Dipper:
He never closed his eyes, but kept them fixed on the Pleiades, on late-setting Bootes, and on the Bear - which men also call the wain, and which turns round and round where it is, facing Orion, and alone never dipping into the stream of Oceanus - for Calypso had told him to keep this to his left. Days seven and ten did he sail over the sea...