Algorithm to find all tiles within a given radius on staggered isometric map

Question

Given staggered isometric map and a start tile what would be the best way to get all surrounding tiles within given radius(middle to middle)?

I can get all neighbours of a given tile and distance between each of them without any problems but I'm not sure what path to take after that. This feature will be used quite often (along with A*) so I'd like to avoid unecessary calculations.

If it makes any difference I'm using XNA and each tile is 64x32 pixels.

Answer 1

I think this might be easier with a visual aide. Here are some different things we might mean when we ask for "tiles within a given radius"

From the OP's responses above, it sounds like the top-left version is desired (Euclidean - screen space). That seems to have generated a bit of confusion since most tile-based games consider ranges in tile space.

No matter which metric you use, a useful strategy is to limit your search area.

You can take advantage of the fact that in all of these metrics, the desired tiles occur in runs with no gaps in the middle (unless your tiles are sparse). I'll assume your tiles are densely packed in rows & columns (either screen-aligned or tile axis-aligned - it changes the details but not the main idea).

1. Determine the least row that could possibly overlap your radius.
2. Determine the greatest row that could possibly overlap your radius.
3. For each row in that range, determine the least & greatest columns that could possibly overlap your radius.
4. Return all tiles within these bounds.

As an example, I'm going to use the tile space Euclidean metric (top right), for simplicity.

for(row = ceil(sourceRow - radius) to floor(sourceRow + radius))
{
  rowDifference = row - sourceRow
  columnRange = sqrt(radius * radius - rowDifference * rowDifference)

  for(column = ceil(sourceColumn - columnRange) to floor(sourceColumn + columnRange))
  {
     yield GetTile(row, column)
  }
}

(Please excuse the sloppy pseudocode and lack of bounds-checking to ensure we're within the map bounds - those should be easy to add)

This version does only O(radius) distance calculations (linear in the radius, rather than quadratic as with methods that test every tile in a neighbourhood, or the brute force O(n^2) which tests every tile on the map)

If that's not directly applicable, it shouldn't be hard to adapt the basic strategy to a different metric/tile arrangement.

Answer 2

Just expand outward from the origin tile:

find(radius, origin, cell, solution) ->
    solution.append(cell)
    for n in cell.neighbors - solution
        find(radius, origin, n, solution) if dist(origin, n) <= radius

Then just pass in the origin tile as both origin and cell on the original call:

cells = []
find(radius, origin, origin, cells)

This also encapsulates away your distance function to use whichever metric you like. Note that cell.neighbors - solution is the set of all cells in cell.neighbors that aren't in solution.