Better shortest path finder

[GChapman]

The shortest path finder is just a path finder. It isnt the shortest path. I found this pretty bad.

This is the path the game wants to take. It will take 52 days.

I decised to manually move the army, since i know for sure there much be a quicker path. I came with this path. It takes 32 days.

This path is a lot faster (Around -40%). It is a bit strange that the AI wont take the shortest path. It would be nice if the pathfinder gets an update, so it really determines the shortest path.

Note: I just discovered this issue at this moment. Maybe there are even worse examples. In this case forts arent an issue (Serbia is neutral) or it doesnt use ships to transport the army.

 

[magnusvejby]

I think one of the reasons for the long paths is to avoid attrition in neutral and enemy land. But i agree it could certainly use an update.

 

[GChapman]

I think one of the reasons for the long paths is to avoid attrition in neutral and enemy land. But i agree it could certainly use an update.

Good point. The shortest route is with attrition (low supply limit), the route of the AI is without attrition.

 

[TheDecider]

Here is an old thread of mine with some pics I took, I think the algorithm is an A* and just "walks" towards the direction of the target, it doesn't perform any search:
https://forum.paradoxplaza.com/forum/index.php?threads/lets-talk-pathing.781804/

 

[GiftGruen]

It seems the algorithm performs badly whenever there is a path it can't take (blocked by navy or fort). My speculation: If there is something blockading the direct path, it splits up the computed path into two segments, the "I can walk until here" part, and the "I can walk again from there" part, and omits anything inbetween. It then computes the shortest way to connect these two parts. Let's say your army is at point A, wants to go to B, can only walk until C unhindered and could walk unhindered from D to B on the direct path, only provinces between C and D are blocked. It then connects C and D, making the path look very odd and ineffective around provinces C and D. It seems to understand the ineffectivity of going somewhere and backtrack from that province, so if a province B would have to be crossed twice like this: A-B-C-D-C-B-E, it omits the whole part between the two same provinces: A-B-E. If however the path does not do that, so if the path in the first example never crosses, it isn't corrected.