Trinitycore: Core/Mmaps: Weird generated paths

[Killyana]

Description: In many cases Npcs choose a weird path when they must move from point A to point B

For example on culling of Stratholm if you speak to Arthas you will see Uther choosing a weird path.

This SAI will reproduce the issue with Uther:

UPDATE `creature_template` SET `AIName`='SmartAI' WHERE `entry` IN (321);
DELETE FROM `smart_scripts` WHERE `entryorguid` IN (321) AND `source_type`=0;
INSERT INTO `smart_scripts` (`entryorguid`,`source_type`,`id`,`link`,`event_type`,`event_phase_mask`,`event_chance`,`event_flags`,`event_param1`,`event_param2`,`event_param3`,`event_param4`,`action_type`,`action_param1`,`action_param2`,`action_param3`,`action_param4`,`action_param5`,`action_param6`,`target_type`,`target_param1`,`target_param2`,`target_param3`,`target_x`,`target_y`,`target_z`,`target_o`,`comment`) VALUES
(321,0,0,0,1,0,100,1,0,0,0,0,69,0,0,0,0,0,0,8,0,0,0,1897.018, 1287.487, 143.481,0, '321 - Ooc - move to pos');

Steps to reproduce the problem:

1. Execute the sql
2. .go xyz 1794.357f, 1272.183f, 140.558f 595
3. .npc add temp 321
4. Notice the chosen path

Notice if you disable the path finding in the action the issue doesn't happen:

(321,0,0,0,1,0,100,1,0,0,0,0,69,0,0,1,0,0,0,8,0,0,0,1897.018, 1287.487, 143.481,0, '321 - Ooc - move to pos');

Branch(es):3.3.5

TC rev. hash/commit: rev. 28591fd1658

[xvwyh]

There aren't any screenshots or videos to showcase the issue, so I can't be sure if it's related, but there's one glaring issue with pathfinding in TC I know:

For some reason, in https://github.com/TrinityCore/TrinityCore/blob/master/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp the value of the constant H_SCALE is set to 2.0f. This is a custom TC edit, in the original repo (https://github.com/recastnavigation/recastnavigation/blob/master/Detour/Source/DetourNavMeshQuery.cpp) you can see the value being set to 0.999f. I'd love to hear the reasoning behind this change in TC, because the end result of it is that it causes units to prefer corners of navmesh polygons over edges.

In particular, I saw the trash in Halls of Reflection escape sequence picking the most odd paths instead of going straight after players/Jaina/Sylvanas:

Setting it back to 0.999f fixed this. Try to do the same and see if it fixes your issue. Rebuilding mmaps is not needed.

[Killyana]

Yes LK and mobs in Halls of Reflection has also this issue.

[Killyana]

I changed H_SCALE to 0.999f and the issue in culling of Stratholm is fixed.
In Halls of Reflection LK path and mobs movements looks better even if lk still have a weird path but even with CREATURE_FLAG_EXTRA_IGNORE_PATHFINDING I got the same result so it's a script issue.

@jackpoz any idea abut this change https://github.com/TrinityCore/TrinityCore/commit/0892c71a16a1fc01822946bdb006eff5bdec9315#diff-5fbf53c24284948216c3edd259ac3491R331 ?

[Shauren]

ugh, venugh thing
i wonder how many surprises from that guy will be found in pathfinding code (why the fuck did we ever let him port this)

[Warpten]

If I ever get done with vulkan debugging this garbage will be a lot easier

[jackpoz]

Let's set it back to the original value then and see what happens

[Teppic1]

After setting it to 0.999f I noticed the kobolds at the entrance to Northshire mines no longer stand mid air when moving around, a bug that's been around forever. Or at least I couldn't reproduce it, where before it was happening all the time.

[Shauren]

Revert it without questioning it. As I said earlier its something venugh guy randomly changed without explanation and wasn't caught during review, its 0.999 in cmangos

[Killyana]

There's still some issues:
.go xyz 1773.751, 1266.626, 138.9953 595
.npc add temp 321
.go xyz 1924.078, 1287.233, 143.684
.mmap path on the npc

Notice the generated path is not correct

[jackpoz]

can you post a screenshot ?

[Killyana]

You can see here 2 paths one is correct and the one at the left is wrong, I just made one step to the left and the whole path was changed:

[xvwyh]

RecastDemo behaves the same way, so this isn't a TC's problem:

And here is an even more egregious example where the path takes a scenic detour around a tree. Guess the library's name was, in a way, prophetic.

[jackpoz]

Path finding is best in the short distance, the example above looks quite long imho. A waypoint path would probably fit better

[Killyana]

Yes in Treeston rewrite it was changed to waypoint, Also this path is not used by the npc, it's just an example.

[Killyana]

The issue on Halls of Reflection is related also as summoned npcs will use mmaps when chasing players so if the distance is something like 90m the generated paths will looks like this:

Same for LK as his chasing Jaina/Sylvanas

[xvwyh]

I'm absolutely not an expert on this, and I may be wrong, but I think this is just an unavoidable side effect of how Detour works.

If I recall correctly, everything Detour does pathfinding-wise is that it gives you a list of navmesh polygons you need to pass through to get from start polygon to end polygon: PathGenerator::BuildPolyPath: _navMeshQuery->findPath. Detour doesn't care about spatial locations of these polygons, only about their connections to each other. Navmesh could very well just be represented as a graph of nodes (polygons) with connections being... I dunno, let's say distance between polygon centers. In such an isolated system that cares not about positions, the resulting list of polygons may very well be the most optimal path between the two points... if we were to always pass through the center of every polygon.

But then the core, after receiving that space-agnostic list of polygons, has to somehow create an actual walkable path through them: PathGenerator::BuildPointPath. And to do that, it just "nudges" the position along each polygon's surface until it finds a way to the next polygon in the list: PathGenerator::GetSteerTarget. Venturing outside of the provided polygons is a no-no - we don't know what lies outside. So in the worst case, the path will end up going right along the edge of the polygon, like on the first screenshot I from my comment above, even if it would've made more sense to go through the adjacent polygon instead: Detour didn't tell us about it - we don't even know it exists.

This nudging can also cause the creature to "overshoot" at sharp corners, because the nudge distance was higher that it needed to be to just make a sharp turn around a bend.

If I am correct, then the only solution would be to make mmap cell size smaller. 2 or even 4 times smaller. Split polygons more, allow for more granularity in which polygons are picked during pathfinding, because currently we only have huge chunks of ~22 yards in length, so it's either one 22 yard chunk or the other adjacent 22 yard chunk, nothing in-between.

[Killyana]

As the issue is related to Recastnavigation, this ticket will be closed.
And don't use move to point when the distance is huge, a waypoint is better in this case, and always test the result IG.
Thanks @xvwyh