Openra: Bug Report on Computer Players Path Finding

[dnqbob]

(bug occurs in version from 0314 to 1102)

This bug occurs when map contains terrains make Computer Players have to take a long side path to reach enemy units instead of a relatively directly approach. The attack squads of Computer Players will get stuck and, if serveral attack squads get stuck and cannot be consumed by other players, the game will lag and the "bot_tick" will be very high.

I made a map can reproduce this bug (file and replay below) for newest 1102.
map&replay.zip

And this is the preview of this map, the way that connect two players' base is shown by using the red arrow. When Players try a straight forward approach to each other, the unit's path finding AI will always choose this way.

There are GIFs performing the behaviors on how Computer Players's attack squads are stuck. They just keep trying a short range Attack-Move in order to keep together immediately after choosing the way which is shown in map preview above. As a result, they are all circling in an area endlessly.

[dnqbob]

Upon solving this bug, I have some thoughts.

1. make a reference or record to see the position change after trying M times for Computer Player. If after M times their positions do not change too much, Computer Player can just order the squad head directly into closest enemy, if destroyed, then next closest enemy. Sacrifice their formation.

2. same as 1, but after T seconds they will regroup and return to normal behave and check if they are circling. This one can probably keep the formation at most of time.

[tovl]

This problem is caused by the squad regrouping around the position of the squad leader. The squad leader is determined based on the relative Euclidian distances to the goal cell of each unit in the squad, with the closest unit becoming the leader. This works for relatively simple paths where each step along the path takes the units closer towards the goal, but fails horribly for more complicated map geometries like in your test map. In this case the shortest path towards the goal takes the unit farther away from the goal cell in simple Euclidian terms at first, before pivoting towards the destination and getting closer again. This means that the leader can actually be in the rear of the squad in terms of the actual path length and regrouping towards the leader makes the rest of the squad move backwards along the path.

This is a major blocker for the Tiberian Sun mod because the maps in that game are generally far more complicated with paths that double back on themselves being the norm rather than the exception. Just try spectating an all AI game on A River Runs Near It and watch the horror.

To solve this problem we would probably need to either base the squad leader on the actual path distance or regroup towards the center of mass of the units rather than the leader.

[dnqbob]

This is a major blocker for the Tiberian Sun mod because the maps in that game are generally far more complicated with paths that double back on themselves being the norm rather than the exception. Just try spectating an all AI game on A River Runs Near It and watch the horror.
To solve this problem we would probably need to either base the squad leader on the actual path distance or regroup towards the center of mass of the units rather than the leader.

Yep. I find this bug in an Openra mod so I wonder if I can reproduce it in RA mod.

IN ADDITION, this bug can be more severe when attack squad contains amphibious units.

When amphibious units get into water field and somehow becomes the leader, all the other ground units that cannot entering the water will try to regroup towards the leader, which is impossible. The entire squad will be stuck at water side, with unmoving amphibious unit in water and moving ground units try to regroup. You can reproduce this bug in certain mod while playing map like:

There is a GIF showing how the bug works. This one can be lethal to any mod on Openra contains amphibious units.