2
\$\begingroup\$

I'm having trouble speeding up where I initialise positions for reused / pooled chunks. I found that where I calculate the positions of neighbor chunks, it's even slower than the algorithm I was using, which was just to find all of the positions in a sphere and subtract all of the active chunk positions from it then use the leftover positions for the new chunks. I'm wondering what is the go-to algorithm to do this quickly? I'm dealing with thousands of chunks. Just needs to be faster as it's currently terribly slow.

I have 3d chunks in a vector that contains each position in the world (i.e. not relative to the player position) and these have to be made relative to the player position then, multiplied by chunk size (right now 24) to get the player/camera-relative render position.

\$\endgroup\$
6
  • \$\begingroup\$ Depends VERY much on how you've implemented your system, which you don't talk much about. (I would suggest doing so, or it's going to be difficult to get an accurate answer.) I deduce from your sphere checks that your world has chunks running in 3 dimensions rather than just 2D? \$\endgroup\$
    – Engineer
    May 30 at 22:00
  • 1
    \$\begingroup\$ i just edited it with a few more details what details do you suggest adding \$\endgroup\$
    – Austin128
    May 30 at 22:05
  • 1
    \$\begingroup\$ Reopened! I'm sorry I didn't see anything about someone working on an answer. That's my fault since I'm new to the mod interface. :) \$\endgroup\$
    – Almo
    May 30 at 22:10
  • 1
    \$\begingroup\$ @Almo No worries! Thanks. \$\endgroup\$
    – Engineer
    May 30 at 22:10
  • 1
    \$\begingroup\$ FWIW, we don't see when someone is working on an answer, we get notified only when the answer is posted. \$\endgroup\$
    – Vaillancourt
    May 30 at 22:12
1
\$\begingroup\$

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
         }
\$\endgroup\$
12
  • \$\begingroup\$ well for getting all positions in a sphere i go through a aabb and check if they're in the sphere without a sqrt because i can just check it with distance squared instead of distance so its not horridly slow \$\endgroup\$
    – Austin128
    May 30 at 22:22
  • \$\begingroup\$ @Austin128, right, and for a radius 10 i.e. diameter 20 box, that's 20*20*20 = 8000 checks or 16000 conditionals. You're doing this, what, once per frame? \$\endgroup\$
    – Engineer
    May 30 at 22:23
  • \$\begingroup\$ no just once just as fast as it can go its in another thread but since its so slow it takes forever to load the chunks \$\endgroup\$
    – Austin128
    May 30 at 22:25
  • \$\begingroup\$ the initial bunch of checks is fine but when i have to check that check against all the other chunks is where the problem lies \$\endgroup\$
    – Austin128
    May 30 at 22:27
  • 1
    \$\begingroup\$ yeah im really bad at figuring out how to do this mainly with the sphere subtracting based approach i have to go through all of the positions in the sphere for every chunk to do the subtracting and the neighbor method i have to check the chunks that have neighbor that don't exist in the render area and check all the other chunks then to find if i have a chunk thats already active there \$\endgroup\$
    – Austin128
    May 30 at 22:33
0
\$\begingroup\$

ok my answer was to just make a 3d array of chunks it is way faster now because an access to the chunks is O(1) pretty much its still a bit buggy though right now but ill figure that out

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.