大块加载和排序

Question

我工作在Minecraft的克隆，我有2个块加载问题。

第一：确定要加载的块。

我找到一个方式，它的丑陋，但工程快给我

1. 定义3D阵列（阵列）（尺寸：MAX_CHUNKS_X，MAX_CHUNKS_Y，MAX_CHUNKS_Z）
2. 填写3D阵列FALSE
3. 虽然从通过如果在设置数组[chunk_x] [chunk_y] [chunk_z] = true时，检查块是否位于视觉范围内的块的列表
4. ;
5. 通过列表开始bassing阵列
6. 对于所有的阵列[chunk_x] [chunk_y] [chunk_z] ==虚假加入LoadingList块在后chunk_x chunk_y chunk_z

另一种方式来少丑陋，还快？

代码：

 ChunksRenderList.clear(); 
    CChunk* Chunk = NULL; 

    s32 RootChunk_X_Location = (floor(RenderCenter.x)/CHUNK_SIZE); 
    s32 RootChunk_Y_Location = (floor(RenderCenter.y)/CHUNK_SIZE); 
    s32 RootChunk_Z_Location = (floor(RenderCenter.z)/CHUNK_SIZE); 

    if(RenderCenter.x < 0) 
     RootChunk_X_Location--; 

    if(RenderCenter.y < 0) 
     RootChunk_Y_Location--; 

    if(RenderCenter.z < 0) 
     RootChunk_Z_Location--; 

    core::vector3s RootChunkLocation(RootChunk_X_Location,RootChunk_Y_Location,RootChunk_Z_Location); 

    u32 XZ_ArraySide = (RenderDistance_XZ*2)+1; 
    u32 Y_ArraySide = (RenderDistance_Y*2)+1; 
    char array[XZ_ArraySide][Y_ArraySide][XZ_ArraySide]; 

    memset(array,0,(XZ_ArraySide*XZ_ArraySide*Y_ArraySide)); 

    for(auto it = Chunks.begin(); it != Chunks.end(); it++) 
    { 
     Chunk = (it->second); 

     if(Chunk->Locked) 
      continue; 

     if(Chunk->KeepAliveCounter <= 0) 
     { 
      ChunksUnloadList.push_back(Chunk); 
      continue; 
     } 
     else 
     { 
      Chunk->KeepAliveCounter -= WORLD_UPDATE_PERIOD; 
      Chunk->DistanceToCamera = RenderCenter.distance_to(Chunk->ChunkAbsolutePosition); 
     } 

     if(Chunk->ChunkPosition.x >= (RootChunk_X_Location - (s32)RenderDistance_XZ) && Chunk->ChunkPosition.x <= (RootChunk_X_Location + (s32)RenderDistance_XZ)) 
      if(Chunk->ChunkPosition.y >= (RootChunk_Y_Location - (s32)RenderDistance_Y) && Chunk->ChunkPosition.y <= (RootChunk_Y_Location + (s32)RenderDistance_Y)) 
       if(Chunk->ChunkPosition.z >= (RootChunk_Z_Location - (s32)RenderDistance_XZ) && Chunk->ChunkPosition.z <= (RootChunk_Z_Location + (s32)RenderDistance_XZ)) 
       { 
        s32 PositionInMatrix_X = Chunk->ChunkPosition.x - (RootChunk_X_Location - (s32)RenderDistance_XZ); 
        s32 PositionInMatrix_Y = Chunk->ChunkPosition.y - (RootChunk_Y_Location - (s32)RenderDistance_Y); 
        s32 PositionInMatrix_Z = Chunk->ChunkPosition.z - (RootChunk_Z_Location - (s32)RenderDistance_XZ); 

        array[PositionInMatrix_X][PositionInMatrix_Y][PositionInMatrix_Z] = true; 

        Chunk->KeepAliveCounter = CHUNK_LIVE_TIME; 
       } 


     if(not Chunk->NeightboarsUpdated) 
     { 
      ChunksNeightboarUpdateList.push_back(Chunk); 
     } 

     if(not Chunk->ChunkUpdated) 
     { 
      ChunksRebuildList.push_back(Chunk); 
     } 
     if(not Chunk->Locked and Chunk->VisibleBlocks > 0) 
     { 
      ChunksRenderList.push_back(Chunk); 
     } 

    } 

    for(u32 y = 0; y < Y_ArraySide; y++) 
     for(u32 x = 0; x < XZ_ArraySide; x++) 
      for(u32 z = 0; z < XZ_ArraySide; z++) 
      { 
       s32 ChunkPosition_X = (s32)x + (RootChunk_X_Location - (s32)RenderDistance_XZ); 
       s32 ChunkPosition_Y = (s32)y + (RootChunk_Y_Location - (s32)RenderDistance_Y); 
       s32 ChunkPosition_Z = (s32)z + (RootChunk_Z_Location - (s32)RenderDistance_XZ); 

       if(array[x][y][z] == 0) 
       { 

    SPendingToLoad ToLoad; 
        ToLoad.Position.set(ChunkPosition_X,ChunkPosition_Y,ChunkPosition_Z); 
        ToLoad.DistanceToCamera = ToLoad.Position.distance_to_sqr(RootChunkLocation); 
        ChunksLoadList.push_back(ToLoad); 
       } 
      } 

二： 如何排序ChunksLoadList生效喜欢留在这个PIC https://www.dropbox.com/s/owjfaaekcj2m23w/58f2e4c8.png?dl=0 红色=最近ChunksLoadList.begin（） 蓝= farest到ChunksLoadList.begin（）

IM尝试使用

ChunksLoadList.sort([&RootChunkLocation](SPendingToLoad& i,SPendingToLoad& j) 
    { 

     return i.DistanceToCamera < j.DistanceToCamera; 
    } 
    ); 

但它的方法，以减缓大视野范围... 我该如何重写代码才能获得快速波动加载效果？

对不起我的可怕的英语，我希望你能理解我......

Answer 1

让远处的排序问题先看看，如果你的ChunksLoadList是一个std ::列表，而不是一个std ::向量或std ::数组（C++ 11）已经失去了性能竞赛！ Bjarne Stroustrup: Why you should avoid Linked Lists密切关注图!!!

如果在将其更改为std :: vector后仍然过于缓慢，则可以尝试“我刚发明的这种方法（TM）”！

最好排序算法是类似

O（C + K * N日志日志N）fastest?

随着可怕的恒定的准备时间，每个元素可怕K和极好的N日志为log N

对于N - >无穷此获取要O（N loglogN个）

BUT这个问题有一个更好的算法！
填充填充后跟插入排序，填充填充产生O（N）中接近排序的列表，并且插入排序从O（N）中的部分排序中总共排列O（N）来确保完全排序的列表。 ..

O（C + K * N）

具有可怕恒定的准备时间，和每元素，但一个可怕的仅N次

variant of wikipedia

Flood-fill (node, target-color, replacement-color): 

If target-color is equal to replacement-color, return. 
Set Q to the empty queue. [must be std::vector or std::array or this will fail] 
Add camera node to the end of Q. 
While Q is not empty: 
    Set n equal to the *first* element of Q. 
    Remove *first* element from Q. 
    If the color of n is equal to target-color: 
     Add n to the distance list as the next closed (this will be nearly correct) 
     Set the color of n to replacement-color and mark "n" as processed. 
     Add adjacent nodes to end of Q if they has not been processed yet. (x/y/z +1/-1) 
Return. 

队列元素是x，y，z
使用std :: dequeue

距离列表必须也是一个随机访问包含，它是从大小开始（viewdistance * 2 + 1）^ 3完全分配的，可能很大。
如果视图距离100是201^3 =〜80000000个体素，你真的想要这个吗？如果你需要一些信息，你必须有一些指针或索引，至少有4个字节，这会在大多数系统上使用缓存。

由于洪水填补其无效，但作为近似距离它是。
如果您的要求得到满足，您可以在此停止。
如果您需要总订购，然后在nearly sorted list O（N）上运行插入排序，但是您还需要计算相机距离。

潜力进一步优化：

• 不透明体素不添加邻居也都是不透明的。
• 空气（完全透明）不会添加到相机列表中，但需要在那里进行填充，以防飞行岛出现。