Roads is a great idea, but as a software developer I don't think having the AI calculate whether its faster to go offroad or not is a good idea as it may be expensive computationally when you have a LOT of ai parties on the map. Rather, I think the rules for following roads should depend on party type and size. For example, caravans, villages, and armies follow roads unless they are chasing/running away from something. Bandits and noble parties don't. A player led army would not be restricted to roads but would get significant off-road speed penalties.