How to find a circle (radius) in grid tiles around another tile

Question

Hey everyone,

I have made a grid system to store some data, and im wondering about the best/most performant approach to find a radius of tiles around a certain tile, or potentially multiple tiles. This radius would need to be scalable, and needs to operate every frame or close to if possible.

I have a few ideas on how to do it but they seem either super heavy or involve manually creating a circle shape for each size.

Some examples would be radius of influence in city builder games, or area of effect for explosions etc in games like xcom. If you have done something similar or have any advice, i'd really appreaciate the help!

Thanks :)

Answer 1

Answer by Eno-Khaon · Oct 26, 2021 at 12:22 AM

If all you need to know is whether objects are within a radius, rather than needing to worry about their specific distance relative to it, you can cut out the Square Root element of Vector Magnitude calculations and stop short at their Square Magnitude instead:

 // Example, radius is already cached from (radius * radius) as applicable
 if((testedTile.position - middleTile.position).sqrMagnitude < radiusSquared)
 {
     // etc.
 }

Add comment · Show 3 · Share

PacRat · Oct 26, 2021 at 02:10 AM 0

Share

Hmm ok, so do you think I should sample a square area with the dimensions of my radius, and then use this to sample each tile inside of that area, then remove the ones that aren't in range?

This could potentially be pretty heavy if I am sampling areas with a radius of 50 or more right?

Eno-Khaon PacRat · Oct 26, 2021 at 04:46 AM 1

Share

If you have the information already available, it shouldn't be so bad, really. For example, if you have your tile information in a 1-or-2-dimensional array already (or similar structure, at least), then it shouldn't be too tough to cycle through them:

 // assu$$anonymous$$g 1-dimensional array to illustrate the
 // slightly-more-complex way of preparing data
 // Example: explosion centered on (2, 315), radius 50.5
 int tileX = 2;
 int tileY = 315;
 Vector2Int tileXY = new Vector2Int(tilex, tileY);
 float radius = 50.5f;
 float sqrRadius = radius * radius;
 int radiusCeil = Mathf.CeilToInt(radius);
 int searchMinX = Mathf.Max(tileX - radiusCeil, 0);
 int searchMaxX = Mathf.Min(tileX + radiusCeil, gridWidth);
 int searchMinY = Mathf.Max(tileY - radiusCeil, 0);
 int searchMaxY = Mathf.Min(tileY + radiusCeil, gridHeight);
 
 Vector2Int currentPos; // maximize speed by declaring it only once
 for(int y = searchMinY; y < searchMaxY; y++)
 {
     currentPos.y = y; // replace value in-place without creating a new Vector2Int
     for(int x = searchMinX; x < searchMaxX; x++)
     {
         currentPos.x = x;
         if((currentPos - tileXY).sqrMagnitude <= sqrRadius)
         {
             // Tile is in range.
             grid[y * gridWidth + x].isInRange... // (etc.)
         }
     }
 }

There's a bit of redundancy in this (i.e. tileX, tileY, tileXY), but it's entirely for the sake of maximizing speed by only using struct types when optimal (as opposed to using values directly). It shouldn't be necessary for a small size like 50x50, but the more you do with each tile in the process, the more every bit will make a difference.

Namely, the example of grid[y * gridWidth + x] works under the assumption that the grid tiles are all accounted for in full, so that you aren't using GetComponent<>() or anything woefully inefficient like that. For example, even if they're all GameObjects with a "GridTile" script attached to them, those "GridTile" scripts would have all relevant references necessary on them, such as Material/Renderer/Sprite/whatever for immediate use.

Edit: Oh, right. 50 radius definitely means more than 50x50, but whatever. 2500 vs. 10000 iterations... Meh, I could substitute the 50's with 25's (i.e. diameter / 2), but I don't think the point's been lost here.

PacRat Eno-Khaon · Oct 26, 2021 at 05:46 AM 0

Share

this is awesome, way more than I expected! That should work well, my grid is all based in a 2 dimensional array so this should be pretty easy to apply. Thanks heaps I really appreciate the help @Eno-Khaon

How to find a circle (radius) in grid tiles around another tile

1 Reply

Your answer

Follow this Question

Related Questions