Long/Tile Pathfinder Rewrite

[Kieran P]

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.

[Kieran P]

From Philip (2012-12-11)

[Jonathan Waller]

Rough merge with svn 13111

[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.

[Badmadblacksad-]

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

[yunta]

Apply after pathperf7.

[yunta]

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

[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 ?

[historic_bruno]

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".

[historic_bruno]

Update to r13496 with some fixes

[Philip Taylor]

Latest version of the patch is currently at ​http://git.wildfiregames.com/gitweb/?p=0ad.git;a=shortlog;h=refs/heads/projects/philip/pathfinder

[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.

[historic_bruno]

Unassigning due to lack of progress.

[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%.

[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.

[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 :-)

[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.

[Itms]

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.

[Itms]

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