Page MenuHomeWildfire Games

D13 prerequisite 8: Upgrade the hierarchical pathfinder
AbandonedPublic

Authored by wraitii on Jan 8 2017, 6:25 PM.

Details

Reviewers
Itms
temple
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Summary

This diff exposes convenience functions through the pathfinder to find reachable navcells from given positions. This is used in D13 to synchronise short and long-range pathfinder, and in the future might have other uses.

This diff also drastically optimises the MakeGoalReachable function, by using global regions to determine connectivity faster for non-point goals, and generally being less naive.

Global regions, being an additional feature, thus slower, required some further optimisations that were not implemented before. Overall, previous testing as shown this patch as being generally faster than svn (see graphs in the comments).

I can't guarantee it returns exactly the same paths as SVN, but they should be close.

Test Plan

Test in-game, report on reachability and/or any weirdness, review code. In principle this alone should have minimal-to-no influence on unit pathing.

Diff Detail

Repository
rP 0 A.D. Public Repository
Branch
D53_hierarchical_upgrade
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 6749
Build 11101: Vulcan BuildJenkins
Build 11100: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
In D53#42839, @wraitii wrote:

Well then the JPS pathfinder cannot lead us, even with makeGoalReachable, to an impassable area. We can pick a target that's impassable to the vertex pathfinder, but the collision detection in UnitMotion will stop us. I don't see the problem then?

Picking a target that's impassable to the vertex pathfinder is a bad thing, that's my point. If you think it's not a bad thing, well, we'll have that discussion at the appropriate time.

In D53#42854, @temple wrote:

Picking a target that's impassable to the vertex pathfinder is a bad thing, that's my point.

Ah, right, OK. Yes I don't think that's a huge issue, and indeed for another time.

@temple Could you review this patch?

temple requested changes to this revision.Jan 21 2018, 5:33 PM
In D53#50238, @wraitii wrote:

@temple Could you review this patch?

Were you going to update the diff?

This revision now requires changes to proceed.Jan 21 2018, 5:33 PM

Not regarding the line below (unless you go deeper in the argument)

Picking a target that's impassable to the vertex pathfinder is a bad thing, that's my point. If you think it's not a bad thing, well, we'll have that discussion at the appropriate time.

Regarding https://code.wildfiregames.com/D53#42685 I could, but my understanding was that you might have more comments from a more complete pre-review that might lead to fewer back-and-forth in the future.

In D53#50281, @wraitii wrote:

Regarding https://code.wildfiregames.com/D53#42685 I could, but my understanding was that you might have more comments from a more complete pre-review that might lead to fewer back-and-forth in the future.

When you said the following, it sounded like you were ready to commit the patch, when I felt like we'd only finally agreed on the main ideas!

Re-formations: this is all unrelated to this patch so I'll make a few last adjustments and commit this.

I hope you wait for a review before committing!

Basically, I thought we still had a long ways to go. A lot of my older comments were either not addressed or I didn't follow up on them because they were small details and I wanted to focus on the big picture. It's been a couple of months so I don't remember the details (but for example, I don't think I ever got tests to work). Anyway, I prefer a lot of back-and-forth.

elexis added inline comments.Jan 21 2018, 7:19 PM
source/simulation2/components/tests/test_Pathfinder.h
567

:s

Ok, well then I'd appreciate if you could summarise/repeat at least some of these comments because to be honest I'm kind of unsure what exactly you wanted changed at this point.

Re-tests, I'm going to delete those as they were useful during the debugging process but not as actual tests. Might add some more performant one but I'm somewhat convinced that efficient pathfinder-related testing must be done in integration/map tests.

In D53#50400, @wraitii wrote:

Ok, well then I'd appreciate if you could summarise/repeat at least some of these comments because to be honest I'm kind of unsure what exactly you wanted changed at this point.

You already know of some things to change, so why not start there? Update the diff to something you think is committable and update the summary, then I'll take a look.

wraitii planned changes to this revision.Jan 23 2018, 9:37 AM

Fair enough.

wraitii updated this revision to Diff 6513.May 5 2018, 9:34 PM
wraitii marked 21 inline comments as done.

I believe this addresses all inline comments by @temple, and should the weird stats thing in the tests (I needed to actually InitGame).

source/simulation2/components/tests/test_Pathfinder.h
567

Deleted this horrible test hack.

source/simulation2/helpers/Geometry.h
48 ↗(On Diff #238)

Done for real this time.

source/simulation2/helpers/HierarchicalPathfinder.cpp
122–123

I think I may have just misunderstood what this code was doing... I've changed it to what you suggest and also reset m_RegionsID explicitly when this is called.

251–252

This is referring to L203 (phabricator messed up).

As said above, I'm indeed only breaking out of the inner loop, so the monotony applies unless I've done something stupid.

491–495

Yes, it's just annoying from an intellectual perspective.

863

(irrelevant since A* was removed)

880

(irrelevant since A* was removed)

905

Irrelevant now.

Vulcan added a comment.May 5 2018, 9:46 PM

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

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

You could update the summary. I'll take a look at some point, maybe not soon. (I've been playing SC2 lately.)

some comments

source/simulation2/helpers/HierarchicalPathfinder.cpp
251–252

But dist2Best is for all rows. So it'll find the best the best value in the first row but after that it could quit early with i=0 because that value of dist2 is too large even those some bigger i could produce a dist2 < dist2Best.

source/simulation2/helpers/HierarchicalPathfinder.h
30

.

38–44

B

41

.

43

.

107–122

no A*

183–189

A lot of this stuff is unneeded now.

wraitii updated this revision to Diff 6525.May 12 2018, 7:58 AM
wraitii marked 2 inline comments as done.
wraitii edited the summary of this revision. (Show Details)

Fix the issues you noted above. I've removed the boost libraries entirely, making this if anything neater to review on phabricator :p

Summary is updated.

wraitii added inline comments.May 12 2018, 8:01 AM
source/simulation2/helpers/HierarchicalPathfinder.cpp
251–252

Ah, I finally get what you mean. You're right, thanks for noticing this. I forgot to account for blocked navcells (otherwise we would also have row-wise monotony, but then the problem is trivial anyways)

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

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

smiley added a subscriber: smiley.May 12 2018, 9:33 AM
wraitii updated this revision to Diff 6526.May 12 2018, 12:21 PM

CreatePointGoalAt was buggy.

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

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

wraitii updated this revision to Diff 6528.May 12 2018, 7:03 PM

And my fix was wrong too :p

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

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

wraitii updated this revision to Diff 6532.May 13 2018, 11:04 AM

Final touchup to createPointGoalAt and fix my new tests.

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

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

wraitii updated this revision to Diff 6538.May 13 2018, 5:58 PM

Const-correct for fun and profit.

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

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

Some new profiling of MakeGoalReachable, on the following replay (which is just moving a pack of units around on Seleucid Sandbox).
Behaviour was virtually identical between svn and D53's result, not exactly the same as expected but sensibly the same result.

As you can see on the below screenshot, the new MakeGoalReachable is much much faster for reachable points, much faster for reachable entities (note that the Y axis is log, so the difference is more than twice), and about as slow for non-reachable points.

wraitii added a comment.EditedMay 14 2018, 8:52 PM

And here's some approximate profiling of HierarchicalPathfinder::Update. We might expect that to be slower because of global regions, but it's actually also faster, 1.5 to 2 times faster (the relationship isn't entirely linear).

This is a weirder graph, it's basically sorting turns by their time spent in HierarchicalPathfinder::Update, so you're pretty much seeing a distribution frequency. As you can see, the red (D53) is much lower than green, in fact the slowest turns of D53 are almost as fast as the fastest turns of svn !

(NB: this profiling was done in the first 10 minutes of an AI game so it's not entirely comparable, but both His just built stuff and since D53 wins on every count, I think it's fair to say that the conclusion holds even if what was happening in the game isn't exactly similar).

wraitii marked 11 inline comments as done.May 16 2018, 7:47 AM

This is RC review-wise. I've tested it a number of times and it returns very similar paths to SVN, as said above it's faster, and I have a number of other revisions that conflict with this so the sooner the better.

source/simulation2/helpers/HierarchicalPathfinder.cpp
229

Need to figure out if I'm still using this.

868

This bit might be removed with D1074. It's doing a little useless work, making the unreachable case perhaps slightly slower than svn (see profiling above)

wraitii updated this revision to Diff 7146.Dec 30 2018, 4:46 PM

Rebased for the hell of it (clean apply).

I'd really like to commit this ASAP, but I'd rather get at least a cursory technical review.

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

Link to build: https://jenkins.wildfiregames.com/job/differential/856/

Stan added a comment.Dec 31 2018, 11:22 AM

@vladislavbelov @temple @Itms can you allocate some time ?

wraitii marked 2 inline comments as done.Jan 5 2019, 5:51 PM
wraitii added inline comments.
source/simulation2/helpers/HierarchicalPathfinder.h
118

This comment isn't accurate, I need to change it.

153

Changed to a vector to use ranged-for loops.

wraitii updated this revision to Diff 7296.Jan 6 2019, 9:53 PM

Add a (rather long) battery of tests on the hierarchical pathfinder specifically.

Connectivity and reachability are both tested. I'm testing a bit of everything but I wouldn't call it 100% coverage, however it makes sure that the basic stuff is handled properly, which is good.

(I've noticed a regression using those tests which is now fixed).

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

Linter detected issues:
Executing section Source...

source/simulation2/helpers/PathGoal.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/components/CCmpPathfinder_Common.h
|   1| /*·Copyright·(C)·2017·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2017"

source/simulation2/components/CCmpPathfinder.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/helpers/HierarchicalPathfinder.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/components/ICmpPathfinder.h
|   1| /*·Copyright·(C)·2017·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2017"

source/simulation2/components/tests/test_Pathfinder.h
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"

source/simulation2/helpers/LongPathfinder.h
|   1| /*·Copyright·(C)·2017·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2017"

source/simulation2/helpers/HierarchicalPathfinder.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"
Executing section JS...
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/differential/936/

wraitii added inline comments.Apr 19 2019, 10:20 PM
source/simulation2/helpers/HierarchicalPathfinder.cpp
971

This is why it works in D53 when const-correcting (cf D1830)

wraitii abandoned this revision.Apr 20 2019, 10:22 AM

I abandon this revision as I've split it in several smaller diffs.
See:
D1829
D1830
D1831
D1832
D1833
D1834
D1835
D1836