Page MenuHomeWildfire Games

Optimise MakeGoalReachable and FindNearestNavcellInRegions (D53 outtake)
ClosedPublic

Authored by wraitii on May 13 2019, 7:14 PM.

Details

Reviewers
None
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Commits
rP22817: Optimise MakeGoalReachable and FindNearestNavcellInRegions (D53 outtake)
Summary

This optimised and cleans up code by using a template and a custom-ordered set.

This also indirectly optimises MakeGoalReachable.

Changes hashes, sadly.

(Last of the D53 series of patches)

Test Plan

Review the logic change, play a game or two.

Event Timeline

wraitii created this revision.May 13 2019, 7:14 PM

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

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

wraitii updated this revision to Diff 9478.Aug 24 2019, 1:16 PM

Rebased, should run.

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

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

wraitii planned changes to this revision.Aug 24 2019, 2:22 PM

This is hilariously broken... Need to have a "InGoal" variant, but I need to find a way to not duplicate this all too much.

wraitii updated this revision to Diff 9484.Aug 24 2019, 7:02 PM
wraitii retitled this revision from Optimise FindNearestNavcellInRegions (D53 outtake) to Optimise MakeGoalReachable and FindNearestNavcellInRegions (D53 outtake).

So yeah, I could actually clean this up better and in a working manner. Thanks to the tests I've added to notice this for me.

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

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

wraitii updated this revision to Diff 9566.Sep 1 2019, 10:17 AM

Had accidentally uploaded the patch to fix the previous broken diff.
This should apply on svn.

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

Link to build: https://jenkins.wildfiregames.com/job/vs2015-differential/26/display/redirect

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

Linter detected issues:
Executing section Source...

source/simulation2/components/tests/test_HierPathfinder.h
|  25| class·TestHierarchicalPathfinder·:·public·CxxTest::TestSuite
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classTestHierarchicalPathfinder:' is invalid C code. Use --std or --language to configure the language.

source/simulation2/helpers/HierarchicalPathfinder.h
|  34| ·*·is·defined·as·a·region.
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.
Executing section JS...
Executing section cli...

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

Add some words on the why.

source/simulation2/helpers/HierarchicalPathfinder.cpp
681

Notice that this computed the best cell for each region, but discarded that data, then recomputes it below.

684

Because now we store more data, we can return in a single, very cheap loop if the goal is reachable.

707

FindPassableRegions inlined (and deleted) since it only was called here, was quite short, and the name was sort of confusing (at first sight, it seems similar to FindReachableRegions, but it's really not).

715

Explanation for why this is an optimisation:
Since the set is already ordered by underestimated distance, we don't have to recompute such distances, this removes a loop.

The actual break logic is similar.

805

We are now using the result of RegionNearestNavcellInGoal, which is a rather expensive operation.

wraitii updated this revision to Diff 9568.Sep 1 2019, 10:39 AM

Slight reordering for better readability in the header.

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

Link to build: https://jenkins.wildfiregames.com/job/vs2015-differential/28/display/redirect

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

Linter detected issues:
Executing section Source...

source/simulation2/components/tests/test_HierPathfinder.h
|  25| class·TestHierarchicalPathfinder·:·public·CxxTest::TestSuite
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'classTestHierarchicalPathfinder:' is invalid C code. Use --std or --language to configure the language.

source/simulation2/helpers/HierarchicalPathfinder.h
|  34| ·*·is·defined·as·a·region.
|    | [MAJOR] CPPCheckBear (syntaxError):
|    | Code 'template<...' is invalid C code. Use --std or --language to configure the language.
Executing section JS...
Executing section cli...

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

This revision was not accepted when it landed; it landed in state Needs Review.Sep 1 2019, 10:59 AM
This revision was automatically updated to reflect the committed changes.