Page MenuHomeWildfire Games

Vertex pathfinder - fixes to quadrant optimisation to ensure units don't take detours around obstructions.
ClosedPublic

Authored by wraitii on May 19 2019, 5:08 PM.

Details

Reviewers
None
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Commits
rP22473: Vertex pathfinder - fixes to quadrant optimisation to ensure units don't take…
Trac Tickets
#5476
Summary

So I've been searching for a cause to the issue that units sometimes don't take the obvious best path when using the short pathfinder.

It appears to me to be because there is an issue with out handling of the "quadrant" optimisation.
This introduces two changes:

  • Compute the outward quadrants once and for all instead of setting them dynamically, because there is no reason why we should always arrive from the same quadrant as the first time we see a vertex.
  • don't consider quadrants for the start-vertex, because of the edge expansion (which can put us in illegal quadrants)

These result in better paths for probably very slightly worse performance.

Test Plan

Review code. Compile. Test ingame

Diff Detail

Event Timeline

wraitii created this revision.May 19 2019, 5:08 PM

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

Link to build: https://jenkins.wildfiregames.com/job/differential/1460/display/redirect

Crynux added a subscriber: Crynux.Jun 2 2019, 8:49 PM

Quoting this here as well:

In D1911#80640, @Crynux wrote:

@Crynux Could you look at D1908? I think it fixes the same issue that you are trying to fix here.

@wraitii Yep - did some quick tests. It seems to be an improvement over the existing implementation. However, in some cases it's still possible for units to not find their way round the outer corner.

wraitii updated this revision to Diff 8752.Jul 6 2019, 12:54 PM

Remove the undefined behaviour - pushing made a copy so we must set quadOutward before that

Vulcan added a comment.Jul 6 2019, 1:17 PM

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

Link to build: https://jenkins.wildfiregames.com/job/differential/1924/display/redirect

wraitii updated the Trac tickets for this revision.Jul 6 2019, 1:54 PM

With the above dumb bug fixed, this appears to completely fix the issues noted above and also noted by @Crynux .

wraitii updated this revision to Diff 8861.Jul 13 2019, 6:10 PM
wraitii retitled this revision from Unit Motion - Fix vertex optimisation / re-extend the clearance for unit-unit collision to Vertex pathfinder - fixes to quadrant optimisation to ensure units don't take detours around obstructions..
wraitii edited the summary of this revision. (Show Details)

Don't bump the clearance reduction hack as that might have unexpected consequences and the fix still works.

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

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

wraitii added inline comments.Jul 14 2019, 12:06 PM
source/simulation2/helpers/VertexPathfinder.cpp
739

This is needed so the target point doesn't occasionally get seen a being behind the domain edges.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 14 2019, 12:19 PM
This revision was automatically updated to reflect the committed changes.