Voxel-based chunk manager

Question

I'm creating a voxel-based game and have been working on it for quite a while.

I've come to a point where I have to load and unload chunks on the fly. I've created a chunk manager class and it's working, but it's quite slow and I would like to improve its speed.

Header file:

#pragma once
#include <d3d11.h>
#include <vector>
#include <unordered_map>
#include <thread>
#include "Chunk.h"
#include "Renderer.h"
#include "Noise.h"
#define WORLD_HEIGHT 4
#define SEED 5000
#define WATER_LEVEL 128
#define MAX_HEIGHT 256
#define BLOCK_BIOME_WEIGHT 1 //less is havier
#define BIOME_MIN 1.4
#define BIOME_MAX 0.7
using namespace std;
class Chunk;
class ChunkManager
{
public:
 ChunkManager(void);
 Chunk* getChunkAt(int x, int y, int z);
 void render(Renderer& renderer);
 void initialize(Camera& camera);
 void rebuild(double delta, Renderer& renderer);
 void update(double delta, Camera& camera, vector<XMFLOAT4>& frustumPlanes);
 float getWorldHeight(int x, int y);//TODO: Create new world class and add world related methods there
public:
 bool centerLoaded;
private:
 int renderDistance;
 int oldChunkX, oldChunkY, oldChunkZ;
 float oldCamYaw, oldCamPitch;
 unordered_map<string, Chunk*> loadedChunks;
 vector<Chunk*> rebuildChunks;
 vector<Chunk*> removableChunks;
 vector<Chunk*> renderChunks;
 vector<Chunk*> visibleChunks;
 double timer, timer2, removeTimer, tickTimer;
 vector<Noise*> noises;
private:
 void addChunks(int x, int z);
 void cullAABB(vector<XMFLOAT4>& frustumPlanes);
 void loadChunks(vector<Chunk*>& tempChunks, int& chunkX, int& chunkZ);
};

Class:

#include "ChunkManager.h"
ChunkManager::ChunkManager() {
 renderDistance = 8;//[5, 6, 7, 8, 12, 13, 14, 15, 20, 22]
 centerLoaded = false;
 timer = 0;
 timer2 = 0;
 tickTimer = 0;
 removeTimer = 0;
 srand(SEED);
 noises.push_back(new Noise(0, 0, 0, rand()));
 noises.push_back(new Noise(1, 0, 0, rand()));
 noises.push_back(new Noise(2, 0, 0, rand()));
}
float ChunkManager::getWorldHeight(int x, int z){
 return (noises[0]->getNoise(x, z) + (noises[1]->getNoise(x, z) * noises[2]->getNoise(x, z))) * 64 + WATER_LEVEL;
}
void ChunkManager::addChunks(int x, int z){
 for(int y = 0; y < WORLD_HEIGHT; y++){
 Chunk* chunk = new Chunk(this, x, y, z);
 rebuildChunks.push_back(chunk);
 string s = to_string(x) + "," + to_string(y) + "," + to_string(z);
 loadedChunks.emplace(s, chunk);
 }
}
Chunk* ChunkManager::getChunkAt(int x, int y, int z){
 string s = to_string(x) + "," + to_string(y) + "," + to_string(z);
 auto& it = loadedChunks.find(s);
 if(it != loadedChunks.end()){
 return it->second;
 }
 return NULL;
}
void ChunkManager::render(Renderer& renderer){
 for(int i = 0; i < visibleChunks.size(); i++){
 visibleChunks[i]->render(renderer);
 }
}
void ChunkManager::initialize(Camera& camera){
 int x = rand() % 48;
 int z = rand() % 48;
 int y = WATER_LEVEL;
 int checks = 1000;
 while(y <= WATER_LEVEL){
 x = rand() % 48;
 z = rand() % 48;
 y = getWorldHeight(x, z);
 checks--;
 if(checks == 0){
 throw std::invalid_argument("Too many checks !");
 }
 }
 int centerX = oldChunkX = floor(x / CHUNK_SIZE);
 int centerZ = oldChunkZ = floor(z / CHUNK_SIZE);
 for(int cx = -renderDistance-1; cx <= renderDistance+1; cx++){
 for(int cz = -renderDistance-1; cz <= renderDistance+1; cz++){
 addChunks(cx + centerX, cz + centerZ);
 }
 }
 camera.setPosition(BLOCK_RENDER_SIZE * x + BLOCK_RENDER_SIZE / 2, BLOCK_RENDER_SIZE * y + BLOCK_RENDER_SIZE * 2, BLOCK_RENDER_SIZE * z + BLOCK_RENDER_SIZE / 2);
}
void ChunkManager::rebuild(double delta, Renderer& renderer){
 if(!removableChunks.empty()){//TODO: THREADED
 if(removeTimer >= 0.01){
 removeTimer= 0;
 Chunk* c = removableChunks.back();
 delete c;//very slow
 removableChunks.pop_back();
 }
 removeTimer+=delta;
 }else{
 removeTimer = 0;
 }
 if(!centerLoaded){
 while(!rebuildChunks.empty()){
 Chunk* c = rebuildChunks.back();
 c->initialize(renderer);
 if((c->x-oldChunkX)*(c->x-oldChunkX) + (c->z-oldChunkZ)*(c->z-oldChunkZ) <= renderDistance*renderDistance + renderDistance * 0.8f){
 if(!c->isAirChunk && !c->isMarkedForRemoval()) { renderChunks.push_back(c); }
 }
 rebuildChunks.pop_back();
 }
 centerLoaded = true;
 }
 if(!rebuildChunks.empty()){//TODO: THREADED
 if(timer2 >= 0.01){
 timer2 = 0;
 Chunk* c = rebuildChunks.back();
 if(c->isInitialized()){
 c->rebuild(renderer);
 }else{
 c->initialize(renderer);
 }
 rebuildChunks.pop_back();
 }
 timer2+=delta;
 }
}
void ChunkManager::update(double delta, Camera& camera, vector<XMFLOAT4>& frustumPlanes){
 int chunkX = floor(XMVectorGetX(camera.camPosition) / double(BLOCK_RENDER_SIZE * CHUNK_SIZE));
 int chunkZ = floor(XMVectorGetZ(camera.camPosition) / double(BLOCK_RENDER_SIZE * CHUNK_SIZE));
 bool moved = oldChunkX != chunkX || oldChunkZ != chunkZ;
 if(moved){
 renderChunks.clear();
 vector<Chunk*> tempChunks;
 for(pair<const string, Chunk*>& pair : loadedChunks){//Remove chunks from list
 Chunk* c = pair.second;
 if(oldChunkX>chunkX){
 if(c->x == oldChunkX + renderDistance+1){
 c->markForRemoval(true);
 removableChunks.emplace_back(c);
 }else if(c->x ==oldChunkX - renderDistance-1){
 rebuildChunks.emplace_back(c);
 }
 }else{
 if(c->x ==oldChunkX - renderDistance-1){
 c->markForRemoval(true);
 removableChunks.emplace_back(c);
 }else if(c->x == oldChunkX + renderDistance+1){
 rebuildChunks.emplace_back(c);
 }
 }
 if(oldChunkZ<chunkZ){
 if(c->z == oldChunkZ - renderDistance-1){
 c->markForRemoval(true);
 removableChunks.emplace_back(c);
 }else if(c->z == oldChunkZ + renderDistance+1){
 rebuildChunks.emplace_back(c);
 }
 }else{
 if(c->z == oldChunkZ + renderDistance+1){
 c->markForRemoval(true);
 removableChunks.emplace_back(c);
 }else if(c->z == oldChunkZ - renderDistance-1){
 rebuildChunks.emplace_back(c);
 }
 }
 if(!c->isMarkedForRemoval()){
 tempChunks.emplace_back(c);
 }
 if((c->x-chunkX)*(c->x-chunkX) + (c->z-chunkZ)*(c->z-chunkZ) <= renderDistance*renderDistance + renderDistance * 0.8f){
 if(!c->isAirChunk && !c->isMarkedForRemoval()) { renderChunks.emplace_back(c); }
 }
 }
 loadChunks(tempChunks, chunkX, chunkZ);
 loadedChunks.clear();
 for(Chunk* c : tempChunks){
 string s = to_string(c->x) + "," + to_string(c->y) + "," + to_string(c->z);
 loadedChunks.emplace(s, c);
 }
 oldChunkX = chunkX;
 oldChunkZ = chunkZ;
 }
 timer+=delta;
 if(timer >= 0.01 && (oldCamYaw != camera.camYaw || oldCamPitch != camera.camPitch || moved)){
 cullAABB(frustumPlanes);
 timer = 0;
 oldCamYaw = camera.camYaw;
 oldCamPitch = camera.camPitch;
 }
 tickTimer+=delta;
 if(tickTimer >= 0.05){//0.05
 for(pair<const string, Chunk*>& pair : loadedChunks){
 pair.second->update(delta);
 }
 //update
 tickTimer = 0;
 }
}
void ChunkManager::loadChunks(vector<Chunk*>& tempChunks, int& chunkX, int& chunkZ){
 bool left = oldChunkX>chunkX;
 bool right = oldChunkX<chunkX;
 bool front = oldChunkZ<chunkZ;
 bool back = oldChunkZ>chunkZ;
 if(left){
 for(int z = -renderDistance-1; z <= renderDistance+1; z++){
 for(int y = 0; y < WORLD_HEIGHT; y++){
 Chunk* chunk = new Chunk(this, chunkX - renderDistance-1, y, z + chunkZ);
 rebuildChunks.push_back(chunk);
 tempChunks.push_back(chunk);
 }
 }
 }else if(right){
 for(int z = -renderDistance-1; z <= renderDistance+1; z++){
 for(int y = 0; y < WORLD_HEIGHT; y++){
 Chunk* chunk = new Chunk(this, chunkX + renderDistance+1, y, z + chunkZ);
 rebuildChunks.push_back(chunk);
 tempChunks.push_back(chunk);
 }
 }
 }else if(front){
 for(int x = -renderDistance-1; x <= renderDistance+1; x++){
 for(int y = 0; y < WORLD_HEIGHT; y++){
 Chunk* chunk = new Chunk(this, x + chunkX, y, chunkZ + renderDistance+1);
 rebuildChunks.push_back(chunk);
 tempChunks.push_back(chunk);
 }
 }
 }else if(back){
 for(int x = -renderDistance-1; x <= renderDistance+1; x++){
 for(int y = 0; y < WORLD_HEIGHT; y++){
 Chunk* chunk = new Chunk(this, x + chunkX, y, chunkZ - renderDistance-1);
 rebuildChunks.push_back(chunk);
 tempChunks.push_back(chunk);
 }
 }
 }
}
void ChunkManager::cullAABB(vector<XMFLOAT4>& frustumPlanes){//TODO: Make global
 bool cull = false;
 visibleChunks.clear();
 for(Chunk* c : renderChunks){
 cull = false;
 for(int planeID = 0; planeID < 6; ++planeID){
 XMVECTOR planeNormal = XMVectorSet(frustumPlanes[planeID].x, frustumPlanes[planeID].y, frustumPlanes[planeID].z, 0.0f);
 float planeConstant = frustumPlanes[planeID].w;
 XMFLOAT3 axisVert;
 if(frustumPlanes[planeID].x < 0.0f)
 axisVert.x = BLOCK_RENDER_SIZE * CHUNK_SIZE * c->x;
 else
 axisVert.x = BLOCK_RENDER_SIZE * CHUNK_SIZE * c->x + BLOCK_RENDER_SIZE * CHUNK_SIZE;
 if(frustumPlanes[planeID].y < 0.0f)
 axisVert.y = BLOCK_RENDER_SIZE * CHUNK_HEIGHT * c->y;
 else
 axisVert.y = BLOCK_RENDER_SIZE * CHUNK_HEIGHT * c->y + BLOCK_RENDER_SIZE * CHUNK_HEIGHT;
 if(frustumPlanes[planeID].z < 0.0f)
 axisVert.z = BLOCK_RENDER_SIZE * CHUNK_SIZE * c->z;
 else
 axisVert.z = BLOCK_RENDER_SIZE * CHUNK_SIZE * c->z + BLOCK_RENDER_SIZE * CHUNK_SIZE;
 if(XMVectorGetX(XMVector3Dot(planeNormal, XMLoadFloat3(&axisVert))) + planeConstant < 0.0f){
 cull = true;
 break;
 }
 }
 if(!cull){
 visibleChunks.push_back(c);
 }
 }
}

Answer 1

Header file:

• It's usually preferred to have your own headers before library headers. This can help avoid possible dependencies and also keep the headers more organized.

• Do not use using namespace std in a header file. It can be okay to have it in an implementation file due to the locality (.cpp files do not get imported), but having it in a header file will force users to have the std namespace exposed, which can possibly break their code. Just leave it out and use std:: where appropriate.

• Macro constants (or macros in general) are not very common in C++, and are primarily discouraged as there are better ways of doing things. Specifically, the const keyword should be used to make something constant and prevent any further changes to it.

  const int WORLD_HEIGHT = 4;
  

  Moreover, as these are in a header file, they will be global by default. While it is not such a bad thing since they cannot be modified, it would be safer to have them contained within a namespace or a class (only if it belongs in a class).

  namespace vals
  {
   const int WORLD_HEIGHT = 4;
   // ...
  }
  

  The constant can then be accessed via the scope operator (::):

  int height = vals::WORLD_HEIGHT;
  

  (Note: The name vals is only an example, so feel free to give a more relevant name. As a user may be using it frequently (unless using is used), try to make it short.)

  If it does belong in a class, then make it a static const type (it must be static as it belongs to the class itself and not the individual objects). If it's an integer type, it can be initialized inside the class declaration as public, otherwise it'll have to be done in the implementation file.

  The scope access concept still applies, except you'll use the class name:

  int height = Class::WORLD_HEIGHT;
  

• You can omit the ChunkManager constructor since you aren't already overwriting it. The compiler will provide a default one for you.

  Also, void parameters are not needed in C++, unlike in C. The compiler will already know that such call takes no arguments.

• It's a little confusing to have multiple public and private sections. Just group them into one.

  Also, centerLoaded should be private as it is a data member. That should not be exposed to the public interface.

Implementation file:

• Do not keep srand() anywhere but in main(). It should only be called once so that the seed will not be reset at each call, giving you the same random values. Keeping it in the constructor is still not sufficient as you'll be creating multiple objects thus calling the function multiple times. By having it in main() only, you know that it will only be called once in the entire program.

• Instead of using a constructor, you can use an initializer list:

  ChunkManager::ChunkManager()
   : renderDistance(8) //[5, 6, 7, 8, 12, 13, 14, 15, 20, 22]
   , centerLoaded(false)
   , timer(0)
   , timer2(0)
   , tickTimer(0)
   , removeTimer(0)
  {
   noises.push_back(new Noise(0, 0, 0, rand()));
   noises.push_back(new Noise(1, 0, 0, rand()));
   noises.push_back(new Noise(2, 0, 0, rand()));
  }
  

  Moreover, you don't need to allocate with new (this isn't Java). Leaving them out will still work as noises will then be adding anonymous objects (those initialized without a name). All it needs are the constructed objects, which you already have.

• Duckdoom5: Thanks for the tips, I'll use them but not edit the post as it will invalidate you answer.
• Jamal: @Duckdoom5: You're welcome! I'd also like to thank you for (supposedly) reading the Help Center and finding out about our answer-invalidation policy. It really does help avoid unneeded hassle.
• nonsensation: @Jamal Can you please elaborate your first point abit more? I also asked here in the comments on that - on my way to do the right things. Thanks :)
• Jamal: @Serthy: In general, it's good to try to keep headers self-dependent, otherwise some changes can lead to errors. By doing this, you can determine if any of your own are dependent on libraries, and if so, you can include the needed libraries on them separately.

Answer 2

A few additions to what has already been mentioned:

1. You said it's slow, but what part exactly is slow? Have you used a profiler and determined which function exactly is costing you the performance?

2. As one guess to performance difficulties: You keep a map loadedChunks which is keyed of a string and you convert a (x, y, z) triplet to strings all the time to find it. This will definitely cost you time. You can try either changing the key of a map to a std::tuple<int, int, int> (note that you'll need to provide a hash function for tuple yourself, example can be found here) or you make the map nested:

   unordered_map<int, unordered_map<int, unordered_map<int, Chunk *>>
   

   which has the downside of being a bit more complicated to use. Can't say how much it will improve things but it's worth a try.

3. Your code for the if(oldChunkX>chunkX){ and if(oldChunkZ<chunkZ){ cases is almost the same - refactor it into a common method.

4. Try and take care to format your code properly and consistently (spacing and indents) - it will improve readability and therefor maintainability. IDE's do that for you these days so there is no reason not to.

Answer 3

Memory management:

The first major issue with you code is that it leaks memory, and this might be one of the causes for your experiencing of low performance. C++ is not garbage collected, so each new must be deleted at some point.

You leak here, in the constructor:

ChunkManager::ChunkManager() {
 ...
 noises.push_back(new Noise(0, 0, 0, rand()));
 noises.push_back(new Noise(1, 0, 0, rand()));
 noises.push_back(new Noise(2, 0, 0, rand()));
}

Those are never deleted.

In addChunks(), not sure if being delete?

void ChunkManager::addChunks(int x, int z){
 for(int y = 0; y < WORLD_HEIGHT; y++){
 Chunk* chunk = new Chunk(this, x, y, z); // <<<<< is this ever deleted?
 rebuildChunks.push_back(chunk);
 string s = to_string(x) + "," + to_string(y) + "," + to_string(z);
 loadedChunks.emplace(s, chunk);
 }
}

And I'm also not sure if all the Chunks allocated by loadChunks() are being freed or not, since you have so may pointers flying around.

What you need here is more clear object ownership semantics. You need smart pointers.

However, the vector<Chunk*> should really just store Chunks by value (E.g.: std::vector<Chunk>). This alone will significantly improve performance due to better data locality and will remove all your memory leaks.

If you do have the need for any other pointer to object, then use an appropriate smart pointer from the standard library.

rand() is pretty lame:

The standard rand() function is very inefficient and is deprecated in favor of the new C++ <random> library. You should replace it by the more modern standard. See this short talk for more on the subject: "rand() Considered Harmful".

A few magic numbers here and there...

int x = rand() % 48;
int z = rand() % 48;
int y = WATER_LEVEL;
int checks = 1000;

These constants are unclear. They should be named constants. Always prefer const or constexpr. Don't use macros for that.

Const correctness:

Your code is not fully const-correct.

// These were missing the 'const' at the end:
float getWorldHeight(int x, int y) const;
Chunk * getChunkAt(int x, int y, int z) const;

Your also have other function parameters that are read-only and are not being declared as const. This should be fixed. Read more about const correctness here.

Don't use NULL:

NULL is an abomination in C++. Never use it. Use nullptr.

Chunk* ChunkManager::getChunkAt(int x, int y, int z){
 string s = to_string(x) + "," + to_string(y) + "," + to_string(z);
 auto& it = loadedChunks.find(s);
 if(it != loadedChunks.end()){
 return it->second;
 }
 //return NULL; wrong!
 return nullptr; // C++11, always prefer. Use 0 on pre-11 code.
}

• ratchet freak: looking at the usage vector<Noise*> noises; and unordered_map<string, Chunk*> loadedChunks; should both be changed to hold by value (or smart pointer in the chunk's case)

Answer 4

you don't specify a destructor meaning every Chunk (and Noise) still loaded will leak when the manager gets destroyed.

More about the efficiency:

When the player is going back and forth at a chunk boundary the chunks at the edge will keep getting loaded and unloaded, you can fix this by making the unload distance 1 or 2 larger than the load distance.

Also consider using a object pool where "deleted" chunks get copied to and can be re-purposed for another chunk. this will require changes in the chunk itself so they can get re-purposed.

Either way I would suggest looking at the Chunk code and investigate why deleting one takes so long.