Path finding does not prefer friendly territory

[sumpfralle]

Engine version

1.10.13405

My Operating System

Debian sid

Map name

Total War: December 1941

Can you describe how to trigger the error? (eg: what sequence of actions will recreate it?)

Try to move a unit with three movement points to a friendly territory, that can be reached within one move.

The shortest path to the target territory leads through one enemy territory (both the source and the target are neighbors of this enemy territory). The path selection prefers the path over the enemy territory (in a non-combat move).

Instead of this error, what should have happened?

The path over non-friendly territory should not be considered (especially not in a non-combat move).

UPDATES

• So I took an initial pass to improve route finding for equal distance options: Improve route finding to consider friendly and requiresUnits #4498
• Comparing non-equal distance options was added for non-combat land moves: Improve Route Finding To Consider Longer Routes #4512

[RoiEXLab]

Could you provide a Screenshot?
I think I know what you're asking for, but it's a bit hard to follow your explanation

[ron-murhammer]

@RoiEXLab I'm fairly sure this is referring to route finding not prioritizing friendly over enemy owned territories for non-combat move. Here is a save game where you can try moving the train from Eastern Germany to Hungary Slovakia or Austria where both moves are legal through Poland but route finding tries to move through enemy owned Bohemia:
test.zip

There is also another thing that route finding doesn't consider which is unitsRequiredToMove (rails) in TWW. Both of these are on my list of things to improve so I can try to take a swing at this.

[RoiEXLab]

@ron-murhammer If it's just preffering friendly territories over enemy territories with the same total distance then just sorting the neighbour territory list (friendly before enemy) before adding to the queue might already be enough already.
If actual distance should play a role, then this becomes a non-trivial task.
For rail mechanics you might need to introduce a priority queue to replace the current queue. And give rails a lower weight

[ron-murhammer]

@RoiEXLab Yeah, its potentially both though when the distance is equal is the more common scenario and much easier to address. If equal distance options at least consider territory ownership and rails that would be a good start.

[sumpfralle]

In my specific case it is about two paths with different distances:

• over non-friendly Uzbek: 2
• over friendly Southern Iran and Baluchistan: 3

The unit in question has a movement limit of three - thus it should be able to reach its destination over the longer friendly route in one turn.

[ron-murhammer]

@sumpfralle Ok, thanks for the clarification. That situation is the more complex one as it then leads to the question of if I would try to move an inf instead of a truck over that route should it show 2 moves over enemy territory like it does in your screenshot or 3 moves over friendly territory. In other words, should you only consider prioritizing longer distances if the unit has enough movement to make the move in the current turn.

[sumpfralle]

I could imagine, that the case of source and target being friendly territories indicate under all circumstances (for combat moves as well as for non-combat moves), that the unit needs to move over friendly territory only.

[ron-murhammer]

So I took an initial pass to improve route finding for equal distance options: #4498

I'll leave this open for now to further consider comparing non-equal distance options.

[Cernelius]

What does "equal distance option" mean? I understand that this means that it may give a possible path that is not actually the shortest possible one. Other than this, will it always work for the case of having a 3 moves possible path over a 2 moves impossible one and, if so, will it always give a possible path, if anyone exists?

[Cernelius]

Regarding what said in the linked pull, "consider friendly" is not fully covered by looking for "not enemy owned". A territory is also hostile (not friendly) if it has hostile units in it, that is usually the case of the sea zones (not being territories), but it may also matter for passable land territories having units belonging to another player you are at war with. Has this been taken into account, or the matter is now limited to ownership (thus totally or mostly irrelevant for sea units).

Regarding the ownership, I wonder if these matters have been taken into considerations too:

1. The territory being impassable.

2. The territory being owned by an archetype Neutral player.

3. The relationship option "canMoveLandUnitsOverOwnedLand".

4. The relationship option "canMoveAirUnitsOverOwnedLand".

5. The relationship option "canMoveIntoDuringCombatMove".

6. Sea territories (meaning sea zones with an assigned territory ownership; usually convoy zones) (differently from land territories, always being passable if the unit is not a non-combat transport or the property "Transport Control Sea Zone" is enabled).

[RoiEXLab]

By equal-distance option we're referring to the case, where there are multiple paths to a territory with the same amount of paths in between them, with the difference that some paths cross enemy territory while others don't. In this case it's trivial to prefer paths that don't cross enemy territory by trying to find a path through friendly territory first, with the same rules as before.

However it's not trivial to create an algorithm that can guarantee to take a path through exclusive friendly territory if one exists for the maximum distance, potentially having to use a slightly longer path.

So we're not talking about what is friendly territory, instead about what could be done if we knew that without completely killing performance and how a friendly route should be valued over the shortest route.

[ron-murhammer]

@Cernelius As @RoiEXLab describes, the logic is only currently looking to prioritize between route options that have the same number of territories so it would never prefer a longer route having only friendly territories over a shorter route including enemy territories.

Of the list of options you have, everything but 5 is already considered (6 only to some extent).

Generally route finding works the following way (this is somewhat simplified):

1. Find the shortest route between the 2 territories considering impassable, restricted, neutral rules, canMoveLandUnitsOverOwnedLand, canMoveAirUnitsOverOwnedLand, territory effects, and canals. These are generally considered hard blockers that we want to avoid showing a route through if at all possible. If no legal route is found then it removes a few restrictions at a time til in the worst case it is considering none of these and just finding the shortest route between territories. As soon as it finds a route that becomes the default route/distance to compare against.
2. Consider prioritizing routes with only land or only sea based on start and end both being one or the other and units being moved. This will become the new default route/distance if it can find one.
3. Consider the 'nice to haves' which include in this order: requiredUnitsToMove, not enemy owned, no enemy units, and no fly over AA.

Example:
I have a territory A and B which have 3 routes that are 2 move distance through say territory C, D, and E (A-C-B, A-D-B, A-E-B). Let's say all of these pass all of the hard blocker checks and are all purely land routes. Then I would try to compare them using the 'nice to haves' and let's say C is enemy owned, D is contested with enemy units but friendly, and E is friendly with no enemy units. It would prioritize route A-E-B.

My advice would be to test the latest pre-release and see if you have certain scenarios where route finding could be improved.

[ron-murhammer]

@sumpfralle The latest pre-release should address improving the route finding scenario you provided and many other similar ones.

[sumpfralle]

@ron-murhammer: thank you! I am just trying it :)