Opened 10 years ago

Closed 7 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 historic_bruno)

Attachments (11)

pathperf5.patch (270.6 KB ) - added by Kieran P 10 years ago.
From Philip (2012-12-11)
perfpath6-quantumstate.diff (264.3 KB ) - added by Jonathan Waller 9 years ago.
Rough merge with svn 13111
pathperf7.patch (269.1 KB ) - added by Badmadblacksad- 9 years ago.
Another merge (based on quantumstate's patch), using trunk as it was on March 8th.
pathperf7_dry1.patch (3.8 KB ) - added by yunta 9 years ago.
Apply after pathperf7.
pathperf8.patch (264.6 KB ) - added by historic_bruno 9 years ago.
Update to r13496 with some fixes
Diff.patch (1.0 MB ) - added by wraitii 8 years ago.
FixGoalDetection.patch (1.6 KB ) - added by kanetaka 8 years ago.
MakeGoalReacheable_improved.patch (2.7 KB ) - added by kanetaka 8 years ago.
PathProfile.patch (5.7 KB ) - added by kanetaka 8 years ago.
commands.txt (94.5 KB ) - added by kanetaka 8 years ago.
MakeGoalReacheable_improved_v2.patch (2.8 KB ) - added by kanetaka 8 years ago.

Change History (33)

by Kieran P, 10 years ago

Attachment: pathperf5.patch added

From Philip (2012-12-11)

comment:1 by Kieran P, 10 years ago

Description: modified (diff)

by Jonathan Waller, 9 years ago

Attachment: perfpath6-quantumstate.diff added

Rough merge with svn 13111

comment:2 by Jonathan Waller, 9 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 Badmadblacksad-, 9 years ago

Attachment: pathperf7.patch added

Another merge (based on quantumstate's patch), using trunk as it was on March 8th.

by yunta, 9 years ago

Attachment: pathperf7_dry1.patch added

Apply after pathperf7.

comment:3 by yunta, 9 years ago

pathperf7_dry1.patch: One function DRY-ied. Otherwise no added value. Not properly tested.

comment:4 by tuan kuranes, 9 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 historic_bruno, 9 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 historic_bruno, 9 years ago

Description: modified (diff)
Summary: Pathfinder Rewrite (Performance)Long/Tile Pathfinder Rewrite

comment:7 by historic_bruno, 9 years ago

Description: modified (diff)

comment:8 by historic_bruno, 9 years ago

Keywords: wip added; unstable removed

by historic_bruno, 9 years ago

Attachment: pathperf8.patch added

Update to r13496 with some fixes

by wraitii, 8 years ago

Attachment: Diff.patch added

comment:10 by wraitii, 8 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.

comment:11 by historic_bruno, 8 years ago

Owner: philip removed

Unassigning due to lack of progress.

by kanetaka, 8 years ago

Attachment: FixGoalDetection.patch added

by kanetaka, 8 years ago

by kanetaka, 8 years ago

Attachment: PathProfile.patch added

by kanetaka, 8 years ago

Attachment: commands.txt added

comment:12 by stanislas69, 8 years ago

Keywords: review added

in reply to:  10 comment:13 by kanetaka, 8 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 Itms, 8 years ago

Milestone: BacklogAlpha 18

by kanetaka, 8 years ago

comment:15 by kanetaka, 8 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.

comment:16 by Itms, 8 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 :-)

in reply to:  16 comment:17 by kanetaka, 8 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 Dave, 8 years ago

Cc: davidshumway@… added

comment:19 by Itms, 8 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 Itms, 7 years ago

Keywords: pathfinding added

comment:21 by Itms, 7 years ago

Milestone: Alpha 18Alpha 19

comment:22 by Itms, 7 years ago

Owner: set to Itms
Resolution: fixed
Status: newclosed

In 16751:

New long-range pathfinder.

Based on Philip's work located at http://git.wildfiregames.com/gitweb/?p=0ad.git;a=shortlog;h=refs/heads/projects/philip/pathfinder
Includes code by wraitii, sanderd17 and kanetaka.

An updated version of docs/pathfinder.pdf describing the changes in detail will be committed ASAP.

Running update-workspaces is needed after this change.

Fixes #1756.
Fixes #930, #1259, #2908, #2960, #3097
Refs #1200, #1914, #1942, #2568, #2132, #2563

Note: See TracTickets for help on using tickets.