Page MenuHomeWildfire Games

Fix pathfinding issue with units not garrison wallturrets due to a UnitMotion ObstructionFilter inconsistency
ClosedPublic

Authored by wraitii on Mar 31 2018, 3:50 PM.

Details

Summary

If a unit is ordered to garrison a wall turret that is not accessible from the inside as it is blocked by the adjacent walls,
the unit will forever walk against the wall, never succeed the garrison nor show up as idle.
It was reported here #4473. It is a very annoying and easy to trigger pathfinder bug.

It can be traced to rP17154 which fixed #3539 but introduced an inconsistency in CCmpUnitMotion::TryGoingStraightToTargetEntity.
This function is the only one not ignoring the target obstruction, while all other calls do account for the target obstructions.
Removing this inconsistency fixes the issue.
The obstruction filter ignores all obstruction shapes that have one of the two controlGroups equal to the target entity.
The wall pieces adjacent to the target wall tower have the same control group, hence are ignored in this one line of code.

It seems the inconsistency comes from a confusion of nearestPointOfGoal:
It doesn't return the nearest point on the obstruction but the point in the garrisonrange.

In rP17154:
Yes, but it put as next waypoint goalPos which the the nearestPointOnGoal which for a wall should be the nearest point on the obstruction square. And there should be no obstruction between the unit and this goalPos.
In https://trac.wildfiregames.com/ticket/3539#comment:4:
tryGoingStraightToTarget which will never suceed as it will always find the way obstructed by the target itself.

Test Plan

Start the "new rms test" map on a normal mapsize with iberians selected and try to garrison a turret that is likely to be inaccessible from the inside.
Add debug_printfs to show when the function succeeds.

The question remains whether formations should also take the target into account.
If not, we could precise the function comment.

Diff Detail

Repository
rP 0 A.D. Public Repository
Branch
/ps/trunk
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 5722
Build 9610: Vulcan Build
Build 9609: arc lint + arc unit

Event Timeline

elexis created this revision.Mar 31 2018, 3:50 PM

Seems to work. (In general there's problems with units getting stuck on things.)

But not always very well.

In D1424#58285, @temple wrote:

But not always very well.

I have noticed the detours too. I believe I had seen them without the patch too. I couldn't reproduce them reliably yet.
I believe mimo has described the same detours that had resulted in the reverted commit in that ticket #3539: rP17184.

the path used by the female was from time to time quite weird, making some unexpected detours

For some reason the long path goal in these two screenshots was inside a wall, and the unit ended up doing the gate dance forever. (D443 might help in this case.)



temple added a comment.Apr 1 2018, 1:05 AM
		// add our final goal as a long range waypoint so we don't forget
		// where we are going if the short-range pathfinder returns
		// an aborted path.
		m_LongPath.m_Waypoints.clear();
		CFixedVector2D target = m_FinalGoal.NearestPointOnGoal(from);
		m_LongPath.m_Waypoints.emplace_back(Waypoint{ target.X, target.Y });

So it's putting the nearest point as a long waypoint, even though that's in the middle of a wall.

elexis added a comment.Apr 1 2018, 4:45 AM

But the shape of m_FinalGoal is set immediately, so that should also be the nearest point in the target range, not the center - unless from is already the center I guess. I'll check.

temple added a comment.Apr 1 2018, 5:21 AM
In D1424#58302, @elexis wrote:

But the shape of m_FinalGoal is set immediately, so that should also be the nearest point in the target range, not the center - unless from is already the center I guess. I'll check.

If you look at the screenshot, it's not the center, it appears to be on the goal -- 2m away from the turret on a corner. But since that's inside the wall it causes some problems.

The unit can garrison on the inside if you bring him close enough to the corner, so I'm wondering why the short pathfinder would make him go outside. Maybe it's the short/long pathfinder incompatibility? But seems strange if we also have 2m to work with, seems like there's enough space there.

temple added a comment.Apr 1 2018, 5:43 AM

Seems like a problem with the short pathfinder. (And maybe we don't have 2m to work with.) I'll investigate more tomorrow.


temple added a comment.Apr 1 2018, 7:38 PM

I think the point is that there's no vertex on the closer side of the turret, so maybe we could split edges when they intersect with the goal area? I don't know how complicated the math would be.

elexis added a comment.Apr 2 2018, 1:38 PM
  • The two replays show two different problems right? Because the first one has a goal inside the wall obstruction, the second one has a goal just outside of the wall obstruction but inside the teal edges.
  • It wasn't obvious what is seen on the screenshots. The (0, 0, 255) blue is the obstruction and teal (0, 255, 255) are edges rendered in CCmpPathfinder::ComputeShortPath. I'm not familiar with the internals of the vertex pathfinder yet.
  • When applying D443, the uploaded replays works as intended.
  • The primary question is if the observed issue can be triggered without this patch or not (i.e. if this patch doesn't add a regression to players and is correct, we can commit it nonetheless and write a ticket)
  • A recipe that reproduces the described issues reliably would likely decide this question.
temple added a comment.Apr 2 2018, 9:07 PM
In D1424#58331, @elexis wrote:
  • The two replays show two different problems right? Because the first one has a goal inside the wall obstruction, the second one has a goal just outside of the wall obstruction but inside the teal edges.

I think the problem is the short pathfinder uses the nearest point on the goal (the red square), but to get there you have to cross an obstruction edge (teal line) which isn't okay. There's other points on the goal that we can reach, but they're never the nearest point (given the unit's position). My idea was to split the edges when they intersect the goal, so then instead they could consider a vertex that intersects the goal, which will be okay. (The long path waypoint is kind of a red herring. It's the nearest point on the goal from the starting position, but the short pathfinder does use the goal not that point.)

  • It wasn't obvious what is seen on the screenshots. The (0, 0, 255) blue is the obstruction and teal (0, 255, 255) are edges rendered in CCmpPathfinder::ComputeShortPath. I'm not familiar with the internals of the vertex pathfinder yet.
  • When applying D443, the uploaded replays works as intended.

Not really, actually. I think the short pathfinder fails so then it uses the long pathfinder. That puts a box around the short pathfinder search space so it can't come up with paths that go outside the space (because those paths could have problems outside the space, like additional sections of wall). The same problem exists though.

  • The primary question is if the observed issue can be triggered without this patch or not (i.e. if this patch doesn't add a regression to players and is correct, we can commit it nonetheless and write a ticket)
  • A recipe that reproduces the described issues reliably would likely decide this question.

You have to be close enough to trigger the short pathfinder and you want the nearest point on the goal to be hidden behind an obstruction. The vertex pathfinder looks at vertices, so if all the relevant vertices are hidden behind edges and can't be reached, then it won't find a path. My guess is overlapping obstructions weren't considered when designing the vertex pathfinder.

temple added a comment.Apr 2 2018, 9:11 PM
In D1424#58331, @elexis wrote:
  • The primary question is if the observed issue can be triggered without this patch or not (i.e. if this patch doesn't add a regression to players and is correct, we can commit it nonetheless and write a ticket)

The issue is independent of the patch, but the patch highlights it. I'd say the question is which is worse, units sometimes getting stuck on walls, or units going outside the wall to garrison in a turret that they should be able to reach from the inside? If the second is worse then maybe we should wait until we have a fix for that too.

temple added a comment.Apr 9 2018, 3:43 AM

I think this is correct, but the vertex pathfinder is wrong, and I think the new problems are worse than the old ones. So I think we should wait on committing this until we have a fix for the vertex pathfinder when there's overlapping obstructions or goals overlapping obstructions.

temple accepted this revision.Apr 13 2018, 7:36 PM

On the other hand, this will give players something new to complain about (if they notice it).

This revision is now accepted and ready to land.Apr 13 2018, 7:36 PM
wraitii added a subscriber: wraitii.May 3 2018, 8:40 AM
In D1424#58372, @temple wrote:

I think the problem is the short pathfinder uses the nearest point on the goal (the red square), but to get there you have to cross an obstruction edge (teal line) which isn't okay. There's other points on the goal that we can reach, but they're never the nearest point (given the unit's position). My idea was to split the edges when they intersect the goal, so then instead they could consider a vertex that intersects the goal, which will be okay. (The long path waypoint is kind of a red herring. It's the nearest point on the goal from the starting position, but the short pathfinder does use the goal not that point.)

I think I've improved that in the unit motion rewrite by having the short-range pathfinder use the long-range pathfinder's target as the goal (with some reversion from that when close enough to the goal). That might be enough to make the issue mostly go away, since the long-range pathfinder's target should always be a valid one, and unless you run into units the short-range pathfinder may not trigger (though iirc I do trigger it when getting close enough as otherwise units wouldn't be able to correctly gather around trees, so maybe not.)

Not really, actually. I think the short pathfinder fails so then it uses the long pathfinder. That puts a box around the short pathfinder search space so it can't come up with paths that go outside the space (because those paths could have problems outside the space, like additional sections of wall). The same problem exists though.

That's definitely correct. I believe SVN has this behaviour where the boxed search space increases in size, up to a point, but if it gets too big it's just far too slow.

The correct fix is probably to intersect edges with the goal like you suggest, which sounds rather easy to do algorithmically, but might slow the vertex pathfinder even further to almost unacceptable levels.

@wraitii you are currently working on many patches with the involved components, and some of your patches sound like they could be relevant to this patch. temple had discovered some bug above, perhaps you have a fix for that already (given the amount of current diffs and the fact that they claim to fix edge cases of stuck units relating to obstructions), and perhaps the converse is true and this diff fixes one of the edge cases that you run into in other places. Maybe not, pathfinder rabbithole is deep.

In D1424#78429, @elexis wrote:

@wraitii you are currently working on many patches with the involved components, and some of your patches sound like they could be relevant to this patch. temple had discovered some bug above, perhaps you have a fix for that already (given the amount of current diffs and the fact that they claim to fix edge cases of stuck units relating to obstructions), and perhaps the converse is true and this diff fixes one of the edge cases that you run into in other places. Maybe not, pathfinder rabbithole is deep.

Indeed this patch is on my mind... I think D1869 has a proper fix to the problem temple described:

I think the problem is the short pathfinder uses the nearest point on the goal (the red square), but to get there you have to cross an obstruction edge (teal line) which isn't okay. There's other points on the goal that we can reach, but they're never the nearest point (given the unit's position). My idea was to split the edges when they intersect the goal, so then instead they could consider a vertex that intersects the goal, which will be okay. (The long path waypoint is kind of a red herring. It's the nearest point on the goal from the starting position, but the short pathfinder does use the goal not that point.)

Because it actually handles that case.

I wish I could be useufl, but I would cross the event horizon then, from https://en.wikipedia.org/wiki/Black_hole:

The boundary of the region from which no escape is possible is called the event horizon.

So, some status report on this, along with two extreme reproduction cases.
In the first replay, the unit doesn't try going straight as all wall pieces don't have the obstruction group of the wall turret - so TryGoingStraightToTarget doesn't ignore the walls even if it ignores the target.
In this case, the issue is strictly that the entity is always trying a short path because the distance between it and the target is below the threshold, and that never succeeds as the max-range for a short-range pathfinding call is smaller than the walls's extent.
A simple fix would be to try a long path if we have failed enough computations.

There is also a second replay for the case where we try going straight. For that, I would switch to skipping the specific target tag, which would make it work in all cases.

wraitii commandeered this revision.Jul 13 2019, 10:18 PM
wraitii updated this revision to Diff 8868.
wraitii added a reviewer: elexis.

Do the above, both replays are fixed in safe manner and keeping the optimisation of going straight.

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/58/display/redirect

wraitii requested review of this revision.Jul 14 2019, 1:10 PM
elexis commandeered this revision.Jul 14 2019, 1:21 PM
elexis edited reviewers, added: wraitii; removed: elexis.

(I wrote that)

wraitii commandeered this revision.Jul 22 2019, 6:47 PM
wraitii edited reviewers, added: elexis; removed: wraitii.

Recommandeering to update the diff, OK to credit you @elexis as 'Reported By + Based on a patch by'?

wraitii updated this revision to Diff 9064.Jul 22 2019, 6:47 PM

Reupload hopefully passing build.

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/194/display/redirect

wraitii updated this revision to Diff 9068.Jul 22 2019, 8:18 PM

Good Ol' Jenkins crashed on us.

Successful build - Chance fights ever on the side of the prudent.

Link to build: https://jenkins.wildfiregames.com/job/docker-differential/197/display/redirect

This revision was not accepted when it landed; it landed in state Needs Review.Jul 23 2019, 8:18 AM
This revision was automatically updated to reflect the committed changes.