Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use a more performant pathfinding algorithm #1561

Open
Ferocimo opened this issue Sep 1, 2018 · 6 comments
Open

Use a more performant pathfinding algorithm #1561

Ferocimo opened this issue Sep 1, 2018 · 6 comments

Comments

@Ferocimo
Copy link

@Ferocimo Ferocimo commented Sep 1, 2018

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
Copy link
Member

@mcmonkey4eva mcmonkey4eva commented Sep 1, 2018

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
Copy link
Author

@Ferocimo Ferocimo commented Sep 1, 2018

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
Copy link
Author

@Ferocimo Ferocimo commented Sep 2, 2018

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.

@fullwall fullwall changed the title Server overload with NPC not finding their path Use a more performant pathfinding algorithm Jan 19, 2019
@Ferocimo
Copy link
Author

@Ferocimo Ferocimo commented May 2, 2020

@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
Copy link
Member

@mcmonkey4eva mcmonkey4eva commented May 2, 2020

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
Copy link
Author

@Ferocimo Ferocimo commented May 2, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants
You can’t perform that action at this time.