When working with tilemaps we will often need to get all tiles in a certain area. The case of an axis aligned rectangle is the simplest and can be implemented very efficiently.
This is exactly what we will write code for here.
Requirements
The requirements for our code are rather simple and straight forward.
Given a regular, rectangular grid or tilemap, and an arbitrary rectangle, both aligned to the same axes, we would like to enumerate all tiles that are intersected by that rectangle.
For now we do not care about the order of the tiles, but we do care that there are no false positives or false negatives.
Brute-forcing it
The simplest approach would be to enumerate all tiles in our tilemap, and then only pass on those that intersect the rectangle.
In pseudo code this would look something like this:
getAllTilesInRectangle(tilemap, rectangle)
{
foreach(tile in tilemap)
if (tile intersects rectangle)
yield tile
}
Clearly, this algorithm is very inefficient. If our rectangle is small compared to the tilemap, we might enumerate a huge number of unnecessary tiles.
Calculating exact solution
Ideally, we want to only enumerate exactly those tiles we are interested in.
In the case of intersection with an axis aligned rectangle, this is very easy to do.
All we need to do is find the tiles containing the top-left and the bottom-right corners of the rectangle (or top-right, bottom-left, as long as they are opposite).
The rectangle of tiles spanned by these two tiles necessarily encompasses the entire rectangle, since it is aligned to the axis. It cannot break out of that rectangle with any diagonal or curved sides.
This means that we only have to enumerate the tiles inside that rectangle of tiles to get exactly the tiles we are interested in.
We can do this easily by accessing the tilemap using x and y coordinates, and enumerating over these in a nested for-loop.
getAllTilesInRectangle(tilemap, rectangle)
{
tileTL = tile containing rectangle.TopLeft
tileBR = tile containing rectangle.BottomRight
for(y = tileTL.y to tileBR.y)
for(x = tileTL.x to tileBR.x)
yield tile at (x, y)
}
Note that it is important that we include the x and y values of the bottom-right tile in our loop.
Otherwise we will miss one row and one column.
When implementing this in real code it is also important to make sure that the first corner tile has lower coordinates than the second one, otherwise the for-loop with simply exit.
If this is the case, we can simply take different opposite corners of the rectangle. If the orientation of our rectangle is not known, we can always use min and max functions to select the smallest and the largest corner easily enough.
Lastly, since we are blindly calculating tilemap coordinates here, we may end up with tiles that are actually outside the tilemap, if it is possible for our rectangles to extend past the tilemap.
In most cases we probably want to not return such tiles, since it is bound to cause problems, when trying to access none existing tiles.
Example implementation
Below is an example implementation that takes all the mentioned subtleties into account. If this extra work is needed will largely depend on your used rectangle type, and whether you expose this method enough to be worried about someone running into the possibly edge cases.
IEnumerable<Tile> GetAllTilesInRectangle(
Tilemap tilemap, Rectangle rectangle)
{
var topLeft = tilemap.GetTileAt(rectangle.TopLeft);
var bottomRight = tilemap.GetTileAt(rectangle.BottomRight);
var xStart = topLeft.X;
var xEnd = bottomRight.X;
var yStart = topLeft.Y;
var yEnd = bottomRigt.Y;
if(xStart > xEnd)
Swap(ref xStart, ref xEnd);
if(yStart > yEnd)
Swap(ref yStart, ref yEnd);
for (int y = yStart; y <= yEnd; y++)
for (int x = xStart; x <= xEnd; x++)
{
if(tilemap.IsValidTile(x, y))
yield return tilemap[x, y];
}
}
static void Swap<T>(ref T one, ref T, other)
{
var temp = one;
one = other;
other = temp;
}
Note that the use of a Swap helper method is of course not necessary, but I think it makes the code more readable, and it is a great method to keep in a static helper class to reuse in many other places of a bigger project.
If we are discarding invalid tiles, we may want to consider clamping our tile rectangle to only contain valid tiles in the first place. That could be done by adding a call to the following method before the loop above.
void clipRectangleToTilemap(Tilemap tilemap,
ref xStart, ref xEnd, ref yStart, ref yEnd)
{
xStart = Math.Max(xStart, 0);
yStart = Math.Max(yStart, 0);
xEnd = Math.Min(xEnd, tilemap.Width);
yEnd = Math.Min(yEnd, tilemap.Width);
}
This method assumes that the valid coordinates of the tilemap range from 0 to width/height, but it can of course be changed to other ranges easily.
If we add a call to this method, we are guaranteed to only loop over valid tiles, which means that we can take out the condition checking every single tile in the loop, and simply return them all.
Conclusion
In this post we discussed how to iterate all tiles in a tilemap intersecting an arbitrary axis aligned rectangle.
If you find the post useful, make sure to share it on your favourite social media.
Next time we will expand on the above and look at how to efficiently return tiles intersecting an arbitrary circle instead.
Enjoy the pixels!