[Loren]

Originally Posted by lch

In my opinion, there are too many variables about moving armies that you really can't let the AI do this for you. Some of those just include:
- which way to move, depending on terrain

Non-issue. Algorithm (I hope the line wrapper leaves this alone!):

Data structures: An array with one cell per province. Each cell holds a turn count and a pointer to a province. Queue of provinces and turns used. Inner queue of provinces & movement remaining.
Load the stating province into the queue.
Repeat
Read province from queue, add to inner queue.
Repeat
Read province from queue.
Iterate across neighbors, add them to the inner queue along with remaining movement.
If the province in the map is empty, fill it with the turns used and the origin of the current move segment. Add the province to the outer queue.
Until inner queue is empty.
Until the target province has data or the outer queue is empty.
If the target has data:
Current = Target.
While Map[Current].ComesFrom <> Origin do
Current = Map[Current].ComesFrom
Move the army to current.

Runtime: This is linearly dependent on the number of provinces * the average number of provinces you can reach in one turn.

- what to do about enemy provinces and/or enemy attacks along the way

Recalculate every turn.

- adding units encountered in provinces along the way

The simple answer, albeit with a file format change wouldbe to add two movement modes:
Gather like--the commander attempts to add any units that match what he's already got. They are added to the same groups.
Gather any--the commander picks up any troops he can.

- how to handle supply problems when moving with multiple big armies

See my previous approach. Run the calculation as above twice. Once normally, once rejecting a province if adding the current army to the already-planned contents of the province would result in starvation. If the second run is no more than one turn longer simply use it. If it's more than one turn longer look at what's eating the supply--if it's armies on move orders then wait, otherwise take the longer route. (Actually, internally you would do both calculations at the same time.)

This handles almost all cases. It will fail in a case where you need to distribute the armies through multiple bottlenecks--they'll all queue up for the shorter one and won't optimize the food use (Say, A needs 100, B needs 80 and C needs 60. The province feeds 160. This approach makes A go first, B & C wait.) It will also fail if two armies are trying to pass each other in opposite directions through a two-province bottleneck where neither province will feed both armies (This case will be detected, though, and you'll get a message.) Such bottlenecks are rare and armies crossing like that is also rare.

In general, I think that even a sophisticated solution for this, which would take an immense amount of work to set up, would be inadequate and require constant fine-tuning all the time anyway. Shortcuts to pool gems and so on that are already present in the game are usually pretty simple stuff, and as soon as it gets a little more complex (e.g. remote site searching) people are not too impressed with the results. Something like army movement is decidedly non-trivial to me.

In a situation like this an exhaustive search is a realistic option. The only time I've seen pathfinding problems in a game that could use such an approach involved fog of war issues or improper handling of an impossible route. The army came along and found the path blocked. It turned back to take another route, once it got far enough away that the blocker was lost in the fog it turned around to take the short route again. (The real culprit here was mishandled fog of war--stationary items in the fog should be as you last saw them, not vanish.)