Sign in to follow this  

Find tile coordinates within a given radius

This topic is 835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites

The images you listed could very well be a diamond pattern -- where abs(deltax) + abs(deltay) should never exceed the given radius, where deltax and deltay is distance from origin.

 

For more "proper" circles, you might want to have a look at https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Share this post


Link to post
Share on other sites

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.

Edited by DishSoap

Share this post


Link to post
Share on other sites

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

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

I just iterate over all tiles in an AABB that contains the shape, and for each tile do a containment check and only then apply the operation (I use c++ lambda for the operation, passed to the iteration function).

 

Its more costly than specialized algorithms (iterating extra tiles, doing containment check for all the tiles including skipped ones), but its hopefully cache efficient and much easier to modify for different use cases.

 

At least have a basic AABB/box iteration function around, even if you do create special cases for some things.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.


For each row of tile found with the algorithm, the tile coordinates will be between the two found values. In other words, if the midpoint algorithm selects tiles 5 and 10 in row x, the tile coordinates for that row within the circle are (5,x), (6,x), (7,x), (8,x), (9,x), (10,x).

Share this post


Link to post
Share on other sites

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

     }

Edited by samoth

Share this post


Link to post
Share on other sites

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;
	}
Edited by P0jahn

Share this post


Link to post
Share on other sites
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:

I personally find almost 2 milliseconds is an awful lot. While Java isn't the fastest language in the world, still two milliseconds is an eternity for something so simple.

On the other hand, if you only need to do this once in a while (like, once each time a grenade explodes), it probably makes no difference and it's not worth worrying..

 

Note the distance-squared optimization that I wrote about and that Mussi pointed out as well.

 

However, I think that that creating (and then leaking, so the GC has to collect them) all those Vector2 temporaries only for calculating the distance is probably more overhead than doing a square root. Yes, this is how you do Java, but creating and recycling all those objects needlessly is not alltogether free.

Of course, it's also very comfortable, and explicit, to dynamically create those Vector2 objects and call the distance function, and toss the objects away. But calculating a distance (or rather, a squared distance) is so trivial that you could really just do it by hand on the coordinates, without these temporaries. If you have a radius of 20, you allocate and free 1,600 objects to no avail. That doesn't sound like a lot per se, but it's unnecessary and it all adds up (with the stuff in the following paragraph, too).

 

I would also rather not use a HashSet to store the points that are found to be in the circle, since you are actually only interested in a contiguous list to which you can push your points and which you can iterate over afterwards (so you can draw red squares, or apply damage to units within each cell, etc) in the most efficient manner possible.

 

This is best represented by a Vector. Other than a HashSet, a Vector does not need to compute a hash (obviously), it does not provide the guarantee that each element exists only once (so, it doesn't need to perform that check for a guarantee that you don't need), doesn't have any other of the underlying implementation's (HashMap) special gimmicks such as null values, and it does not have issues with hash collisions (which, in the current implementation of HashMap that uses chaining means traversing linked lists!).

Edited by samoth

Share this post


Link to post
Share on other sites

Added the optimisations suggested here and got it down to 1 ms(radius 20). As samoth mentioned, this is going to be calculated when ever a major bomb explodes, so it is far from every frame. I can live with it.

Share this post


Link to post
Share on other sites

This topic is 835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this