Куски загрузки и сортировки

Question

Я работаю над клоном minecraft, и у меня есть 2 проблемы с загрузкой куска.

Первый: определить куски для загрузки.

я нашел один способ это некрасиво, но работает быстро для меня

1. Определение 3d массива (массив) (размер: MAX_CHUNKS_X, MAX_CHUNKS_Y, MAX_CHUNKS_Z)
2. Заливка 3d массив с фальшивыми
3. При переходе от список блоков, проверяющих, есть ли внутри диапазона видения
4. если внутри массива набора [chunk_x] [chunk_y] [chunk_z] = true;
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 вступили в силу, как оставить на этой картинке https://www.dropbox.com/s/owjfaaekcj2m23w/58f2e4c8.png?dl=0 Красный = ближайший к ChunksLoadList.begin() Синий = Farest к ChunksLoadList.begin()

им пытаются использовать

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

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

Но это способ замедлить большие диапазоны видимости ... Как я должен переписать код для быстрого эффекта волновой нагрузки?

Извините меня ужасный английский, я надеюсь, что вы меня понимаете ...

Answer 1

Давайте сначала посмотрим на расстоянии сортировочной проблемы, если ваш ChunksLoadList является станд :: список и не станд :: вектор или станд :: array (C++ 11) вы уже потеряли гонку производительности! Bjarne Stroustrup: Why you should avoid Linked Lists Обратите внимание на график !!!

Если его все еще слишком медленно после того, как вы изменили его на std :: vector, вы можете попробовать «этот метод, который я только что придумал (TM)»!

Лучшие алгоритмы сортировки являются чем-то вроде

O (C + K * N журнал журнал N) fastest?

С ужасным С постоянной времени приготовительный, ужасный K на элемент и очень хороший N журнал журнал N

для N -> бесконечность это добирается, чтобы быть O (N журнал N журнал)

НО для этой проблемы есть еще лучший алгоритм!
Заполнение заливки, за которым следует сортировка вставки, заливка заливки производит сортированный список в O (N), а сортировка вставки сохраняет полностью упорядоченный список из частично упорядоченного в O (N) для всего O (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 байта, это удаляет кеш на большинстве систем.

Как наводнение, оно неэффективно, а как приближение к расстоянию.
Вы можете остановиться здесь, если ваши требования выполнены.
IF Вам необходимо всего упорядочить, а затем выполнить сортировку вставки на nearly sorted list O (N), но тогда вам также необходимо рассчитать расстояние между камерами.

потенциал дальнейшей оптимизации:

• непрозрачных вокселей не добавляет соседей, которые также являются непрозрачными.
• воздух (полностью прозрачный) не добавляется в список камер, но должен быть там для заполнения, в случае присутствия летающего острова.