So, I looked at the impromptu routes post and thought "what if I used a dice map instead?"
Here's a tentative result.
Print the image so that it's an 8 inch by 8 inch square. The center represents the starting settlement. For heavy population density areas, roll 5d6 on the sheet; everywhere a die lands represents one settlement in that direction relative to the starting point. The ring it lands in tells you what size settlement; if there is a multiplier, multiply the die result by the given number to get the total leagues to the settlement.
If a die lands in the center, feel free to define underground settlements.
For lower population densities, use 5d12 (light density) or 5d20 (sparse density.) To map out nearby kingdoms, the dice results are in weeks of travel instead of leagues.