大塊加載和排序

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）上運行插入排序，但是您還需要計算相機距離。

潛力進一步優化：

• 不透明體素不添加鄰居也都是不透明的。
• 空氣（完全透明）不會添加到相機列表中，但需要在那裏進行填充，以防飛行島出現。