Game freezes during long actions (crafting/reading/disassembling etc)

[SilearFlare]

Describe the bug

All of the sudden after two seasons, the game has become horribly laggy, but only when crafting/reading/disassembling, and in weird spurts. It starts, runs fine for a second, but for each second it freezes for another 5/10.
I've managed isolate the problem to the overground by disabling Z-levels and going underground: crafting, sleeping etc runs fine there.

I've included the save (actually the entire folder, since there's a lot of custom stuff in there) in the zip. Just uh, ignore the red warnings, they're nothing gamebreaking but I did some fuckery to fix PK from crashing on startup, but since it's mostly PK items that got removed that really shouldn't be the problem.
I've fucked around with overmap teleportation and editing the time after finding out the problem, but that did nothing.

Steps To Reproduce

Unzip the zip and just read or craft anything above ground.

Expected behavior

Not that.

The whole dang thing

https://files.catbox.moe/hffgdu.zip

Versions and configuration

linux, curses, 64 bit :^)

[olanti-p]

A cursory glance through profiler shows that ~90% of CPU time is spent in game::overmap_npc_move on pathfinding.

This looks suspiciously like CleverRaven#44452

[Coolthulhu]

Looks like the NPC is trying to reach an island or a bit of land that is "effectively an island" by the virtue of being very far from nearest connection to the NPC.
The get_npc_path function is not equipped to deal with cases like this. It is also incredibly unoptimized, performing multiple string comparisons per tile.

There's no trivial fix. For now, I propose a vile hack: a NPC that fails to find an overmap path, becomes dumbstruck and refuses to (overmap) path until loaded into reality bubble at least once.

A proper solution would be to generate reachability maps, either for preset path types or on-demand.
The problem is combining the results from multiple overmaps: it is unacceptable to run an algorithm over an unbounded number of overmaps. Having to recalculate it over nearest 9x9 overmaps might be doable.

It would help a lot to cache the terrain types properly instead of literally checking "do the first 4 characters of the terrain type match the word 'road'?". The check should look like "does this terrain type have a 'road' flag?", with the flag ideally being an int (I think DDA has inty flags, I'll need to grab that someday).

[SilearFlare]

Oh wow, I really just thought that my PC was being extra janky as usual.
Thanks.