# How to get chunks in a sphere rather than cuboid

Chunks are stored in a dictionary with the key being a struct consisting of x,y,z integer coordinates. Available data are:

• Real position of the player
• Current chunk of the player
• Center point and size of each chunk (same size for all)
• I know when the player steps into another chunk

A quick calculation revealed that if I'd be able to load chunks spherically instead of cubically, I would be able to load ~40% less chunks. The amount of chunks I have to grab (currently) can vary, ranging from a range of 3 to ~8 (meaning minimum of (2*3+1) 7*7*7=343 to (2*8+1) 17*17*17=4913). Current Code:

    public Chunk[,,] GetChunksInCuboid (Coordinate coords, int range)
{
return GetChunksInRectangle (new Coordinate (coords.x - range, coords.y - range, coords.z - range), new Coordinate (coords.x + range, coords.y + range, coords.z + range));
}

public Chunk[,,] GetChunksInCuboid (Coordinate min, Coordinate max)
{
int xLen = max.x - min.x + 1;
int yLen = max.y - min.y + 1;
int zLen = max.z - min.z + 1;

Chunk[,,] A = new Chunk[xLen, yLen, zLen];

for (int x = 0; x < xLen; x++)
{
for (int y = 0; y < yLen; y++)
{
for (int z = 0; z < zLen; z++)
{
A[x, y, z] = GetChunk (x + min.x, y + min.y, z + min.z);
}
}
}

return A;
}


My question is the following: Is it possible, and if yes, how can I performantly load chunks in a sphere?

Once I faced this particular problem. My approach was to make the code dumber.

I hard baked the precomputed offsets for different load distances. And then I would just go over them, and add the offset to the coordinates of current chunk where the player is located. I had not to worry about any distance check because the offsets were precomputed for that.

I think we can do better, actually. If we know that all the chunks near the last position of the player loaded, we only need to load the chunks that are near the new position that were not near the old position. We could have precomputed offsets for those sections.

I suggest to use code generation for that.

Now, while I wrote the question I had an idea and the solution was actually simple. But I thought I'd still throw it up here in case someone has a similar challenge. Be reminded, I selected the most optimal data structures - but if you find something to improve here, feel free to inform me!

The solution is: Get all chunks in a rectangle as described in the question, but filter them based on their 'coordinate' distance. Here is a SE answer to how to calculate distance in a 3D sphere. One additional optimization comes from not applying square root to the distance, but just comparing the distance by using their "squared" form.

Meaning: If a² > b² then |a| > |b|.
Concluding: If a > b and a > 0 and b > 0, then a^n > b^n with n >= 1.
By not square rooting the distance, you can save one relatively cost heavy computation for every chunk's distance check.

    public Chunk[,,] GetChunksInSphere (Coordinate coords, int range, float radius)
{
Coordinate min = new Coordinate (coords.x - range, coords.y - range, coords.z - range);
Coordinate max = new Coordinate (coords.x + range, coords.y + range, coords.z + range);

int xLen = max.x - min.x + 1;
int yLen = max.y - min.y + 1;
int zLen = max.z - min.z + 1;
float r = radius / (float) ChunkSize;
float sqRadius = r * r;

Chunk[,,] A = new Chunk[xLen, yLen, zLen];

for (int x = 0; x < xLen; x++)
{
for (int y = 0; y < yLen; y++)
{
for (int z = 0; z < zLen; z++)
{
Coordinate c = new Coordinate (x + min.x, y + min.y, z + min.z);
if (Coordinate.RealSquareDistance (coords, c) <= sqRadius) A[x, y, z] = GetChunk (c);
}
}
}

return A; // Beware that the array will be filled will 'null's!
}


The formulas for getting the distance in the Coordinate struct:

    /// <summary> More performant for comparing distances. </summary>
public static double RealSquareDistance (Coordinate a, Coordinate b)
{
int xDis = a.x - b.x;
int yDis = a.y - b.y;
int zDis = a.z - b.z;
return xDis * xDis + yDis * yDis + zDis * zDis;
}

public static double RealDistance (Coordinate a, Coordinate b)
{
int xDis = a.x - b.x;
int yDis = a.y - b.y;
int zDis = a.z - b.z;
return Math.Sqrt (xDis * xDis + yDis * yDis + zDis * zDis);
}


These will return the distance in "Coordinate" size. For checking the distance with real ranges, simply divide it with your chunk size.

## Result

This optimization cut computation time almost in half and it reduced the cached stars
from ~2000 to ~70 - which means we got a ~40% performance increase and ~95% less data to cache (depends on chunk size, bigger chunks have more to store). Further improvements to performance come by having to check much less cached data (the cached stars are expected to be manifested as GameObjects at any time).

This is because all chunks at the edges between the loading range distance sphere and the cube around it, which had previously loaded 0 stars and just cached everything, were no longer being loaded. The only cached stars now are those which are just outside the loading range sphere, but still inside the loaded chunks on the edges.

I was quite surprised about the result, but it all makes sense.

• You can reduce your range of iteration so you never even visit the corners of the cuboid, using a 3D analogue of the trick shown here. You'd walk through each plane from the top of the sphere down, and for each plane calculate the radius of the disc intersecting that plane. Then walk through that disc from front to back, in each row calculating the left and rightmost extents of the disc in that row. Then you can get every chunk in that range, with no further checks. You do fewer distance calcs for large spheres this way. Feb 1 '20 at 14:15
• @DMGregory - Ah yes, that might be exactly what I was hoping to find all along! Thank you. Feb 2 '20 at 8:23