Hehe, I'd stay away from fonts with overly descriptive names For some reason they often try to hard, and end up looking exaggerated, in my experience. With fonts, subtle is best, I think. I looked through my collection for fonts that might work and found Chalkduster (could look like it was written on a cave wall), Herculanum, Hobbiton (also a little exaggerated to be honest), Letter Sseungi (a bit Asian-inspired), Lithos Pro (very subtle, but I like it), and Papyrus (somewhat overused, but a really nice font). Some of them are free download, but some where pre-installed on my computer so I don't know if they might cost something if you don't have them. But they could be worth looking into It's also possible to go another way and not try to find something tribal at all, but make the map as if drawn by outsiders, so you could use a nice roman font or even something modern or sci-fi.