find all of the positions in a sphere
That'll be as slow as treacle, since it involves 3 square root operations for every single check. I have no idea what your sphere radius is, but for a sphere of radius 10 chunks, that is 4188 chunks to be checked every single time you move. That is a lot of square roots = pretty costly!
use the neighbors of the chunks to do it i tried it and its even slower than the algorithm I was using
If they're topological neighbours, i.e. if every Chunk is linked by pointers or references to its neighbour Chunks, it very likely will also be slow as treacle with thousands of chunks in memory at once. The jumps could be large and you will wait potentially up to hundreds of cycles for any Chunks that are not in L1 cache, to be returned from main memory. Major pipeline stall!
I'm just wondering what is the go to algorithm
Approach 1: Cheap distance checks
Generally, we wouldn't use sphere checks to do this. Even a cylinder check (oriented up-down) is going to be a lot cheaper than a sphere check, since it involves only 1 square root distance check, instead of the 3 you're using for sphere distance checking. With a cylinder check you are checking within a circle around that player along the horizon plane, and then doing a simple up / down axis distance check which is cheap.
In fact, any distance check that is not an axis-aligned bounding box check is unwise. AABB checks generally look like this:
if (p >= min && p < max) then chunk is in range for this axis
However, if you must use something more like a circle or a cylinder, I suggest using the Manhattan Distance:
distance = dx + dy
for 3D that would obviously be
distance = dx + dy + dz
Manhattan distances create angular forms but are cheap to calculate, since addition is a very fast operation on any CPU.
Approach 2: No distance checks - dynamic chunk regeneration
So here what we do is we don't pull anything back from main memory or disk. Instead we regenerate every chunk from scratch. Every chunk has it's own unique ID based on a combination of:
- the chunk's unique x, y, z position in the world
- (optionally) some unique world seed value
This ID is basically a chunk-seed, and it used to regenerate the chunk as you cross certain world row / column boundaries.
Of course, this data can be placed into reusable chunks that you have allocated once off at runtime - as you are already doing.
So all you are doing here is:
- grab player position
p
- get your maximum viewing distance and divide it by half, in each axis =
h
- start from
p - h, and run to p + h, in each axis, generating the chunks
- render each chunk you have just generated.
EDIT: After comments
You are checking every chunk against every other chunk at startup - this is logically incorrect and very slow - we call this O(n^2) ("big-o n-squared").
You need to do something along these lines...
//Get position of chunk player is in:
xChunkPlayer = xWorldPlayer / 24;
yChunkPlayer = yWorldPlayer / 24;
zChunkPlayer = zWorldPlayer / 24;
//Get player chunk - you will do any checks (if required) only against this.
Chunk playerChunk = ... //some means of retrieval
//Let's say the width of your cube of interest is 20, so half that is 10.
//Use this number to get the other chunks' positions by running through
//the cubic space centred around the player's current chunk.
for (int zChunk = zChunkPlayer - 10; zChunk < zChunkPlayer + 10; zChunkPlayer++)
for (int yChunk = yChunkPlayer - 10; yChunk < yChunkPlayer + 10; zChunkPlayer++)
for (int xChunk = xChunkPlayer - 10; xChunk < xChunkPlayer + 10; xChunkPlayer++)
{
//TODO get the chunk using xChunk, yChunk, zChunk or derivatives thereof which are local to the player
//TODO do what you need with the chunk, e.g. change or render it or test it against player chunk
}
