How to find grid cells not seen by an object

Question

I am writing a VB.NET program.

I have a grid view which is made of multiple small cells called grid cell.

On the grid view, I have placed an obstacle (red box) and an observer (blue box).

My task is to find how to find grid cells which are not seen by the blue box. You may refer to the screenshot below.

Take note that the yellow box shape is not necessary a rectangle.

1) I have considered to loop through all grid cells in the grid view and check each of them if it is seen by the blue box.

However, there could be millions of grid cells in the grid view and looping through each of them will consume a lot of time and is not efficient.

Is there any better way to locate grid cells not seen by the blue box other than looping through all the grid cells in the view?

Thank you.

Answer 1

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:

1. Finding whether a single cell is unseen, on demand
2. Finding all unseen cells within a certain distance from your observer
3. 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.

Answer 2

For grid problems, I usually use clustering instead of operating on a single cell I take for example group 5x5 cells and loop through such clusters. So instead of looping through every cell, you could loop through clusters of cells that are made of many cells and loop through cells in the cluster only if it meets some cluster visible condition. And going further you can make a cluster of clusters and repeat this operation recursively.

You can search more about quadtrees: https://en.wikipedia.org/wiki/Quadtree

Answer 3

There is probably a way for you to divide up your grid into larger pieces, and determine visibility of the pieces as a short cut. For example, if a bigger chunk (say, like an 8x8 group of cells) isn't visible (checking the 4 corners), then you can mark the entire set of cells as not visible.

I haven't tried this, but I think something like this would work...

Take your entire grid, and dividing it into quarters. Determine visibility on each quarter by checking if you can see any of the corners of that quarter. If you can't see any of the corners, then mark the entire quarter's cells as not visible. If any one corner of a quarter is visible, then at least part of it is visible. In that case, recursively divide that quarter up into sub-quarters and repeat the process for them.