Use a more performant pathfinding algorithm

[Ferocimo]

Server : git-Paper-1230 (MC: 1.12.2)
Plugin version : Citizens 2.0.24-SNAPSHOT (build 1567)
Config : https://pastebin.com/XW3FCirN
Timings : https://timings.aikar.co/?id=38f2ec8e33bc4b72abd80abb52a185cb#plugins
Save.yml : if really needed please PM. But this bug can occur even with one NPC, in the correct setting.
Server specs : CPU: Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
RAM: 64 GO
SSD: 450 GO

Hello,

If an NPC has not a clear path and cannot reach target (for instance, he's on a tree, or something is blocking the way), the CPU of the server starts overloading and the TPS drops massively. This can slow down the whole server with only one NPC.

For more information, and especially on server monitoring, there is a certain issue that apparently we can't talk about since it isn't posted by us even though we have the same issue, posted on Sentinel, number 179, that has done some research on the matter.

If needed we can also provide some testing and more data.

Thank you for looking into this.

[mcmonkey4eva]

The other issue post was closed because it was literally just posting a link to somebody else's issue with nothing more in the post, which is not a valid issue post in the slightest.

use-new-finder config setting is highly relevant here.

This is a messy issue to fix effectively... because in A* pathfinding (and most pathfinding algorithms), it's rather computationally expensive to prove that no path exists (as the alg first assumes a path exists then tries to find it, and only gives up when all possible options are exhausted)

use-new-finder set to true uses a generally more capable and functional pathfinder, but at the cost of being more costly on the CPU. Set to false weakens its capabilities and general accuracy, but makes it significantly less of a pain on the CPU (false makes NPC pathfinding use the same codepaths as are used by vanilla minecraft mobs running around)

[Ferocimo]

I understand, but the "use-new-finder" was the fix to another issue we posted a while ago, with NPCs not knowing what to do in water.

So if we disable it, we'll have this issue again.

[Ferocimo]

Update : it's indeed specific to new-finder. We now turned it off, but it's too bad we can't use it, so this issue should still be fixed some day if possible. I'll leave this open in the mean time.

[Ferocimo]

@fullwall @mcmonkey4eva

Hello,

As previously said, we still can't use new-finder because it causes massive performance issues (even with a server designed to host easily 120 players, the server will have a TPS of 14 with no players on it, just with NPCs).

As a result we are obligated to disable new-fidner, which causes the following issues :
mcmonkeyprojects/Sentinel#335

(NPCs not knowing what to do on water, on carpets, on slabs, etc).

So we have to choose between massive performance drops (which we can't choose, obviously), or tons of pathfinding issues. Currently we're stuck with the later, it's been nearly two years since this was posted.

Do you think any improvement could be made in a close future ?

[mcmonkey4eva]

It's being worked on. Fullwall has been experimenting quite a bit with new pathfinding code.
See for reference this in-progress system https://github.com/CitizensDev/CitizensAPI/tree/master/src/main/java/net/citizensnpcs/api/hpastar

It's not been the highest priority but it has actually been relatively high, and been a topic of discussion on the Discord a fair bit.

[Ferocimo]

Okay thank you for the update on status, we'll wait for the fix.