For one I don't want to find cover from a specific character's current location, it's more to realize what areas are "danger" areas in general. So if stepping outside a building or into a corridor intersection, the AI needs to be able to realize it might be walking into a hostile location.

Aggregate danger level of each tile is computed by combining threats from each enemy. If 2 gunners see a certain map square, if I cross it they'll shoot me twice as much as 1 gunner.

So I really need a data structure on top of the walkable node areas where I can query if 2 nodes are visible to each other that returns a fast result. But generating that out in brute force could be quite time consuming and require a lot of space. There's something like 100k nodes in a typical map I'm using.
[/quote]The most efficient calculation should be first iterating over all enemies (much fewer than map nodes) and mark where they can shoot storing data in map nodes, then aggregate threat data only in places that are actually used in pathfinding (caching everything after the first access).

Now I'm trying to think if there's some way to partition this into larger spaces then connect those or something.
[/quote]
Most likely you'll have to make some approximation: if danger levels are fudged to be uniform over a larger region, you'll need to store and compute less of them. What are your current map data structures?

It needs to be independent of the location of enemies, which are unknown to the AI. The idea is to figure out the intersections of areas where every node in the area is visible to every other node in the area.

So don't think of it like pathfinding as in many games. Once I identify the locations of note I know what behaviors I want and how to achieve them.

Right now I just have a bit array that shows if location is walkable or not, plus they are in regions but the regions are not convex any more due to some changes I made recently. I'm thinking to add a link to some data structure that says what is visible from where. The important part though is to find the transitions, like I explained.

I'm looking into dynamic connectivity structures like link-cut trees but I don't think it needs to be dynamically updatable necessarily. But if there's a freely available implementation of that and it works like I think maybe that should at least take care of building the structure itself which would be nice.

For similar games a lot of time it's tile based. So it's obvious you have a door tile or window tile and that makes the AI easy to deal with for that spot. You know what the entrances and exits are pretty naturally. The problem is I don't really limit things like this, because it doesn't make as much sense and also I want to avoid having to hand place AI markers or having maps that are tile based (though in 3D) and squarish maps or maps that consist of tons of corridors.