You haven't specified what sort of output you're looking for. If there really could be millions of grid cells unseen, finding them all will necessarily require processing millions of grid cells. So you'll need to limit your algorithm to finding a subset of those, for example:
- Finding whether a single cell is unseen, on demand
- Finding all unseen cells within a certain distance from your observer
- Finding the nearest unseen cell
The first one is easy: perform a single line-of-sight test between the cell and the observer.
The second is also easy, just perform a line-of-sight test over a subset of the entire grid. Eric Lippert's Shadowcasting algorithm is a nice one that minimises revisiting cells, but I've found a really simple one that performs line-of-sight tests to the boundary cells can also suffice.
For the third one, you can repeatedly perform line-of-sight tests starting from cells nearest to the observer and gradually search outwards, for example in a spiral pattern. Depending on your algorithm, you can avoid unnecessary duplication of cell tests - for example, if a cell that's in the same direction and closer to the observer is seen, we can assume that the current cell is also seen by the observer, and avoid performing the full test all the way to the observer. You probably still want to limit this search somehow, since if the observer is in the middle of an empty field, then the nearest unseen cell could be very far away and you'll have to search many cells. If your grid is especially sparse, you can try a ray-based approach searching for obstacles instead of cells.