Algorithm - Finding closest empty square a 2d grid

Question

Given a starting square (y, x) on a 2d grid, I want to find the closest empty square to it. (Note: The 4 squares adjacent to the starting square should be considered closer than the 4 diagonal squares nearest it.)

The following image shows the order that I need to check the following cells on this grid:

The grid is bounded but can be quite large. In practice, the starting coordinate will be randomly located around the grid. (So, I don't think it's too important to worry about coordinates outside the bounds of the grid....)

What algorithm can I use to iterate around the circle in this manner?

Answer 1

A simple breadth-first search will do it. Push each neighbour to be examined onto a heap, prioritised by distance. You can probably get away with manhattan distance (dx + dy), but if not just use squared radial distance (dx² + dy²). Whenever you pop an item it'll be the nearest. If it's empty, you found it. Otherwise push its neighbours onto the heap and keep popping.

I would probably use the square radial distance and only add adjacent squares (not diagonals). The diagonals will be considered later because they are immediately adjacent to other squares. You do need a way to keep track of which squares have already been considered so you don't add them again. There must be a clever dynamic-programming way of tracking this without having to clear a large grid of booleans each time you search... But saying that, a large grid of booleans will do quite nicely.

Answer 2

If the content of the grid changes often, use methods described in previous answers, that is bread-first search.

If the content of your grid does changes seldom AND Manhattan distance is ok for your application, my advise is to compute the distance transform of the binarized grid (0 if empty, 1 else) distance transform is very simple for Manhattan distance, way more complicated for euclidian distance). This step can be done at a cost of 2*N*M (number of elements of the grid). Then, for each request, you can visit the neighborhood in a very straightforward manner, that is follow the path of min distance starting from the starting cell (like some gradient descent), it will stop at the nearest empty cell. May be really faster to search with this algorithm, as you don't look in the wrong way for an empty cell more than 1 cell far.