(Scripting) Getting a circle of points in an array

Questions & Answers
1

Lets say you have a double array of any data type. You are given an x and y value, that represents a single value in this array, such as map[x,y]. Now, you want to do something to not only that point in the array, but to the points around in it in a circle.

There are several way I have achieved this, but none as quite good enough. The first method was to just loop through every value in the array and check if its distance from the center point was lower than a given value, if so, it was in the circle. However, the scale of the array that this is in is around 500x500, and I’d like to make that even bigger if I can. The issue is that 500x500 is 250,000. Looping through that and applying functions is death to my game, but has to be done somehow.

I have created a better method that runs only through the local points, by basically looping through a small square of width and height same as the diameter of the circle, which is 999x faster than before. Ex:

void Circle(int x, int y, int radius)
{
    Vector2 center = new Vector2(x,y);
    for (int i = x-radius; i < x+radius; i++)
    {
        for (int j = y-radius; j < y+radius; j++)
        {
            if (Vector2.Distance(center, new Vector2(i,j)) <= radius)
            {
                //Do Stuff
            }
        }
    }
}

This will be done a lot, so even little improvements make a big difference. What I’m looking for is a way that doesn’t loop through a square and compare distances, but instead produces all points in the circle directly. I’m not sure how it would be done, but I think it might be possible, and then would likely be more efficient.

2

Well, if the radius is constant you can in deed create a list of all points that make up a circle since your center is made up by a whole number. It would be best to create an int version of a 2d vector:

public struct Vector2i
{
    public int x;
    public int y;
    public Vector2i(int aX, int aY)
    {
        x = aX; y = aY;
    }
}

Now just use a generic list and prepare your points:

List<Vector2i> offsets = new List<Vector2i>();
int threshold = radius * radius;
for (int i = -radius; i < radius; i++)
{
    for (int j = -radius; j < radius; j++)
    {
        if (i*i + j*j <threshold)
            offsets.Add(new Vector2i(i,j));
    }
}

Btw: since each quadrant of a circle is equal, just flipped on x, y or both axis you could even do:

offsets.Add(new Vector3i(0,0));
for (int i = 1; i < radius; i++)
{
    for (int j = 1; j < radius; j++)
    {
        if (i*i + j*j <threshold)
        {
            offsets.Add(new Vector2i(i,j));
            offsets.Add(new Vector2i(-i,j));
            offsets.Add(new Vector2i(i,-j));
            offsets.Add(new Vector2i(-i,-j));
        }
    }
}

Though there shouldn’t be much difference. The best performance gain is to avoid unnecessary method calls inside your loops. If you can you should inline as much as possible. That’s best to avoid cachemisses. For that matter of fact it might even be faster to do:

offsets.Add(new Vector3i(0,0));
Vector2i vec = new Vector2i();
for (int i = 1; i < radius; i++)
{
    vec.x = i;
    for (int j = 1; j < radius; j++)
    {
        if (i*i + j*j <threshold)
        {
            vec.y = j;
            offsets.Add(vec); vec.x = -vec.x; // i,j
            offsets.Add(vec); vec.y = -vec.y; // -i,j
            offsets.Add(vec); vec.x = -vec.x; // -i,-j
            offsets.Add(vec);                 // i,-j
        }
    }
}

Though since you do this only once and then use the offsets list directly that shouldn’t make a huge difference ^^.