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

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.

• Manhattan distance or Euclidean? Rhombic (diamond) tiles or hexagonal? Aug 2, 2013 at 21:45
• Diamond 64x32 and as for distance - Pythagorean I guess, I have each cell's middle coordinates Aug 2, 2013 at 21:57
• Given that answer, I have to ask why? What "business rule" are you trying to achieve with this proposed solution? Aug 2, 2013 at 22:00
• For example if I have an item that have a range of 100 I'd like to show visualy the area of effect, in this case it would be around the player but I can imagine many more uses. Aug 2, 2013 at 22:24
• Why are you sing Euclidean (Pythagorean distance)? There is a reason no-one is answering your question - it doesn't make enough sense yet. Also, put all answers to my questions in your question, where they can be quickly found by anyone interested in helping you out. Aug 2, 2013 at 22:31

2 Answers

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.

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.

• I believe you have missed why no-one answered this question last month: OP desires to use the true isometric distance as displayed on the screen as metric. Sep 3, 2013 at 1:47