Radial Grid Search Algorithm

Question

I'm sure there's a clean way to do this, but I'm probably not using the right keywords for find it.

So let's say I have a grid. Starting from a position on the grid, return all of the grid coordinates that fall within a given distance. So I call something like:

getCoordinates( currentPosition, distance )

And for each coordinate, starting from the initial position, add all cardinal directions, and then add the spaces around those and so forth until the distance is reached. I imagine that on a grid this would look like a diamond. The function would return that array of coordinates. Can someone point me to a routine that will do this efficiently ( I'm working in AS3, for what it's worth )?

In the desired output, iteration 1 would be:

.x.
xxx
.x.

Iteration 2 would be:

..x..
.xxx.
xxxxx
.xxx.
..x..

Iteration 3:

...x...
..xxx..
.xxxxx.
xxxxxxx
.xxxxx.
..xxx..
...x...

and so on...

Answer 1

It depends what kind of data structure you're using to represent your grid, but generally a breadth-first search should take care of this for you.

Answer 2

Edit: Updated the algorithm to reflect what the OP wanted.

Iteration 1:

.x.
xxx
.x.

Iteration 2:

..x..
.xxx.
xxxxx
.xxx.
..x..

... Iteration 4:

....x....
...xxx...
..xxxxx..
.xxxxxxx.
xxxxxxxxx
.xxxxxxx.
..xxxxx..
...xxx...
....x....

Clearly, you can determine the coordinates without iterating.

If the starting point is (X, Y), and the iteration is n

for(int i = x - n; i <= x + n; i++)
{
    for(int j = y - n; j <= y + n; j++)
    {
        int dx = abs(i - x);
        int dy = abs(j - y);
        if(dx + dy <= n) //Produces a diamond, n+1 would produce a diamond with cut corners
        {
            //The point at (i, j) is within the marked area.
        }
    }
}

Answer 3

BFS + FIFO queue:

P = U = 0;
Q[P] = currentPosition;
D[ Q[P] ] = 0; D[~all the rest~] = infinity (or really any flag, such as -1)

while ( P <= U )
{
  current = Q[P];
  ++P;

  for ( each neighbor N = (X', Y') of (current.X, current.Y) )
    if ( D[N] == inf && D[current] + 1 <= distance )
    {
      D[N] = D[current] + 1;

      ++U;
      Q[U] = N;
    }    
} 

Answer 4

Two possibilities, depending on what kins of distance you want and how much programming you are willing to do:

(1) Dijkstra's algorithm. If you imagine that each two neighboring points on you grid are connected (only vertical and horizontal connections, so each point has 4 neighbors), you'll get your diamond. You don't have to implement any data structure for the graph -- you only need to generate lists of neighbors for current vertex, as you go.

(2) Fast marching. This'll give you true Euclidean distance within the numerical error, so you'll get an approximate circle, not a diamond.

Answer 5

For Iteration N, you want all points P' such that distance from P to P' <= N, where distance is |X' - X| + |Y' - Y|.

for (int i = -N; i <= N; i++)
   for (int j = abs(i) - N; j <= N - abs(i); j++)
   {
      results.Add(new Point(X+i, Y+j));
   }
}

return results;