Thanks to +David Wilkie for his Wiki diving.
Step away from the idea that a map needs to be a survey. Why not, right? The concept of "Map" isn't a fundamental aspect of being human, we made it up. Even our modern maps aren't just sky photos, they've got their own contrivances, an arbitrary level of accuracy more than the one pictured above. Negligible even.
Itineraries tell us where cities or other useful stopping points are, the routes between them, and how long they take. Note, how long, not how far. If the route between Caragnium and Prax goes through a swamp, or the road is poor, or it's a dangerous area that requires careful going, then it will take more time. Just time. The map hardly has any indication of anything otherwise, certainly nothing not within easy reach of the paths. Leave the itinerary and you're on your own.
You can buy these in cities, so they almost always include directions from cities, to cities. Village folk need their wits about them to travel, so they rarely bother.
To generate an itinerary
- You get your two places, any two. Let's use cities, since that's most likely.
- Roll d3 for how many direct routes there are between them
- roll d6 per route for the number of settlements on the way
- roll d6 for each settlement - 1-3 village 4-5 stop (fort, tavern, waystation etc.) 6 something weird but traversable (ghost town, bandit canyon)
- roll d6 for each connection - 1-4 one day travel 5-6 +one day, roll again
- Paint in implied terrain. Anything you could see from the road and use as a directional aid (maps don't care for anything further)
See here, we have two cities linked by 3 routes with 6, 4 and 3 stops on the way. The top route will take a total of 11 days, middle 7 and bottom 7. Since one is quite a bit longer than the other we can guess there is likely stuff in the way between the top two routes. Some hills here, a swamp there, done.
Now, when you get yourself one of these maps from an itinerant you have to remember they aren't always accurate. Things can change, people can be dumb or liars. Maybe he got it from another traveller and wrote it down wrong? Maybe the road is washed out?
How do we resist marking all the villages and forts and ghost canyons? Easy. If you don't remember a place or a village when you come to do another itinerary it's probably not on the way there. A city will have tons and tons of settlements within reach, it's plausible to not visit the same one twice (unless it's interesting and you remember it vividly).
What about the wilderness? Well it's wild. You know roughly what form it takes so just roll with it from there. No one goes cross country. No one! If you take the party offroad then you just decided to have a capital A Adventure. You may or may not turn up where you wanted. Remember, those trails are only relative to the beginning and end, the parallel paths might as well be on the moon for how accurate they are to each other.