Keep in mind, the game is not real, and it does not have to follow most of real rules.
Also, you want to keep an algorithm as simple as possible, getting somehow believable result at the same time.
Throw away everything, except few rules that make sense for a game and fit into it.
1. Roads connect places. This is good rule. It fits into game concept and allows to explore the world without need to constantly check your map. You just follow a path defined by road and you end up somewhere - a city, or other settlement type, or ruins, or tomb, or camp, whatever point of interest you want.
2. There should be various roads (not many types), e.g. stone roads between big cities, dirt roads leading to smaller settlements, and abandoned variations of both types for ruins and wild, secret or hidden places.
3. Roads cross each other sometimes. Period.
4. Roads are not straight lines, for various reasons. And, human's eye likes when roads are constantly wriggling, it gives more natural look to roads.