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

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Pomelo

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)

:bust_in_silhouette: Reply From: Inces

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)

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.

Pomelo | 2022-06-07 20:06

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

Rotation matrix - Wikipedia

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 )

Inces | 2022-06-08 08:32

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).

Pomelo | 2022-06-10 15:46

:bust_in_silhouette: Reply From: CassanovaWong

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_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.

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!

Pomelo | 2022-06-08 00:29

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.

CassanovaWong | 2022-06-08 01:42