Voxel engine and LibGDX – Continuous terrain
In my previous post I showed how to create a bunch of static chunks in code. If we did move outside the area they did disappear. What we want is that new chunks are created when we move around in the world.
Git repository with the source code
Create new chunks
The easiest way to do this is by checking where the camera currently is located and create new chunks around it. We also want to limit how wide area is checked and we do this by setting a view range.
Inside the view range we do loop trough all the possible locations for chunks in a grid by the same size as our chunk size. So every 16 block in all directions. If no chunk is found there we will create a new one.
public static int VIEWRANGE = 150;
for (float x = camPos.x - VIEWRANGE; x < camPos.x + VIEWRANGE; x += WIDTH) {
for (float z = camPos.z - VIEWRANGE; z < camPos.z + VIEWRANGE; z += WIDTH) {
position.set(x, 0, z);
position.x = (float) Math.floor(position.x / WIDTH) * WIDTH;
position.z = (float) Math.floor(position.z / WIDTH) * WIDTH;
Chunk chunk = findChunk(position);
if (chunk == null) {
Vector3 chunkPosition = position.cpy();
Chunk c = createRandomChunk(chunkPosition);
chunks.add(chunkPosition);
currentChunk = c;
}
}
}This works great and new chunks are created when we fly around. But after a while the speed starts to decrease and it takes longer and longer time to check for chunks. The reason is that we store all chunks in a List and to find out if a chunk exists in a certain place we have to loop trough the list and check all entries.
To solve this there are a few different ways. One is to use something call Octrees where chunks are stored in a efficient way where lookups are fast. It’s also a quite difficult algorithm to implement so lets go for something easier. If I need to find a chunk in a certain place without having to loop trough them all.. what would we use? A HashMap! We store the location of the chunk as the key and the chunk itself as the value. Now it will only take one call to check if a chunk exists.
private HashMap<Vector3,Chunk> chunks = new HashMap<Vector3,Chunk>();
....
Chunk c = createRandomChunk(chunkPosition);
chunks.put(chunkPosition, c);
....
public Chunk findChunk(Vector3 pos) {
if (chunks.containsKey(pos)){
return chunks.get(pos);
}
return null;
}Allright! creation of chunks are fast again.. but the FPS is still dropping! Well off course.. it will keep all chunk meshes on the screen even if we can’t see them anymore (they are behind us or the chunks are basically outside the far view of the camera.
How can we solve that?
Frustum culling
I will not go into details about this but frustum is basically a triangle that starts a the cameras near point and extends out to the far point. Everything we see on the screen is inside this triangle. Frustum culling is where we check if the mesh we want to draw is inside or outside this triangle.
The easiest way to check for this is in our rendering method where we go trough all chunks before drawing them. What’s the algorithm for that? It’s a bit complicated but luckily (and one of the reasons I did pick LibGDX) we have just such a method on the camera frustum class.
for (Chunk chunk : terrain.getChunks()) {
boolean inFrustum = camera.frustum.sphereInFrustum(chunk.getPosition(), Terrain.WIDTH * 1.5f);
if (!inFrustum) {
//System.out.println("Not in frustum");
continue;
}
... render...
}And there it is. We can now fly around “forever” with new chunks being created. There are a few more optimizations that can be done (for example pass a location to the getChunks() call and make sure that anything outside that location is not included in the chunk loop but basically this should allow us to walk around for a long time (in current code we fly with a very fast speed). The only thing that will be a resource hog now is the memory.