I saw an excellent video in a western civ class years ago that discussed roman road building at length. According to the video, building (paving) the roads was a secondary concern. The primary concern was to keep a standing army from sitting. : ) It was proposed that if soldiers were given too much time of their own, the free time, and the discussions that go with it, could sow discontent and could lead to rebellion. By keeping the troops busy building roads and working at other tasks, in between campaigns, the rulers were actually maintaining their control over their soldiers.
Take that for what it's worth. But I would draw the conclusion that if building roads was primarily busy work (useful in itself but not the primary goal), perhaps there wasn't as much forethought involved in the planning of the roads. If that's true, roads could end up more haphazard than we would otherwise imagine. Following coastlines and rivers, and using the most economical route when dealing with obstacles would certainly always be true but if road-building is a less important project, they may not have assigned their best engineering minds to the project.
I'm not saying, necessarily, that is what happened in medieval Europe. Just offering a different perspective to consider when planning your roads.
Also, not all roads connect cities to cities. Walled cities require a great deal of stone. Wooden structures require lumber. Fields require irrigation systems. Many roads would have to be developed to transport materials. Obviously, most folks would want to build a walled city near a quarry given the chance. But when the prince's new bride says "honey, I'd just love to build our home 'there'", the prince will order the construction to begin regardless as to how far away the quarry may be.
Just food for thought.