Opened 11 years ago
Closed 9 years ago
#1756 closed enhancement (fixed)
Long/Tile Pathfinder Rewrite
Reported by: | Kieran P | Owned by: | Itms |
---|---|---|---|
Priority: | Must Have | Milestone: | Alpha 19 |
Component: | Core engine | Keywords: | patch pathfinding |
Cc: | davidshumway@… | Patch: |
Description (last modified by )
For continuing Philip's pathfinder work. For the short-range pathfinder rewrite, see #1942.
See the following posts for progress so far:
- http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=80#entry230053
- http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=100#entry230217
- http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=120#entry233181
- http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=140#entry233213
- http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=160#entry233998
- http://www.wildfiregames.com/forum/index.php?showtopic=15270&st=180#entry234910
Also pathfinder.pdf for some concepts of the new pathfinder design.
Attachments (11)
Change History (33)
by , 11 years ago
Attachment: | pathperf5.patch added |
---|
comment:1 by , 11 years ago
Description: | modified (diff) |
---|
comment:2 by , 11 years ago
I did a crude merge with the latest svn. There were some conflicts which were not dealt with properly but it will now compile and run, though the AI breaks and I got an assertion failure while testing.
by , 11 years ago
Attachment: | pathperf7.patch added |
---|
Another merge (based on quantumstate's patch), using trunk as it was on March 8th.
comment:3 by , 11 years ago
pathperf7_dry1.patch: One function DRY-ied. Otherwise no added value. Not properly tested.
comment:4 by , 11 years ago
Would like to give a go there. Applied patch and started looking, and additions are huge indeed. A good start would be imho to make all pathfinding code goes in its own static libs, allowing using a small 2D test/bench test app, easier and faster for coding/testing than compiling and loading the whole app at each test/bench changes. Or is there already one ? (last post with black and white grid and blue path ?)
(single fast 2D apps are very useful, and could be declined/reused for formation, tactical ai like done here http://www.cgf-ai.com/products.html#tacastarexplorer )
Could a dedicated forum post be made about current state and next steps ?
comment:5 by , 11 years ago
I think Philip (Ykkrosh) would have to be the one to summarize the current state of the pathfinder, but I doubt he will have time to do that. You might have better luck if you drop by IRC and try to catch him there.
What I know is:
- It mostly affects the long-range / tile pathfinder, not the short-range / vertex pathfinder. Both have performance issues, this patch is intended to make the pathfinders consistent.
- It's not intended to improve performance. In fact, the new approach uses a higher resolution map and so optimizations like JPS were required to even make it feasible. More optimizations are of course possible but the basic design should be completed first.
- It's much faster in some cases, like testing if a target is unreachable.
- It's much slower in some cases like terrain modification or placing structures, this needs to be optimized.
pathfinder.pdf may be a good place to learn about the design, it won't necessarily match the latest patch. Other than that, I would ask Philip in IRC, and you might find a bit more info by searching the IRC logs for "pathfinder".
comment:6 by , 11 years ago
Description: | modified (diff) |
---|---|
Summary: | Pathfinder Rewrite (Performance) → Long/Tile Pathfinder Rewrite |
comment:7 by , 11 years ago
Description: | modified (diff) |
---|
comment:8 by , 11 years ago
Keywords: | wip added; unstable removed |
---|
comment:9 by , 11 years ago
Latest version of the patch is currently at http://git.wildfiregames.com/gitweb/?p=0ad.git;a=shortlog;h=refs/heads/projects/philip/pathfinder
by , 10 years ago
Attachment: | Diff.patch added |
---|
follow-up: 13 comment:10 by , 10 years ago
Experiment: could somebody try "patch -p1 -i Diff.patch" to apply the above patch to svn? It should compile cleanly against the latest version.
by , 10 years ago
Attachment: | FixGoalDetection.patch added |
---|
by , 10 years ago
Attachment: | MakeGoalReacheable_improved.patch added |
---|
by , 10 years ago
Attachment: | PathProfile.patch added |
---|
by , 10 years ago
Attachment: | commands.txt added |
---|
comment:12 by , 10 years ago
Keywords: | review added |
---|
comment:13 by , 10 years ago
I made 2 patches from wraitii's pathfinding branch. First one is for fixing long pathfinder's goal detection, second one is for improving performance of hierarchical pathfinder.
The original long JPS pathfinder detects a goal by the target's center nav-cell. If this cell is unreachable but the goal circle/square isn't, it searches whole map. First patch fixed this problem.
Second patch improves CCmpPathfinder_Hier::MakeGoalReachable(), which eats almost 80% time of long pathfinder.
To check my improvements, I added some profiling code in both the original and my patches and I have both codes run with replay mode. The commands.txt is from 1 human vs. 1 AI player's match. The result is:
Original, r15724 tc_ProcessShortRequests: 16.5748 Gc (7827x) tc_ProcessLongRequests: 39.688 Gc (11588x) tc_MakeGoalReachable: 31.5947 Gc (55211x) tc_NavcellContainsGoal: 11.0595 Gc (209755470x) Patched tc_ProcessShortRequests: 25.4634 Gc (8334x) tc_ProcessLongRequests: 29.0432 Gc (11593x) tc_MakeGoalReachable: 17.8753 Gc (60880x) tc_NavcellContainsGoal: 12.8727 Gc (221986854x)
I can't say total time is neither improved nor worsened. Long pathfinder's gain is almost canceled by short pathfinder's loss. Mysterious trade-off between long and short pathfinder is interesting but far beyond this report.
MakeGoalReachable() is called from ProcessLongRequests(), and NavcellContainsGoal() is called from both MakeGoalReachable() and ProcessLongRequests(). MakeGoalReachable() runs 70% or more faster while NavcellContainsGoal() runs slightly slower, about 10%.
comment:14 by , 10 years ago
Milestone: | Backlog → Alpha 18 |
---|
by , 10 years ago
Attachment: | MakeGoalReacheable_improved_v2.patch added |
---|
comment:15 by , 10 years ago
I revised my previous patch for hierarchical pathfinder. This patch makes MakeGoalReachable() much faster. I patched all of my accomplishments(PathProfile.patch, FixGoalDetection.patch and this patch) and I measured the performance by the same way to my previous post.
tc_ProcessShortRequests: 26.2598 Gc (8334x) tc_ProcessLongRequests: 14.4048 Gc (11593x) tc_MakeGoalReachable: 3570.41 Mc (60880x) tc_NavcellContainsGoal: 4350.96 Mc (66922908x)
Now MakeGoalReachable() runs 9 times faster than original, significantly contributes overall pathfinder's performance.
follow-up: 17 comment:16 by , 10 years ago
Hello kanetaka. Just to keep you updated, wraitii is busy these weeks (he may be back around November).
You should probably propose a pull request on his branch, that way he'd be able to review the patches really easily (also he'd be notified appropriately, instead of having to read Trac tickets ;-) ).
I'm leaving your patches here in the review queue, but I'm not sure anyone here, except wraitii, knows the branch well enough to review them appropriately.
Thanks anyways for your work on this, this is a hot issue :-)
comment:17 by , 10 years ago
Replying to Itms:
You should probably propose a pull request on his branch, that way he'd be able to review the patches really easily (also he'd be notified appropriately, instead of having to read Trac tickets ;-) ).
Thank you for your advise. I had wondered if I post patches here, now I've got the right place.
comment:18 by , 9 years ago
Cc: | added |
---|
comment:19 by , 9 years ago
Keywords: | wip review removed |
---|
I'm currently working on integrating kanetaka's patches to the pathfinding branch, so I'm taking this ticket out of the review queue, and I'll close it as fixed when the branch is merged on SVN.
comment:20 by , 9 years ago
Keywords: | pathfinding added |
---|
comment:21 by , 9 years ago
Milestone: | Alpha 18 → Alpha 19 |
---|
From Philip (2012-12-11)