If you do not happen to be interested in algorithms, as most people aren't, move on, because this post has nothing for you :p
That being said, I was having an infantry unit collect some a single province and return to his base city, so I used a waypoint. I noticed that the way he took to the province and back to the city was different. This is surely not optimal, because one of these must be the shortest path, and the shortest path to and from a city is identical. I tried using both paths alone separately, and yo and behold, one was better than the other, and better than the thing that was automatically set by the algorithm.
My assumption is that the algorithm used to determine paths is either greedy, or approximate using heuristics. I'd like a dev to comment on how these things are computed.
My suggestion, is that since a map has <10000 provinces, then an O(n^3) precomputation application of Floyd-Warshall APSP algorithm for each unit would be sufficient to generate all optimal paths in O(1) query time!
That being said, I was having an infantry unit collect some a single province and return to his base city, so I used a waypoint. I noticed that the way he took to the province and back to the city was different. This is surely not optimal, because one of these must be the shortest path, and the shortest path to and from a city is identical. I tried using both paths alone separately, and yo and behold, one was better than the other, and better than the thing that was automatically set by the algorithm.
My assumption is that the algorithm used to determine paths is either greedy, or approximate using heuristics. I'd like a dev to comment on how these things are computed.
My suggestion, is that since a map has <10000 provinces, then an O(n^3) precomputation application of Floyd-Warshall APSP algorithm for each unit would be sufficient to generate all optimal paths in O(1) query time!