Question about getting tiles that resemble a circle in a square grid

Question

First of all, I am not sure if this question should be asked here, since it might be more of a general question about algorithms. Let me know if I am out of line.

In my game I use a grid of integer coordinates ( (0,0), (0,1), ...) to hold info the map/level
I am trying to get an array of coordinates (Vector2(x,y)) that "resembles" a "circle" around a given starting start_pos and 2 int, min_range and max_range. The purpose is to have a list of valid tiles for attacking at a distance in a tactical RPG grid based game.

I have found a way of implementing it, but seems quite bloated, and was wandering if there is a simplier way of doing it.

func get_tiles_in_ranges(start_pos: Vector2, min_range: int, max_range: int) -> Array:
    var out = []
    for R in range(min_range, max_range + 1, 1):
        out.append_array([
        start_pos + Vector2(R,0),
        start_pos + Vector2(-R,0),
        start_pos + Vector2(0,R),
        start_pos + Vector2(0,-R),
        ])
        for x in range (1, R, 1):
            var y = R - x 
            out.append_array([
               start_pos + Vector2(x,y),
               start_pos + Vector2(-x,y),
               start_pos + Vector2(x,-y),
               start_pos + Vector2(-x,-y),
            ])
    return out

Also, is there a good source/book of usefull algorithms for these type of grid/tactical games? Thanks in advance!

edit: to clarify it should look like ( in the case of min_range =1, max range=3) (the blue tiles)

Answer 1

I am not sure how 3 arguments in rangework, but I guess You could get surrounding tiles in square shape and than check them for distance to the original ?

#pseudocode below

 for x in range(min_range,max_range + 1,1):
        for y in range((min_range,max_range + 1,1):
               var target = startingtile + vec2(x,y)
               if target.distance_to(starttingtile) > mindist and < maxdist:
                        tilesincircle.append(target)

Comments

Thanks for the awnser! This wouldnt work because you are leaving out some tiles. For example with min_range = 3 max_range=4 you want the tiles (3,0) (2,1) (1,2) (0,3) (and the corresponding negatives ones) and you are not getting either (2,1) or (1,2). I tried yor method starting x and y from cero, and then you get some extra tiles at the outer borders like (3,2) which you shouldnt be getting ( you should be getting (4,0) (3,1) (2,2) (1,3) (0,4) )

Maybe I didnt explained quite well what my circle should look like. I will edit my question

Also the third argument in range() just means by how much you move between the min and max. If you ommit it, it defaults to 1.

---

The shape in your printscreen is no circle, it is just a square, except it is shifted diagonally :)
So You can still get normal square around You, and translate it by diagonal matrix.

https://en.wikipedia.org/wiki/Rotation_matrix

So all Yuo need to do it to multiply positions of tiles in range of square by this 2d matrix using 45deg as an angle. ( You need to translate it to radians though )

---

Thanks! Involving a transformation matrix is neat idea! It seems though, that at the end of the day, there is no "simple" 2 or 3 lines code to do it. My main concern was, if I was missing a really obvious way to do it (since I will be writing much more of similar code).

Answer 2

I don't know a lot about tiles, I don't know much about building a tactics game either, but I do work on building 2D/2.5D RTS games primarily and I use Geometry a lot.

Geometry:

https://docs.godotengine.org/en/stable/classes/class_geometry.html

https://docs.godotengine.org/en/stable/classes/class_tileset.html#class-tileset-method-tile-set-shape

https://docs.godotengine.org/en/stable/classes/class_geometry.html#class-geometry-method-is-point-in-circle

This guy does a good intro for that class:

https://www.youtube.com/watch?v=mRixyMUr5VM @2:05 He talks about intersection.

So, you could just have or add two child shapes or polygons to the starting Vector2 and set a shape for your tiles, then you'd find the tiles' shapes that share points contained by the larger ( max range), but not the smaller of the two (min range).

I'm sure there's even better ways to do the using direct space state and ray casting, but I'm still a novice here.

Comments

Thanks! Since I am working in a more "logic" oriented way of dealing with the grid (you could in principle play the game without visuals). I am not using any kind of polygon or shape, its just data inside a JSON type object.

Still, didnt know about the geometry class so thanks for introducing it to me. It seems quite powerfull!

---

Well, you could probably write a function using some combination of get_distance_to(), clamp(), wrapf(), etc. I can think of a number of ways to solve this or , as you said, de-"bloat" your current implementation. However, without knowing the elements and the implementation you're using (along with my insufficient understanding of tiles/tilesets, I wouldn't know which to suggest.