Trinitycore: [Crash] Freeze in dtNavMeshQuery::findPath

[sirikfoll]

Description:

Core freezes in dtNavMeshQuery::findPath,
it loops with nodes pidx 115 -> 116-> 104 -> 115
and endNode 163

Relevant Positions
start = {x = 5825.4165, y = 649.498962, z = 609.336792}
dest = {x = 5819.81982, y = 643.027893, z = 609.885925}

CrashLog: https://gist.github.com/sirikfoll/290c09e12b63ef477534c71b127b8909

Steps to reproduce the problem:

Not precise at all, but..

1. .go xyz 5825.878906 650.455505 609.157959 571
2. .mod speed all 6
3. .cast 42650 (summon Army of the Dead)
4. Run with your character from one platform to another, to make the pets cross in the water, they get stuck in there.

Branch(es): 3.3.5

TC rev. hash/commit: 3a83dc60d5bd

Operating system: Windows 10

[Jildor]

hhmmm, seems similar: https://github.com/TrinityCore/TrinityCore/issues/19553
it isn't the same crashlog, but, the zone it's the same and similar crashlog

[illfated]

Thanks for describing that issue in detail, I did notice something related,
only briefly and without doing any extreme moves (normal running).

I was picking infused mushrooms and some of those Dalaran elixir bottles,
when all of a sudden my bear didn't want to follow me past some fixture or building part.
Mounting and dismounting solved it for me, no crash or core freeze.

[jackpoz]

https://github.com/TrinityCore/TrinityCore/commit/c8ec2dd95d07e3eec00027cdb9605529a49d6475 is some kind of emergency fix for this.
I loaded the tile in recast demo and that area with the platforms makes detour pick strange paths (the usual issue where a straight path has higher cost than a zig-zag path but crossing less polys).
It would be nice to reproduce it in recast demo and report it to recast, or even in TC hardcoding the positions just to trigger the issue.

[jackpoz]

I'll change https://github.com/TrinityCore/TrinityCore/commit/c8ec2dd95d07e3eec00027cdb9605529a49d6475 to a loop iteration count check after we get a bit more info about the issue, currently tracked also at recast itself at https://github.com/recastnavigation/recastnavigation/issues/343

[jackpoz]

I wonder if we could use the node pool size as upper limit

[jackpoz]

https://github.com/TrinityCore/TrinityCore/commit/12e6faa0fa0cf389bcebd4a6f2220e71c697250c changed the check to exit early.
We can consider this issue low priority now that it doesn't cause anymore an infinite loop and that the code to check for that is "good enough"

[sirikfoll]

Still crashes in rev 59682bbd9b33, now it loops here
for (unsigned int i = bestPoly->firstLink; i != DT_NULL_LINK; i = bestTile->links[i].next)
inside dtNavMeshQuery::findPath
CrashLog: https://gist.github.com/sirikfoll/e2992bcef5d26d0fe6ca5e2256a9fb27
Updated the Repro steps, instead of a hunter with pet, use a dk with Army of the dead (.cast 42650)

[lost-illusion]

@jackpoz @sirikfoll
What do you think about https://github.com/recastnavigation/recastnavigation/pull/374 ?

[jackpoz]

that's the result of the discussion at https://github.com/recastnavigation/recastnavigation/pull/373

[lost-illusion]

I know, read conversation before, i mean it's working fix ? Or something "in progress" (maybe you checked this)

[jackpoz]

it doesn't fix all the bad triangles created in Recast and that's kind of the main issue. Feel free to test if that PR hides more infinite loop cases.

[Jildor]

can we implement in disables table a way to disable MMAP by area like VMAPs?
if it's possible maybe a temp fix disable this area (only for preven crash temporary)

[jackpoz]

might just revert https://github.com/TrinityCore/TrinityCore/commit/5ff88ea04aec4677f1c1d669674e5442288a25e3 , that's the easiest fix

[jackpoz]

Next steps:

• use https://github.com/jackpoz/recastnavigation/commits/3.3.5-recast_bisect and keep merging some commits until mmaps_generator produces a "bad" tile (which can be loaded in RecastDemo using https://github.com/jackpoz/recastnavigation/commits/master ). It will be an excuse to learn to use git bisect.
  If anyone would like to have fun with git bisect:

git checkout -b 3.3.5-recast_bisect 2c85309280dbc9c82029e7ab16dfb01b9235c74e
git cherry-pick -x 2f535adba13bcc0f6fa8ea51386caffce908f85d
$goodhash = git rev-parse HEAD
git merge recastnavigation/master
git rebase $cherryhash --force-rebase
$badhash = git rev-parse HEAD
git bisect start $badhash $goodhash

• report the commit to recast team and help them fix the issue
• if this takes too long, revert https://github.com/TrinityCore/TrinityCore/commit/5ff88ea04aec4677f1c1d669674e5442288a25e3 (by also restoring version 7 of mmaps in case someone didn't delete them yet) . I would prefer to just fix recast myself as I've always done without reverting (mmaps re-extract required) and then merge again with the fixed version (another mmaps re-extract required). We'll see.

[lost-illusion]

I'm apply changes from PR as temporary solution. Write something tomorow.

[jackpoz]

As discussed with Shauren in April for Shattrath, this is caused by a "wet roat/wet floor" issue: there are some small puddles on the floor that make recast create a tile with a lot of different GROUND/WATER areas while it should just be handled as a whole GROUND area. This happens because https://github.com/recastnavigation/recastnavigation/blob/master/Recast/Source/RecastRasterization.cpp#L133 favours area types with higher ids and we have GROUND = 0x1 and WATER = 0x8.
A simple fix is to change the order of importance, making GROUND win against WATER.
Here's a small patch that I will push to 3.3.5 after a bit of extra testing and comparision:

 dep/recastnavigation/Recast/Source/RecastRasterization.cpp | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/dep/recastnavigation/Recast/Source/RecastRasterization.cpp b/dep/recastnavigation/Recast/Source/RecastRasterization.cpp
index a4cef74909..a8b35f34f9 100644
--- a/dep/recastnavigation/Recast/Source/RecastRasterization.cpp
+++ b/dep/recastnavigation/Recast/Source/RecastRasterization.cpp
@@ -130,7 +130,12 @@ static bool addSpan(rcHeightfield& hf, const int x, const int y,

            // Merge flags.
            if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr)
-               s->area = rcMax(s->area, cur->area);
+           {
+               if (s->area == 0)
+                   s->area = cur->area;
+               else if (cur->area != 0)
+                   s->area = rcMin(s->area, cur->area);
+           }

            // Remove current span.
            rcSpan* next = cur->next;

This is how it looked before:

This is how it looks now:

It would be nice to play a bit more with recast code to ensure small polys get simplified enough everywhere, not just in Dalaran Underbelly.

[lost-illusion]

Good news. I hope you can finally fix this problem.

I'm apply path from 374 pr and now, it freezing in NormalizePath() = |

[jackpoz]

One note about the patch above: it still gives some issues in case .\mmaps_generator 547 --debugOutput "true" --tile "32,31"
Without the change:

With the change:

Going to try rcMedianFilterWalkableArea() to see what changes

[jackpoz]

wrapping up:

1. we made ground win over water when the water level is very low (think about a road after it has rained, it's wet and full of puddles but it's still ground, none is going to swim there)
2. we reported the infinite loops to recast guys and they added std::isfinite() checks in a PR to deal with degenerated triangles with 0 area which trigger a NaN float that wreaks havoc all around. We merged that PR into TC code.
3. we added rcMedianFilterWalkableArea() to simplify areas where there are many small ground/water polys