stranded dwarf detector

[ab9rf]

This came out of a discussion on Discord: a tool to detect dwarfs that have been cut off from the rest of the fort. This originated as a suggestion for detecting dwarfs that are stuck in trees, but we realized it may have other utility (such as detecting a dig or build error that cuts off part of the fort from the rest of the fort).

The idea is to iterate over all units, and for each unit, see if that unit can path to any other unit, using dfhack.maps.canWalkBetween. Any unit that cannot path to at least one other unit is presumably stranded somewhere and possibly in need of rescue.

The calculation is O(n^2) in the number of units, so might not want to run this too very often, but the average case cost is actually a lot lower because the iteration for any given unit can stop when any unit it can path to is found, and the canWalkBetween check is very cheap, so running this several times per game day is fairly reasonable.

[azrazalea]

I'm going to try to grab this one and make a lua script. I thought of an edge case optimization too. I currently have thoughts for 3 iterations of the script (all in the same PR).

1. The simple algorithm above (outer loop and inner loop). Pops up something similar to the "creature starving" box if found, runs ?? number of times a day if enabled.
2. Edge case optimization(not sure how much these will matter since we're using cached pathing):
   1. If you've already found someone in the inner loop as being able to be reached by someone in the outer loop then you know they are not stranded and can skip them when you get to them.
   2. If you've already found someone in the outer loop as being stranded, you don't need to have anyone else in the outer loop check if they can reach them as you already know you can't.
3. Make certain dwarves ignorable in case they are purposely stranded (using an option on the popup), save this for the fortress. This would also require at minimum a way to clear your list of ignored in case you need them around again.

Some future add-ons possible would be able to list witch citizens are ignored, add them without having to wait for a popup, and general list management. Maybe also configure how often to check and have a status view?

I'm not expecting 1 & 2 to take more than today, but 3 might take longer. If you don't hear back in 2 weeks you can assume I got busy and have someone take over/redo it.

[azrazalea]

Got something working, and it seems pretty efficient.

I've not written any DF scripts before though so I'm going in blind on the APIs. Next step is making it an alert and having it run periodically.

Once I have that running I'll get a PR up and see about the ignoring feature.

-- Detects and alerts when a citizen is stranded
-- by Azrazalea

local strandedUnits = {}

-- True means stranded, False means not stranded, nil means not processed
-- Used for optimizations
local strandedUnitIds = {}

local citizens = dfhack.units.getCitizens()

-- Outer loop, left-hand of find operation
for leftIndex, leftCitizen in pairs(citizens) do
  local isFirst = leftIndex == 1
  
  -- Citizens that already have been determined safe don't need processing
  if strandedUnitIds[leftCitizen.id] == false then goto done end

  -- Inner loop, right-hand of find operation
  for rightIndex, rightCitizen in pairs(citizens) do
    -- Citizens that already have been determined stranded are not helpful to check
    if leftCitizen.id == rightCitizen.id or strandedUnitIds[rightCitizen.id] == true then goto nextCitizen end
    
    if dfhack.maps.canWalkBetween(leftCitizen.pos, rightCitizen.pos) then
      -- Assignments are cheap enough that it's probably not worth checking if we have already set these
      strandedUnitIds[leftCitizen.id] = false
      strandedUnitIds[rightCitizen.id] = false
    
      -- If we don't use goto here the first time, then in the best case where everyone can reach everyone we only have
      -- to do the inner loop once! In worse cases we'll have to do more work anyway, so this is probably worth it.
      if not isFirst then goto done end
    end
    
    ::nextCitizen::
  end
  
  
  -- Possibly stranded dwarves won't be in this list unless already processed
  -- This even works for the first dwarf, since they would be in here already if not stranded
  if #citizens == #strandedUnitIds then goto stopProcessing end       
    
  -- If we never hit the done or stopProcessing goto then we are stranded. 
  strandedUnitIds[leftCitizen.id] = true
  table.insert(strandedUnits, leftCitizen)
  
  ::done::
end
::stopProcessing::

-- From warn-starving
local function getSexString(sex)
  local sym = df.pronoun_type.attrs[sex].symbol
  if not sym then
    return ""
  end
  return "("..sym..")"
end

print("Number of stranded: ")
print(#strandedUnits)

for _, unit in pairs(strandedUnits) do
  print('['..dfhack.units.getProfessionName(unit)..'] '..dfhack.TranslateName(dfhack.units.getVisibleName(unit))..' '..getSexString(unit.sex)..' Stress category: '..dfhack.units.getStressCategory(unit))
end

[myk002]

When you're ready for feedback, feel free to open a PR. It's much easier to attach comments to specific lines in a PR review.

[myk002]

However, let me just mention that I think this can be done in O(N) by grouping units by their pathability group id and then counting the groups. See gui/pathable for an example of how to get the pathability group.

[azrazalea]

@myk002 Yeah I was just showing that I was working on it.

I assumed by the issue description there wasn't something easy like that, my lack of DF internals knowledge is making it a little hard for me to understand how the group is being calculated but it definitely looks like that'll work! Awesome.

[azrazalea]

@myk002 Alright, got it rewritten using pathability groups! I'll have a PR up later tonight