qazxc said:
A tribe of hunter-gatherers can exhaust an area of game and other resources fast, and thus are likely to travel several hundred miles in a single generation.
Not all nomads are hunter-gatherers and not all hunter-gatherers are nomads. Some nomads are pastoralists: the Kuhi sub-tribe of the Kashkai (a confederation of tribes in Iran) for example travel about 540 miles a year.
A single generation is roughly a turn in the beginning of the game. A tile is several hundred miles.
The 540 miles that the Kashgai travel is not without the aid of domesticated animals. This is not the case for the stone-age tribe that just learned about plant and animal domestication (thereby seeing the advantage to settling down, i.e. we didn't learn horseback riding yet). And it is not in a forward direction but cyclical (i.e between 2 tiles) between winter and summer pasture lands. They would only be directly familiar with 3 tiles at most. This is typical of nomadic tribes, they do not typically go "forward" but rather range within an area. (Especially in an area that has other tribes surrounding it).
Old World nomadic habits were much more sedentary (this isn't the best word, but I can't think of the right one) because by the time frame postulated by the beginning of the game the world was claimed other tribes or very dangerous. You couldn't go hundreds of miles before other tribes tried to turn you back.
On the other hand, (let's start at ~11000 BC instead of 4000BC), let's look at North America. Here we see the native American settlements expanding rapidly into open areas. These hunter-gatherers (and they nearly all were at this time frame) were travelling on foot (the Americas had no useful domesticable riding). These did fit the model you were talking about, better than your examples. Within a few centuries they killed off most of the big game (mammoths, etc.) and settled the Americas. It was fruitful, for a while. Even so, people did not typically travel thousands of miles
as a tribe in a linear direction in one generation.
By the time Columbus "discovered" America, even the hunter-gatherer tribes (there were obviously settled agricultural societies by this time) had territory claimed and were quite willing to fight over it.
Your point about oral traditions is well taken, though. Maybe there should be an incorrect "map" of the area passed on from your ancestors. I remember learning about the "Old Country" from my grandma and grandpa. Huge forests, fertile grain, good beer, evil dictators, tanks, giants, trolls, all across the great ocean. Seriously, in the days before writing, oral tradition was stronger and (hopefully) better passed on to the next generations.