oh duh, my brain wasn't working, we'd just mark the tile dirty and do the check once when it's unloaded.
Already planning on offloading a bunch of bookkeepping onto map tile load/unload. So yea, there'd just be an algorithm that checks navigability of the tile and it gets run when a map tile is unloaded. Possibly even allowing for traps to be "pseudo-blocking", so if you have contiguous walls and traps blocking navagability, things would move across, but be forced onto the traps. Of course that isn't going to do much to zombies unless it obliterates them...
Re: "breaching", the blockage is per-tile, so we won't be checking continuity for an entire perimiter or something. Imagine it like this, if you zoom out of the normal map scale to the overmap scale (conviniently what you see on the map display), one tile is now just a single square of terrain, and hordes navigate around on it on relatively long timescales (not sure what scale exactly, basically a horde would have an "overmap move speed"). Some tiles, like deep water for terrestrial animals, are already blocking, so on the overmap scale that kind of horde wouldn't be able to cross that tile. Building contiguous wals across a tile would mark that tile as non-navigible to non-flying creatures, there might be a directionality thing, but it'd be much easier to just say the tile is blocked off entirely. That way we don't have to worry about the potentially NP-hard problem of determining connected-ness.
This means, for example, that you could have gaps all over the place but still block movement. The thing is, I'd rather it act a little funny than either delay the feature (potentially by a LOT) or not have it at all.