Page MenuHomeWildfire Games

Hierarchical pathfinder: speed up edge update (D53 outtake)

Authored by wraitii on Apr 20 2019, 9:50 AM.


Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
rP22279: Hierarchical pathfinder: Speed up edge update

Speed up edge update by being clever, only updating dirty tiles instead of everything (effectively doing to "TODO be clever" here).

(D53 outtake)

Test Plan

Review code, test behaviour.

Diff Detail

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

Event Timeline

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

Link to build:

Stan added a subscriber: Stan.Apr 27 2019, 1:44 PM
Stan added inline comments.
73 ↗(On Diff #7779)

Unless the name is very long we shouldn't use auto

502 ↗(On Diff #7779)

Maybe do it here in this differential to reduce the maintenance ?

737 ↗(On Diff #7779)

ternary ?

wraitii updated this revision to Diff 7901.May 4 2019, 3:03 PM
wraitii marked 3 inline comments as done.
wraitii edited the summary of this revision. (Show Details)

Splicing further. This is solely the edge update.

I've replayed an AI 4v4 for 5 minutes on a giant map, here's the data:

Basically, on that giant map, updating edges took a minimum of 29ms, about 40ms on average, and a max of 70. Now it takes 8ms in the best case, and 25ms in the worst, with about 11 on average.

Basically this is an important speed-up.

This doesn't change hashes, passes tests, so I intend to commit it soon enough regardless of reviews (though I'm welcoming them).

wraitii retitled this revision from Hierarchical pathfinder: Implement global regions / speed up edge update (D53 outtake) to Hierarchical pathfinder: speed up edge update (D53 outtake).May 4 2019, 3:06 PM
Vulcan added a comment.May 4 2019, 3:10 PM

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

Link to build:

This revision was not accepted when it landed; it landed in state Needs Review.May 13 2019, 7:02 PM
This revision was automatically updated to reflect the committed changes.