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

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

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

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

  1. Определить трехмерный массив (массив) (размер: MAX_CHUNKS_X, MAX_CHUNKS_Y, MAX_CHUNKS_Z)
  2. Заполните 3D массив с ЛОЖЬ
  3. При прохождении из списка фрагментов проверяется, находится ли фрагмент внутри диапазона видимости
  4. если внутри установленного массива [chunk_x] [chunk_y] [chunk_z] = true;
  5. После прохождения списка начинаются басовые массивы
  6. Для всего массива [chunk_x] [chunk_y] [chunk_z] == false добавить к блоку 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 ()
Синий = далекий от ChunksLoadList.begin ()

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

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

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

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

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

0

Решение

Давайте сначала посмотрим на проблему сортировки расстояний, если ваш ChunksLoadList это std :: list, а не std :: vector или std :: array (C ++ 11), вы уже проиграли гонку производительности! Бьярне Страуструп: почему вы должны избегать связанных списков Обратите пристальное внимание на график !!!

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

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

O (C + K * N log log N) самый быстрый?

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

Для N -> бесконечность это становится O (N log log N)

НО для этой проблемы есть еще лучший алгоритм!
Заполнение Flood, сопровождаемое сортировкой вставки, заполнение Flood создает почти отсортированный список в O (N), а сортировка вставкой обеспечивает полностью упорядоченный список из частично упорядоченного в O (N) всего O (N) …

О (С + К * Н)

с ужасным постоянным временем подготовки, и ужасным для каждого элемента, но только N раз

вариант википедии

 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 байта, это уносит кэш в большинстве систем.

Как наводнение заполнить его не эффективно, но в качестве приближения к расстоянию это так.
Вы можете остановиться здесь, если ваши требования будут выполнены.
ЕСЛИ вам нужно общее количество заказов, а затем запустить сортировку вставки на почти отсортированный список O (N), но тогда вам также необходимо рассчитать расстояние до камеры.

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

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

Другие решения


По вопросам рекламы [email protected]