I am developing a game where the top left corner of the world is coordinate 0:0. Thus, x is increasing while moving right and y down.

I am trying to come up with an algorithm that finds the coordinates of the tiles within the given circle.

The method signature could look like this:

ArrayOfCoordinates findCoords(int centerX, int centerY, int radius)

Example, if radius is set to 1, it would search something like this:

[attachment=28925:pic1.jpg]

If it is 2:

[attachment=28926:pic2.jpg]

And 3:

[attachment=28927:pic3.jpg]

4:

[attachment=28928:pic4.jpg]

And so on.

You could do a breadth first search for all available nodes to depth N, just make sure you remove diagonal tiles from the adjacency lists. For example:

ArrayOfNeighbors getNeighbors(int x, int y)
{
    return Array(Coord(x + 1, y), Coord(x - 1, y), Coord(x, y + 1), Coord(x, y - 1));
}

ArrayOfCoordinates findCoords(int centerX, int centerY, int radius)
{
    ArrayOfCoordinates arr;
    QueueOfCoordinates frontier;


    frontier.add(coord(centerX, centerY));

    int i = 0;
    while (!frontier.empty() && i++ < radius)
    {
        Coord coord= frontier.dequeue();
        if (cord not in arr)
            arr.add(coord);
        foreach (adjacentNode to coord) // Use getNeighbors or getUniqueNeighbors(ones not seen in arr)
            frontier.enqueue(adjacentNode);
    }

    return arr;
}

I'm sure the above is wrong, syntactically, in some way. But I hope it's a clear example, do a bfs up until depth radius. You'd likely want to use a set or something for what you have seen and use a variant of getNeighbors like getUniqueNeighbors to find all neighbors that aren't in your array.

From the center, move N tiles to the right. That is your first point (x, y) = (N, 0). Mirror it to the other axes.

Next, move 1 up, and compute distance(x, y+1). If it is less or equal to N (but see note below), it's the next point.

The other option is that the distance is too large. In that case, move x a single tile to the left (ie to (x-1, y+1)).

Each new point can be mirrorred to 7 other positions at the circle.

Move another line up, etc, until x < y (ie you moved beyond 45 degrees). At that moment, you're done.

Note: Circles look a lot better if you allow rounding down the distance, that is, distance(x, y) must be < N + 0.5

I have been thinking about a square grid with every other row offset half the wdith of one square. This acts the same as a hex grid but may be easier to work with. Sorry, I do not have really good pictures to put up....

[attachment=28937:grid with circle.JPG]

The circle is close to having the center at 4,4 (did it by eye)

example: center of square 4,4 to square 2,2. the radius mathematically using 4,4 as the center is aprox 2.828. Counting spaces directly from one point to the other is the count is 3 . It should not be all that difficult to work up an algorithim that would count the spaces mathematically.

Taking at look at the 2nd picture - all of the green asterisks are a 3 count from the red 4,4 square.

[attachment=28938:grid with circle 2.JPG]

This is much closer to a true circle then a square grid.

Thanks for the help. Tried some of the suggestions noted here, such as the link to Midpoint Circle Algorithm. While they work, they dont find the coordinates inside the circle. Ie they dont fill search.

Thanks for the help. Tried some of the suggestions noted here, such as the link to Midpoint Circle Algorithm. While they work, they dont find the coordinates inside the circle. Ie they dont fill search.

Not sure I understand the problem correctly, but this is a pretty trivial application of pythagoras' theorem?

The radius is the hypothenuse in a rectangular triangle. A point is inside a circle with a given radius, if its distance from the center is equal or less than the radius. These two are pretty obvious.

The radius can thus be decomposed into an x and y coordinate where its length can be calculated according to pythagoras' formula. Or, more easily and computionally more efficient, its square can be calculated from the same formula without the square root. That's a common optimization.

Thus, for all points that are inside a circle, (dx*dx + dy*dy) <= r*r must be true (where dx is the point's x coordinate subtracted from the center). In the easiest unoptimized case, you just iterate over every single cell and check its midpoint coordinate accordingly. It's either true (inside) or false (not inside).

Further, a circle with a given diameter lies completely within a square whose sides are the length of the diameter. You can therefore optimize the search by only iterating over the cells that are in the (midpoint.x - x ... midpoint.x +x) and (midpoint.y -y ... midpoint.y+y) range.

So... in pseudo-C code, something like...

rr = radius*radius;

for(x = center.x - radius; x <= center.x + radius; ++x)

for(y = center.y - radius; y <= center.y + radius; ++y)

{

dx = center.x -x;

dy = center.y -y;

if((dx*dx + dy*dy) < rr)

point_inside(x, y);

}

Yeah, this wasn't so hard as I expected.

samoth: I found something very similar. The performance is ok I guess. Took 1.768828 milliseconds when the radius was 20, in Java. Complete code for future reference:

	public Set<Vector2> searchTiles(int x, int y, int r) {
	    Set<Vector2> points = new HashSet<>();
	    for (int j=x-r; j<=x+r; j++)
	        for (int k=y-r; k<=y+r; k++)
	            if (distance(new Vector2(j,k), new Vector2(x,y)) <= r) 
	            	points.add(new Vector2(j,k));

		return points;
	}