Я работаю над клоном Minecraft, и у меня есть 2 проблемы с загрузкой чанка.
Первый: определить куски, которые будут загружены.
я нашел один способ, это уродливо, но работает быстро для меня
Еще один способ менее уродливый и все еще быстрый?
Код:
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;
}
);
Но это метод замедления для больших дальностей видения …
Как я должен переписать код, чтобы получить быстрый эффект загрузки волны?
Извини меня, ужасный английский, надеюсь, ты меня понимаешь …
Давайте сначала посмотрим на проблему сортировки расстояний, если ваш 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), но тогда вам также необходимо рассчитать расстояние до камеры.
Потенциал дальнейшей оптимизации: