Sometimes when selecting two armies located in the same province, ordering them to the same province will cause two different paths to be generated, probably to reduce attrition damage?
PI, your path finding needs some work...
- Thread starter TehJumpingJawa
- Start date
-
We have updated our Community Code of Conduct. Please read through the new rules for the forum that are an integral part of Paradox Interactive’s User Agreement.
thinking out loud here, but wouldn't it be possible to 'steal' some code from a GPS, and feed it a map where each province is an intersection with roads to the neighboring provinces to each province, and tell it how many units long each road is, and then let that find the shortest way from Province ABC to XYZ? ... while it might be a large number it would certainly be finite and from my (admittedly somewhat limited) knowledge it shouldn't be that taxing for.
- 1
.png){kind=avatar}
I've never seen this behaviour, in fact I usually have to manually force armies to take different routes precisely to avoid attrition.
I suppose hypothetically it might be possible for the armies to take different paths, if the two armies had different manoeuvre ratings, and rounding was applied during the cost evaluation(rounding to a whole number of days).
E.g.
Start---6---6---Goal
\_____12_____/
Army A, no manoeuvre bonus, picks the top route (same cost as the bottom route, so arbitrary choice)
Army B, 5% bonus, picks the bottom route; rint(6*.95) + rint(6*.95) = 12; rint(12*.95)=11
Though I doubt very much it's implemented anything like that.
As I said, I've never seen 2 armies in the same start node, take different routes to the same destination (unless ofc one was exiled, or fort ZoC was screwing with the paths)
Last edited:
If it's implemented as one would expect, that's precisely what it is doing.
The general algorithm is called A* (A-star), and is a "best first" search algorithm.
By using a problem specific heuristic, it explores the node graph more intelligently than simple breadth-first or depth-first search algorithms.
Last edited:
- 1
Can't easily explain this behaviour 
Auto-pathing:
Arsi -> Gonder; generates erroneous very much longer route.
Gonder -> Arsi; generates correct shortest route.
A* certainly shouldn't make such broken paths. (unless the heuristic is really quite broken)
Auto-pathing:
Arsi -> Gonder; generates erroneous very much longer route.
Gonder -> Arsi; generates correct shortest route.
A* certainly shouldn't make such broken paths. (unless the heuristic is really quite broken)
That algorithm REALLY hates leaving home turf.Can't easily explain this behaviour
While I really like the discussion on search algorithms and path finding, I'd like to repeat the "save games please" for specific situations. It doesn't seem like the algorithm as a whole is broken, but there are specific edge cases where (presumably due to rounding or "good enough" conditions) the results are suboptimal.
I always just assumed this was due to the stupid zone of control nonsense. I might have to manually plot courses for my armies from now on.
A question about pathfinding in General in Paradox Games.
Does it only look for the shortest route, or does it also look for a short route with low attrition on the way, because of insufficent provincesupply?
Does it only look for the shortest route, or does it also look for a short route with low attrition on the way, because of insufficent provincesupply?
Considering there's suboptimal pathing all over the map and it's 100% reproducible (not talking about anything to do with forts here, just cases of the algorithm spitting out bad paths), do you really need actual save games?
Just load up a new game as the Timurids and try walking from one end of your country to the other. There's your save file, the unmodified 1444 start.
- 1