Soldier pathfinding can deadlock in narrow areas

[Nicolai Hähnle]

In narrow passages, such as in the map "The ancient sun of fire", the soldier pathfinding can cause deadlocks. When large groups of allied soldiers try to go into opposite directions, neither of them will give way, and the game cannot get itself out of this situation.

Workaround: When this happens to your own soldiers, you can resolve the deadlocks by destroying one of your military buildings that the soldier came from.

Reproduce: I am attaching a savegame of "The ancient sun of fire" which was graciously provided by Andi Hotz in bug #612348. (That bug was a mixture of different, vaguely similar soldier-related bugs). Load the savegame and attack one of the orange Guardhalls with a large group of soldiers. Then a bit later, but before the first group of soldiers returns, attack the other Guardhall with a similarly large group. They will get stuck fairly reliably.

[Astuur (wolfsteinmetz)]

It seems as if it does not have to be a narrow space.
I guess this one is related:
I had a mass fight (40+soldiers from each side) partly in mountain terrain.
All went fine, except one pair.
The enemy soldier was in walking animation, but could not pass my soldier, who in turn
kept hitting at him without any effect. Others were standing guard.
I ignored it for a good while, and then used the spot where they were fighting
for building a sentry.
That warped them from the location and they started and finished a regular fight.

[Nicolai Hähnle (nha)]

That sounds to me like it might be a separate bug. The kind of pathfinding deadlocks mentioned in the original description should resolve themselves after a few seconds if there is enough space. If you still have a savegame/replay that exhibits the problem you saw, could you perhaps open a new bug report and attach it?

[Astuur (wolfsteinmetz)]

Sorry, haven't kept anything.
Next time around ...

[Shevonar (shevonar)]

I just produced a very stable deadlock. It does not resolve itself for a long time (maybe never).
I will have a look at this bug at the WiHack.

[Hans Joachim Desserud (hjd)]

>I just produced a very stable deadlock. It does not resolve itself for a long time (maybe never).

This resolved itself fairly easily once I attacked one of Shevonar's buildings. They then proceeded to attack what I assume was their original target.

One interesting thing I noticed is that at the way back they started attacking the building I had taken over. I wonder if this could be because it was because it was the building they had left and they just wanted to get back in.

If you intend to look into this bug, see also bug 782744 which I am not sure whether is a duplicate or a similar issue. There may be some common issue which have triggered it in both games.

[LAZA (laza74)]

So the solution is to destroy the military building, i think it is a FEATURE:

If the player attacks the enemy an sees, he is outstanding...
the player can DETACH the military building and the attack is canceled.

Just for information!

[SirVer (sirver)]

See also bug 923129

[SirVer (sirver)]

I guess we will not fix this for b17. This is really hard to reproduce and noone has an idea yet how to fix this.

[Nicolai Hähnle (nha)]

Some thoughts on soldier pathfinding.

1. This type of deadlock is best solved by taking a more global perspective on soldier pathfinding. Right now (bzr6539), soldiers individually find their own paths, and some heuristics are thrown in to allow soldiers to find their way around waiting allies. However, this type of deadlock can only be resolved if some soldiers voluntarily go _away_ from their preferred position. It seems easier to reason about this from a global perspective.

2. Given that every soldier has a position where they want to be, the goal of global soldier pathfinding should be to minimize the sum of distances of soldiers from their preferred positions. Furthermore, this sum of distances should be minimized quickly (in terms of gametime).

3. Minimizing this sum of distances as fast as possible is difficult to do, but we can settle for reasonable heuristics.

4. Unfortunately, it is possible to get stuck in local minima. By this, I mean a situation in which the minimum sum of distances to preferred positions has not been reached, but any further decrease requires the soldiers to make several steps, some of which may _increase_ the sum of distances in the meantime.

5. To solve this bug once and for all, we would have to identify a set of non-local moves that guarantee that we ultimately convergence on a global minimum. To avoid further bugs in the code, these non-local moves should have some sort of clean, non-hackish description.

So there are tough questions that still need answering, for a bug that is annoying but should rarely be a problem in practice.

[wl-zocker (wl-zocker)]

I have noticed that heavily injured soldiers can walk through other soldiers still waiting for a fight. Soldiers that have conquered a building, but that have gotten no place in it (or the building has burnt down), won't walk through soldiers when retreating. This (attacking vs. retreating soldiers) causes the deadlock described. A solution would therefore be to allow these soldiers to walk through their comrades.

[Kai Dietrich (0cs935kb517wwm-mail)]

So, deadlocks are a tough problem ...

StarCraft 1 had a similar problem with their pathfinding algorithm: The drones near the base that had to collect the crystals were to many and would constantly get stuck. They solved it by disabling collision for the drones when they are collecting crystals.
Here is the blog post: http://www.codeofhonor.com/blog/the-starcraft-path-finding-hack

Could this hack maybe help here, too?

if(soldiers_stuck_for_too_long()) {
  disable_collision_for_seconds(3);
}

I real sollution would involve a read deadlock detection and resolution ... not so easy.

[SirVer (sirver)]

Setting to incomplete for bug sweeping.

[Launchpad Janitor (janitor)]

[Expired for widelands because there has been no activity for 60 days.]

[TiborB (tiborb95)]

Is it the same issue as in bug-1457425 "Fight never end (also not 2h later)" This one was fixed in rev 7485...

[Hans Joachim Desserud (hjd)]

Since we haven't had any response since the previous comment, I'm going to go out on a limb and mark this as a duplicate of bug 1457425. If anyone are able to trigger similar problems in a recent development version, please leave a comment here or file a new bug report. :)

(Note that this problem might not be 100% fixed, since there is some ongoing work with bug 1395238 as well)