NPCs assigned to faction camp construction tasks appear to cause the game to run incredibly slowly.

[Froffy025]

Describe the bug

Title. My game is running slowly ever since I assigned my NPC to perform a construction task. Message report shows that NPC is "trying to find necessary items to do the job" 300-400 times every time I move. Telling the NPC to stand guard and follow causes the issue to stop.

Attach save file

Monarch_copy-trimmed.tar.gz

Steps to reproduce

1. Create player & NPC
2. Create faction camp
3. Use construction zones to try to create project (in my case, a log cabin with furniture, roof, etc.), basecamp storage to store some of these materials
4. Assign NPC to faction camp to do construction work

Expected behavior

I expected the NPC to either find the materials in storage, or not be able to find them and give up for a while. However, they instead lagged my game by checking more than once per turn.

Screenshots

Versions and configuration

• OS: Windows
  • OS Version: 10.0.19044.2728 (21H2)
• Game Version: a33c958 [64-bit]
• Graphics Version: Tiles
• Game Language: System language []
• Mods loaded: [ Dark Days Ahead [dda], Disable NPC Needs [no_npc_food], Portal Storms Ignore NPCs [personal_portal_storms], No Fungal Growth [no_fungal_growth], Bionic Professions [package_bionic_professions], Stats Through Skills [StatsThroughSkills], Stats Through Kills [stats_through_kills], SpeedyDex [speedydex], Blaze Industries [blazeindustries], Bombastic Perks [bombastic_perks], Translate Complex Dialogue [translate_dialogue] ]

Additional context

No response

[PatrikLundell]

Yes. My experience is that you have to monitor the start of companion construction tasks to verify that they're able to path to the construction location and are able to use construction materials. This can mean setting up storage zones right next to the construction location, handing them the tools needed manually, and lead them by the nose to the construction location. You also have to make sure they're then not trying to defect to take up some other construction activity elsewhere. You basically have to ensure they're actually doing what they're tasked with doing (check their activity) to make sure they're not stuck in some continuously failing task (in the benign case they give up immediately when they "can't find" the tools in front of their noses, etc. In that case you can at least see they're unable to do the task, even if you're left to try to figure out why (Lack of inventory space? Lack of sufficient skills? Unable to find materials, legitimately or not?...)).

It can be noted that I've also seen similar issued with other zone activities, such as sorting, where the morons have walked into a wall and just stand there trying again and again to just walk through the wall (at least that's what I think they're trying to do) to reach the target location. I don't know what causes this pathing issue, but a possibility might be that pathing somehow is based on what the map looked like initially, before any construction was made.

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not bump or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.

[RenechCDDA]

So, part of the problem is that we're now searching z-levels as of #65613

Specifically zone_manager::get_point_set_loot is given an argument for radius from requirements_map. radius is set to ACTIVITY_SEARCH_DISTANCE (60 tiles) - but it's applied to both xy coordinates and z-levels in zone_manager::get_point_set_loot https://github.com/CleverRaven/Cataclysm-DDA/blob/eddf8588664ed5b5e770f9f756cb8486738e0e29/src/clzones.cpp#L788

I made a simple patch(example only, should not be PR'd) to test how badly this was affecting it. https://github.com/CleverRaven/Cataclysm-DDA/commit/40ead9c24c4d541e08a3bd30982bfe7b8a9a1aad

Going from 121 z-levels of searches to 3 is theoretically 40x faster. I can't tell you exactly how much faster it is, I can only tell you that after the patch moving a tile in the provided save takes about 10 seconds. Previously I had left the game sit for several minutes before terminating the process, as it seemed to hang indefinitely.

So the performance is still terrible, but the z-level checks likely need to be addressed (or reconsidered) in addition to the root cause.

[Zireael07]

Going from 121 z-levels of searches

Why would you ever need 121 z-levels? Only around 10 or so are actually used in game...

[RenechCDDA]

It's not particularly intentional (and the game may be capping it to searching z+10 to z-10, but that would still be several times more tiles than previously flat search). ACTIVITY_SEARCH_DISTANCE is just a very large value which gets passed as both the xy(2d) and z(vertical) values to search.

The PR basically made all searches spherical(3D) instead of circular(2D), which is a fine implementation - but now we have an actual case where that may cause performance issues.

[SurFlurer]

zone_manager::get_point_set_loot() itself looks stressful on processor ( needing to iterate over more than 220,000 tiles. Considering how large the number of zones in the zone manager can get, it seems even more stressful).

Maybe we should get nearby zones first, then push every point in the zones into the set, then remove all points in nearby zone_type_NO_NPC_PICKUP zones ( getting these zones through zone_manager::get_near_zones() ).

unordered_set is super fast for adding and deleting elements. Time to take advantage of this.

[SurFlurer]

https://github.com/CleverRaven/Cataclysm-DDA/blob/5820766101efba4da283f8175e0b891bac188a49/src/activity_item_handling.cpp#L3011-L3016

Oh my god it hit here. Maybe we should cancel the activity instead.

On a second thought, we can add a counter. If this part gets hit more than twice in one turn, cancel the activity which wants to fetch things. This can avoid infinite loop.

So there are 3 things that need fix:

1. The infinite loop.
2. Low efficiency of that function.
3. The NPC silently fails to retrive resources for no obvious reason.

[SurFlurer]

I composed an optimized version of get_point_set_loot()( not fully tested, may be buggy, only for test purpose)

The main principle is to check for zones that are fully inside the range or partially inside the range, and insert the tripoints of them if appropriate.

diff --git a/src/clzones.cpp b/src/clzones.cpp
index 0f426ba8df..b168cc8d5d 100644
--- a/src/clzones.cpp
+++ b/src/clzones.cpp
@@ -783,19 +783,75 @@ std::unordered_set<tripoint> zone_manager::get_point_set_loot( const tripoint_ab
 std::unordered_set<tripoint> zone_manager::get_point_set_loot( const tripoint_abs_ms &where,
         int radius, bool npc_search, const faction_id &fac ) const
 {
-    std::unordered_set<tripoint> res;
+    auto const check = [&fac]( zone_data const & z ) {
+        return z.get_faction() == fac && z.get_type().str().substr( 0, 4 ) == "LOOT";
+    };
+    auto const check1 = [&where, &radius]( zone_data const & z ) {
+        return square_dist( z.get_end_point().xy(), where.xy() ) <= radius &&
+               square_dist( z.get_start_point().xy(), where.xy() ) <= radius;
+    };
+    auto const check2 = [&fac, &where, &radius]( zone_data const & z ) {
+        return square_dist( point_abs_ms( z.get_end_point().x(), z.get_end_point().y() ),
+                            where.xy() ) <= radius ||
+               square_dist( point_abs_ms( z.get_end_point().x(), -z.get_end_point().y() ),
+                            where.xy() ) <= radius ||
+               square_dist( point_abs_ms( -z.get_end_point().x(), z.get_end_point().y() ),
+                            where.xy() ) <= radius ||
+               square_dist( point_abs_ms( -z.get_end_point().x(), -z.get_end_point().y() ),
+                            where.xy() ) <= radius ;
+    };
+    std::vector<const zone_data *> tier1;
+    std::vector<const zone_data *> tier2;
     map &here = get_map();
-    for( const tripoint &elem : here.points_in_radius( here.getlocal( where ), radius, radius ) ) {
-        const zone_data *zone = get_zone_at( here.getglobal( elem ), true, fac );
-        if( zone == nullptr ) {
-            continue;
+    for( const zone_data &zone : zones ) {
+        if( check( zone ) ) {
+            if( check1( zone ) ) {
+                tier1.emplace_back( &zone );
+                continue;
+            }
+            if( check2( zone ) ) {
+                tier2.emplace_back( &zone );
+                continue;
+            }
         }
-        if( npc_search && has( zone_type_NO_NPC_PICKUP, where ) ) {
-            continue;
+    }
+    for( zone_data *it : get_map().get_vehicle_zones( get_map().get_abs_sub().z() ) ) {
+        if( check( *it ) ) {
+            if( check1( *it ) ) {
+                tier1.emplace_back( it );
+                continue;
+            }
+            if( check2( *it ) ) {
+                tier2.emplace_back( it );
+                continue;
+            }
+        }
+    }
+    std::unordered_set<tripoint> res;
+    auto range = here.points_in_radius( here.getlocal( where ), radius );
+
+    for( const zone_data *zone : tier1 ) {
+        for( const tripoint_abs_ms &p : tripoint_range<tripoint_abs_ms>(
+                 zone->get_start_point(), zone->get_end_point() ) ) {
+            res.emplace( here.getlocal( p ) );
+        }
+    }
+    for( const zone_data *zone : tier2 ) {
+        for( const tripoint_abs_ms &p : tripoint_range<tripoint_abs_ms>(
+                 zone->get_start_point(), zone->get_end_point() ) ) {
+            if( here.inbounds( p ) ) {
+                res.emplace( here.getlocal( p ) );
+            }
+        }
+    }
+
+    if( npc_search ) {
+        auto no_pickup = get_point_set( zone_type_NO_NPC_PICKUP );
+        for( const tripoint_abs_ms &p : no_pickup ) {
+            res.erase( here.getlocal( p ) );
         }
-        res.insert( elem );
     }
-    return res;
+    return std::move( res );
 }

 std::unordered_set<tripoint_abs_ms> zone_manager::get_vzone_set( const zone_type_id &type,

With this change, passing one turn in the provided save cost around 0.5 second ( there's still 100 failed attempts to fetch resources in one turn. ). Hundreds times faster than current implementation.

[lispcoc]

@SurFlurer Do you have any plan to make PR about this? IIf not, I'm planning to try to reduce amount of calculation.

[SurFlurer]

@SurFlurer Do you have any plan to make PR about this? IIf not, I'm planning to try to reduce amount of calculation.

Hi there, feel free to do that! As a side note, I've realised there are bugs in the code piece I posted above 😄

However I believe the real problem is the infinite loop. It shouldn't be too slow if that slow function only runs few times.

[lispcoc]

This issue has been partially resolved. However, the job search algorithm itself is still inefficient, with a slight lag every 10 minutes. I should bring the pruning process earlier in order to eliminate useless searches. but it needs eliminate ad-hoc implementation. Source code should be organized and structured.

[akrieger]

It's not far enough yet. There's issues with other activities which fail to fetch tools. The bail condition that's supposed to skip the activity doesn't get triggered because the requirements id is randomly generated every time the function is entered.

https://github.com/CleverRaven/Cataclysm-DDA/blob/9a345c5c4d0a0e800e10f973c8100096bc38f7f5/src/activity_item_handling.cpp#L2789-L2792

https://github.com/CleverRaven/Cataclysm-DDA/blob/9a345c5c4d0a0e800e10f973c8100096bc38f7f5/src/activity_item_handling.cpp#L2868-L2875

Then NPCs get a thousands of jobs long job history failing to fetch stuff.

See eg. #68299

[akrieger]

I think since #68299 was resolved, this is resolved?

[RenechCDDA]

There's a big spike on the first turn and profiling says it's NPC activity related but it seems to clear up after that.

Should be good to go