Page MenuHomeWildfire Games

Fix chasing when the chaser ID is lower than the target ID.
ClosedPublic

Authored by wraitii on Jan 26 2021, 11:22 PM.

Details

Summary

As reported by feldfeld and discussed on IRC, there is a fundamental problem with fast moving units and MP turns.
Because:

  • movement is "all or nothing"
  • Over 500ms MP turns, cavalry can move by slightly more than 9 meter
  • their attack range is only 4 meters
  • entities have to account for their target moving later in the turn if they want to be in range by next turn

Entities can try to move ahead of their target, thus colliding with them, thus not moving at all, thus never actually going in range.

This happens less if the ID order is reversed because the chased unit moves first, and the chaser has ample room to actually catch up a little. However, if the target isn't actually moving very fast (typically, a trader or a muskox), then the cavalry, which is still going a little ahead of its target, might run in the same issue regardless (it's, in this case, a speed ∆ problem).

Note that this diff introduces another problem, which can be argued to be less bad: the chaser will go through the attacker if its ID is lower and end up "blocking" the attacker when he tries to move (since the move is 'committed'). Thus chased units will suddenly stop. This makes chasing much more efficient compared in the "lower ID" case, which is a little annoying, but perhaps better than making chase just not work at all.
It's quite stat-dependent and only seems to happen with cav-on-cav in A24, so I think it might be fixed by tweaking cav stats.

See test map I'll attach tomorrow & likewise video.

Test Plan

Run the test map. Chase units elsewhere. Do other unit movements (such as head-on collisions, need to check those).

Diff Detail

Repository
rP 0 A.D. Public Repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

wraitii created this revision.Jan 26 2021, 11:22 PM
wraitii edited the summary of this revision. (Show Details)Jan 26 2021, 11:25 PM
wraitii edited the summary of this revision. (Show Details)Jan 26 2021, 11:28 PM

Build is green

builderr-debug-macos.txt
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ranlib: file: ../../../binaries/system/libsimulation2_dbg.a(precompiled.o) has no symbols
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ranlib: file: ../../../binaries/system/libgraphics_dbg.a(precompiled.o) has no symbols
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ranlib: file: ../../../binaries/system/libatlas_dbg.a(precompiled.o) has no symbols
ld: warning: text-based stub file /System/Library/Frameworks//CoreAudio.framework/CoreAudio.tbd and library file /System/Library/Frameworks//CoreAudio.framework/CoreAudio are out of sync. Falling back to library file for linking.
ld: warning: text-based stub file /System/Library/Frameworks//AudioToolbox.framework/AudioToolbox.tbd and library file /System/Library/Frameworks//AudioToolbox.framework/AudioToolbox are out of sync. Falling back to library

See https://jenkins.wildfiregames.com/job/macos-differential/3074/display/redirect for more details.

Build is green

builderr-release-gcc7.txt
In file included from ../../../source/pch/atlas/precompiled.h:26:
../../../source/tools/atlas/GameInterface/Messages.h: In function 'void AtlasMessage::fGetTerrainGroupPreviews(AtlasMessage::qGetTerrainGroupPreviews*)':
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref' not supported by dump_expr#<expression error>' may be used uninitialized in this function [-Wmaybe-uninitialized]
 struct sTerrainTexturePreview
        ^~~~~~~~~~~~~~~~~~~~~~
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref' not supported by dump_expr#<expression error>' may be used uninitialized in this function [-Wmaybe-uninitialized]
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref' not supported by dump_expr#<expression error>' may be used uninitialized in this function [-Wmaybe-uninitialized]
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref

See https://jenkins.wildfiregames.com/job/docker-differential/4732/display/redirect for more details.

wraitii requested review of this revision.Jan 27 2021, 12:00 AM

Here is the problem, as I already detailed in D1987 which introduced the "predict position 2x in advance" but only partially.
Bit of a wall of text, I invite you to copy this into a multi-column environment.
Assuming A and B chase each other in a straight line, with B moving at speed 8 and A at speed 10. The range of A is 4, and I explore the A<B and B<A ID cases (i.e. who moves first).
A starts at x, B starts at x+8. Both are static at the start, so A initially moves to x+8

If A compute paths to B's position at the moment of moving, here's what happens:

B<A:
B moves to x+16
A checks if in range - ∆ 16
A moves to x+8
A computes path to x+16

B moves to x+24
A checks if in range - ∆ 16
A moves to x+16
A computes path to x+24
[repeats forever]

B>A:
A checks if in range - ∆ 8
A moves to x+8
A computes path to x+8 <- problem.
B moves to x+16

A checks if in range - ∆ 8
A moves to x+8
A computes path to x+16 <- also problem.
B moves to x+24


A checks if in range - ∆ 16
A moves to x+16
A computes path to x+24
B moves to x+32
[repeats forever]

The problem here is that the other unit will move by the time A checks ranges again, and so A is never in range.
If we now account for this turn of movement, here's what happens:

B<A:
B moves to x+16
A checks if in range - ∆ 16
A moves to x+8
A computes path to x+24

B moves to x+24
A checks if in range - ∆ 16
A moves to x+18 (<- here its greater speed lets it close in)
A computes path to x+32

B moves to x+32
A checks if in range - ∆ 14
A moves to x+28
A computes path to x+40

B moves to x+40
A checks if in range - ∆ 12
A moves to x+38
A computes path to x+48

B moves to x+48
A checks if in range - ∆ 10
A moves to x+48
A computes path to x+56

B moves to x+56
A checks if in range - ∆ 8
A moves to x+56 <- here we're back to an infinite loop situation - A never actually gets closer than a turn delta.
A computes path to x+64
[repeats forever]

B>A:
A checks if in range - ∆ 16
A moves to x+8
A computes path to x+16
B moves to x+16

A checks if in range - ∆ 8
A moves to x+16
A computes path to x+24
B moves to x+24
[repeats forever]

As you can see, this also doesn't work. D1987 thus predict 2x the movement speed, which goes like this:

B<A:
B moves to x+16
A checks if in range - ∆ 16
A moves to x+8
A computes path to x+32

[same as above for a few turns]

B moves to x+48
A checks if in range - ∆ 10
A moves to x+48
A computes path to x+64

B moves to x+56
A checks if in range - ∆ 8
A moves to x+58 <- here problem: the chaser collides with the target. This makes it actually stay at 48, and it infinite loops.
A computes path to x+64
[repeats forever]

B>A:
A checks if in range - ∆ 16
A moves to x+8
A computes path to x+24
B moves to x+16

A checks if in range - ∆ 8
A moves to x+18
A computes path to x+32
B moves to x+24

A checks if in range - ∆ 6
A moves to x+28
A computes path to x+40
B moves to x+32

A checks if in range - ∆ 4 <- HIT!
A moves to x+38 <- would collide, but it's OK because we've already hit. This is the muskox issue -> here the speed delta is so large that gradual change can't happen and we overshoot.
[repeats forever]

This somewhat works. If ID(A) < ID(B), the unit collides and doesn't get in range (thus this patch). However, if ID(A) > ID(B), there is some room, depending on B's speed.
Now what I failed to realise in D1987 is the impact of entity ID and collision course. However, as I noted here: https://code.wildfiregames.com/D1987#82700, we could check range before moving (D3230). Here are the same scenarios with that change (you'll notice that it doesn't change the case where ID(A) < ID(B) at all, so those bug out just the same. I haven't repeated them.

If A compute paths to B's position at the moment of moving, here's what happens:

B<A:
A checks if in range - ∆ 8
B moves to x+16
A moves to x+8
A computes path to x+16

A checks if in range - ∆ 8
B moves to x+24
A moves to x+16
A computes path to x+24
[repeats forever]

This still doesn't work - we still have a one-turn lag that we do need to account for.
If we now account for this turn of movement, here's what happens:

B<A:
A checks if in range - ∆ 8
B moves to x+16
A moves to x+8
A computes path to x+24

A checks if in range - ∆ 8
B moves to x+24
A moves to x+18 (<- here its greater speed lets it close in)
A computes path to x+32

A checks if in range - ∆ 6
B moves to x+32
A moves to x+28
A computes path to x+40

A checks if in range - ∆ 4 <- HIT
B moves to x+40
A moves to x+38 <- you'll notice the lack of a collision here, because B moved first.
A computes path to x+48
[repeats forever]

This works somewhat. Essentially, it makes the ID cases symmetrical -> here we also have an issue with chasing slow targets, because B might not move out of the way enough.

Now, muddying all this - there is a "tryMovingStraightToTarget" function that at the beginning of a turn moves synchronously. This is also not symmetrical, but it avoids the asynchronous pathing delay. What happens is actually this:

B<A:
B moves to x+16
A checks if in range - ∆ 16
A moves directly to x+10 (predicting B=24 - one turn delta)
A computes path to x+24

B moves to x+24
A checks if in range - ∆ 14
A moves directly to x+20 (predicting B=32 - one turn delta)
A computes path to x+32

B moves to x+32
A checks if in range - ∆ 12
A moves directly to x+30 (predicting B=40 - one turn delta)
A computes path to x+40

B moves to x+40
A checks if in range - ∆ 10
A moves directly to x+40 (predicting B=48 - one turn delta)
A computes path to x+48

B moves to x+48
A checks if in range - ∆ 8
A moves directly to x+50 (predicting B=56 - one turn delta) <- Collision.

[repeats forever]

With checking first & not turn delta (not needed)
A checks if in range - ∆ 8
B moves to x+16
A moves directly to x+10 (sees B at x+16)
A computes path to x+16 <- don't really care

A checks if in range - ∆ 6
B moves to x+24
A moves directly to x+20 (sees B at x+24)
A computes path to x+24

A checks if in range - ∆ 4 <- HIT
B moves to x+32
A moves directly to x+30 (sees B at x+32) <- note no collision because of entity ID stuff.
A computes path to x+32


[repeats forever]
Inverting A and B

A checks if in range - ∆ 8
A moves directly to x+10 (predicting B=16 - one turn delta)
A computes path to x+16
B moves to x+16

A checks if in range - ∆ 6
A moves directly to x+20 (predicting B=24 - one turn delta <- this is where we're fixing the synchronicity issue)
A computes path to x+24 <- don't care
B moves to x+24

A checks if in range - ∆ 4 <- HIT
A moves directly to x+30 (predicting B=32 - one turn delta) <- Collision but it's OK, we've hit already.

You'll note that this still doesn't work in some cases, but with direct movement and optional One turn delta prediction, it works, assuming we don't run into collisions before hitting the target.


There is one final piece to this puzzle, and it's that path results are sent at the beginning of a turn, but if the entity thinks its path would not lead it to the target, it actives the 'following known imperfect path' routine and then it doesn't try recomputing paths every turn.
The problem is that by predicting 2* turns in advance, the paths are actually ahead of the target. This activates the hack, which makes the chasing fail, because entities can sometimes just not get in range of the direct pathing logic (which remember is necessary to chase).
The only way to have correct paths is to predict where the entity will be at the next turn's start, which is either its current position if ID(A) > ID(B) or position + expected movement.


Therefore -> D3230 removes the prediction * 2 hack. Assuming that the "straight to target" logic can take over - it does from ∆ 24, which should be enough with the current entity speeds, then it's not needed for chasing to hit. It also fixes the issue with the pathing predictions.
The only remaining problem is the collision issue. This is where this patch comes in -> it removes collisions with the target, letting entities get in range.

wraitii updated this revision to Diff 15716.Jan 27 2021, 2:13 PM

Improve on the fleeing hack.

Before / After:


As you can see, this patch fixes all cases of fleeing not fixed by D3230, but it introduces (as expected) 'phasing' through units when chasing sometimes, which makes it:

  • very easy to chase as the target is stopped
  • look weird.
wraitii updated this revision to Diff 15728.Jan 27 2021, 4:52 PM

Out of a healthy sense of paranoia, only discard collision with the target if it's a moving obstruction. Should avoid any weirdness, though I wasn't able to trigger any anyways.

Committing once green on CI.

Build is green

builderr-release-gcc7.txt
In file included from ../../../source/pch/atlas/precompiled.h:26:
../../../source/tools/atlas/GameInterface/Messages.h: In function 'void AtlasMessage::fGetTerrainGroupPreviews(AtlasMessage::qGetTerrainGroupPreviews*)':
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref' not supported by dump_expr#<expression error>' may be used uninitialized in this function [-Wmaybe-uninitialized]
 struct sTerrainTexturePreview
        ^~~~~~~~~~~~~~~~~~~~~~
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref' not supported by dump_expr#<expression error>' may be used uninitialized in this function [-Wmaybe-uninitialized]
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref' not supported by dump_expr#<expression error>' may be used uninitialized in this function [-Wmaybe-uninitialized]
../../../source/tools/atlas/GameInterface/Messages.h:315:8: warning: '#'target_mem_ref

See https://jenkins.wildfiregames.com/job/docker-differential/4744/display/redirect for more details.

Build is green

builderr-debug-macos.txt
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ranlib: file: ../../../binaries/system/libsimulation2_dbg.a(precompiled.o) has no symbols
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ranlib: file: ../../../binaries/system/libgraphics_dbg.a(precompiled.o) has no symbols
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ranlib: file: ../../../binaries/system/libatlas_dbg.a(precompiled.o) has no symbols
ld: warning: text-based stub file /System/Library/Frameworks//CoreAudio.framework/CoreAudio.tbd and library file /System/Library/Frameworks//CoreAudio.framework/CoreAudio are out of sync. Falling back to library file for linking.
ld: warning: text-based stub file /System/Library/Frameworks//AudioToolbox.framework/AudioToolbox.tbd and library file /System/Library/Frameworks//AudioToolbox.framework/AudioToolbox are out of sync. Falling back to library

See https://jenkins.wildfiregames.com/job/macos-differential/3086/display/redirect for more details.

This revision was not accepted when it landed; it landed in state Needs Review.Jan 27 2021, 6:44 PM
This revision was automatically updated to reflect the committed changes.