Jump to content
  • Advertisement
Sign in to follow this  
P0jahn

Find tile coordinates within a given radius

This topic is 1146 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
Advertisement

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!