Attachments (11)

pathperf5.patch (270.6 KB) - added by Kieran P 7 years ago.
From Philip (2012-12-11)
perfpath6-quantumstate.diff (264.3 KB) - added by Jonathan Waller 6 years ago.
Rough merge with svn 13111
pathperf7.patch (269.1 KB) - added by Badmadblacksad- 6 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 6 years ago.
Apply after pathperf7.
pathperf8.patch (264.6 KB) - added by Ben Brian 6 years ago.
Update to r13496 with some fixes
Diff.patch (1.0 MB) - added by wraitii 5 years ago.
FixGoalDetection.patch (1.6 KB) - added by kanetaka 5 years ago.
MakeGoalReacheable_improved.patch (2.7 KB) - added by kanetaka 5 years ago.
PathProfile.patch (5.7 KB) - added by kanetaka 5 years ago.
commands.txt (94.5 KB) - added by kanetaka 5 years ago.
MakeGoalReacheable_improved_v2.patch (2.8 KB) - added by kanetaka 5 years ago.

Change History (33)

Changed 7 years ago by Kieran P

Attachment: pathperf5.patch added

From Philip (2012-12-11)

comment:1 Changed 7 years ago by Kieran P

Description: modified (diff)

Changed 6 years ago by Jonathan Waller

Attachment: perfpath6-quantumstate.diff added

Rough merge with svn 13111

comment:2 Changed 6 years ago by Jonathan Waller

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.

Changed 6 years ago by Badmadblacksad-

Attachment: pathperf7.patch added

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

Changed 6 years ago by yunta

Attachment: pathperf7_dry1.patch added

Apply after pathperf7.

comment:3 Changed 6 years ago by yunta

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

comment:4 Changed 6 years ago by tuan kuranes

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 Changed 6 years ago by Ben Brian

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 Changed 6 years ago by Ben Brian

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

comment:7 Changed 6 years ago by Ben Brian

Description: modified (diff)

comment:8 Changed 6 years ago by Ben Brian

Keywords: wip added; unstable removed

Changed 6 years ago by Ben Brian

Attachment: pathperf8.patch added

Update to r13496 with some fixes

Changed 5 years ago by wraitii

Attachment: Diff.patch added

comment:10 Changed 5 years ago by wraitii

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 Changed 5 years ago by Ben Brian

Owner: philip deleted

Unassigning due to lack of progress.

Changed 5 years ago by kanetaka

Attachment: FixGoalDetection.patch added

Changed 5 years ago by kanetaka

Changed 5 years ago by kanetaka

Attachment: PathProfile.patch added

Changed 5 years ago by kanetaka

Attachment: commands.txt added

comment:12 Changed 5 years ago by stanislas69

Keywords: review added

comment:13 in reply to:  10 Changed 5 years ago by kanetaka

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 Changed 5 years ago by Itms

Milestone: BacklogAlpha 18

Changed 5 years ago by kanetaka

comment:15 Changed 5 years ago by kanetaka

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 Changed 5 years ago by Itms

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 in reply to:  16 Changed 5 years ago by kanetaka

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 Changed 5 years ago by Dave

Cc: davidshumway@… added

comment:19 Changed 5 years ago by Itms

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 Changed 4 years ago by Itms

Keywords: pathfinding added

comment:21 Changed 4 years ago by Itms

Milestone: Alpha 18Alpha 19

comment:22 Changed 4 years ago by Itms

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.