1d10You may also use some d6s and d20s as follow-up rolls for this step.
3d8 of one color ("light",) another set of a different color ("dark")
Start with the assumption that the player characters begin at the center of the map. This is based on the assumption that we want substantial travel time in the wilderness before having to draw another kingdom-scale map. If the dead center of the map wouldn't make a good home base for some reason, move the starting point to the closest hex that works. Home base is not necessarily the capitol of the kingdom; it's just the center point we use to figure out the position of settlements.
The d10 is the size (diameter) of the starting kingdom or territory, in hexes. This also tells you whether the territory really is a kingdom (5+), principality (2-4), or barony (1.)
The 2d6 roll is the status of the kingdom. Use the standard 2d6 reaction table if things are Normal, Good/Bad, or Very Good/Bad. If times are Good, political relations are peaceful and the kingdom is growing; Very Good means the equivalent of a gold rush. If times are Bad, supplies are scarce and people are worried; Very Bad means the kingdom is at war with one or more neighbors.
The 4d4 places the neighboring settlements. The direction of each d4 relative to the d10 is the direction to the settlement from home base. The result rolled on each d4 is the number of hexes to that settlement. If the settlement is outside the kingdom's borders, it's a colony of the kingdom, but intervening land isn't completely under the kingdom's control. The settlement's kind/size is determined when PCs travel to or ask about the settlement in play. Each settlement is connected to home base by a road; roads go around lakes and high ground/mountains when possible. Each road may continue past each settlement or may have branches, but only traveling the road will determine this for sure.
The two color sets of d8s represent major neighbors. These are interpreted as directions, as we did for off-map bodies of water. The "light" set is the direction to off-map cities or kingdoms. The "dark" set is the direction to neighboring settlements that are not part of the home base territory; in other words, these are trade partners, rivals, or enemies. The minimum distance to each neighboring settlement is equal to the diameter of the starting kingdom; if there is a colony between home base and the neighbor, measure the distance from the colony instead.
At this point, name all the settlements on the map, if you have names in mind. If not, we'll give them three-letter abbreviations using 2d20 and 1d6 rolled together and read left to right as a word, using this familiar table: