# Help with on-the-fly terrain generation

This topic is 2895 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm writing an engine that can generate landscapes using noise functions, and load in new chunks as the player moves around the terrain. I spent the best part of two days figuring out how to place these chunks in the right position, so they don't overlap or get placed on top of existing chunks. It works well functionally, but there is a massive performance hit the further away you generate the chunks from the player (e.g. if you generate in a 3 chunk radius around the player, it's lighting fast, but if you increase that to a radius of 20 chunks it slows down very fast).

I know exactly why that is, but I can't think of any other way to do this. Before I go any further, here's the code I'm currently using, hopefully it's commented well enough to understand:

 // Get the player's position rounded to the nearest chunk on the grid. D3DXVECTOR3 roundedPlayerPos(SnapToMultiple(m_Dx->m_Camera->GetPosition().x, CHUNK_X), 0, SnapToMultiple(m_Dx->m_Camera->GetPosition().z, CHUNK_Z)); // Iterate through every point on an invisible grid. At each point, check if it is // inside a circle the size of the grid (so we generate chunks in a circle around // the player, not a square). At each point that is inside the circle, add a chunk to // the ChunksToAdd vector. for (int x = -CHUNK_RANGE-1; x <= CHUNK_RANGE; x++) { for (int z = -CHUNK_RANGE-1; z <= CHUNK_RANGE; z++) { if (IsInside(roundedPlayerPos, CHUNK_X*CHUNK_RANGE, D3DXVECTOR3(roundedPlayerPos.x+x*CHUNK_X, 0, roundedPlayerPos.z+z*CHUNK_Z))) { Chunk chunkToAdd; chunkToAdd.chunk = 0; chunkToAdd.position = D3DXVECTOR3((roundedPlayerPos.x + x*CHUNK_X), 0, (roundedPlayerPos.z + z*CHUNK_Z)); chunkToAdd.chunkExists = false; m_ChunksToAdd.push_back(chunkToAdd); } } } // Iterate through the ChunksToAdd vector. For each chunk in this vector, compare it's // position to every chunk in the Chunks vector (which stores each generated chunk). // If the statement returns true, then there is already a chunk at that location, and // we don't need to generate another. for (i = 0; i < m_ChunksToAdd.size(); i++) { for (int j = 0; j < m_Chunks.size(); j++) { // Check the chunk in the ChunksToAdd vector with the chunk in the Chunks vector (chunks which are already generated). if (m_ChunksToAdd.position.x == m_Chunks[j].position.x && m_ChunksToAdd.position.z == m_Chunks[j].position.z) { m_ChunksToAdd.chunkExists = true; } } } // Determine the closest chunk to the player, so we can generate that first. // Iterate through the ChunksToAdd vector, and if the vector doesn't exist (if it // does exist, we're not going to generate it so ignore it), compare the current (i) // chunk against the current closest chunk. If it is larger, move on, and if it is // smaller, store it's position as the new smallest chunk. int closest = 0; for (j = 0; j < m_ChunksToAdd.size(); j++) { if (!m_ChunksToAdd[j].chunkExists) { // Get the distance from the player to the chunk for the current closest chunk, and // the chunk being tested. float x1 = ABS(DistanceFrom(roundedPlayerPos, m_ChunksToAdd[j].position)); float x2 = ABS(DistanceFrom(roundedPlayerPos, m_ChunksToAdd[closest].position)); // If the chunk being tested is closer to the player, make it the new closest chunk. if (x1 <= x2) closest = j; } } // After determining the position of the closest chunk, generate the volume and mesh, and add it // to the Chunks vector for rendering. if (!m_ChunksToAdd[closest].chunkExists) // Only add it if the chunk doesn't already exist in the Chunks vector. { Chunk chunk; chunk.chunk = new chunkClass; chunk.chunk->m_Position = m_ChunksToAdd[closest].position; chunk.chunk->GenerateVolume(m_Simplex); chunk.chunk->GenerateMesh(m_Dx->GetDevice()); chunk.position = m_ChunksToAdd[closest].position; chunk.chunkExists = true; m_Chunks.push_back(chunk); } // Clear the ChunksToAdd vector ready for another frame. m_ChunksToAdd.clear();

(if it wasn't already obvious, this is run every frame.)

The problem area is to do with the CHUNK_RANGE variable. The larger this value, the more the first two loops are iterated through each frame, slowing the whole thing down tremendously. I need some advice or suggestions on how to do this more efficiently, thanks.

##### Share on other sites
• Rather than every frame, only re-generate your chunks-to-add vector when the player character enters a new chunk. And rather than flagging chunks which already exist, remove them from the vector when they're detected or generated.

• Use the direction of character movement to cut the range(s) in half (no need to scan the area he's coming from).

• The search through the existing chunks, for one pre-existing at a given position, needs to early-out when it finds one. As written, it continues to scan all the rest of the existing chunks even though it already found the one it was looking for. (This scan can become a problem anyway if existing chunks are never cleared from this list.)

• Assuming that, in the general case, there will already be a circle of chunks around the player character, and the closest new chunk will be somewhere at the edge of that circle... Even though you only generate one new chunk per frame, it's probably unnecessary to ensure that it's the closest possible one. Simply generating the first one in the chunks-to-add vector each frame, until it's empty, should probably be sufficient.
Edited by vreality

##### Share on other sites

• Rather than every frame, only re-generate your chunks-to-add vector when the player character enters a new chunk.
• The search through the existing chunks for one pre-existing at a given position needs to early-out when it finds one. As written, it continues to scan all the rest of the existing chunks even though it already found the one it was looking for.
• Assuming that, in the general case, there will already be a circle of chunks around the player character, and the closest new chunk will be somewhere at the edge of that circle... Even though you only generate one new chunk per frame, it's probably unnecessary to ensure that it's the closest possible one. Simply generating the first one in the chunks-to-add vector each frame, until it's empty, should probably be sufficient.

Great advice, thanks. I'll have a go at implementing those ideas. The thing with generating the nearest chunk is more so that it looks good when flying over the terrain fast, at speeds the player will normally travel it is a bit redundant, I agree .

##### Share on other sites
Ooops. Edited my previous post while you were replying. Please take another look.

##### Share on other sites
You do realise that generating all chunks in a 20 chunk radius creates over 40x more chunks than generating all chunks in a 3 chunk radius? This is the cause of the slowdown you noticed.

VReality's suggestions are good, another thing to remember is that you don't need to render any chunks that are behind the player or out of their field of view. Currently you seem to be assuming that every generated chunk should be rendered. Google "Frustrum Culling", as that's a pretty good technique for determining what to draw, especially for terrain which is already broken up into chunks.

##### Share on other sites

You do realise that generating all chunks in a 20 chunk radius creates over 40x more chunks than generating all chunks in a 3 chunk radius? This is the cause of the slowdown you noticed.

VReality's suggestions are good, another thing to remember is that you don't need to render any chunks that are behind the player or out of their field of view. Currently you seem to be assuming that every generated chunk should be rendered. Google "Frustrum Culling", as that's a pretty good technique for determining what to draw, especially for terrain which is already broken up into chunks.

Thanks for the advice. I implemented most of VReality's suggestions, it is faster now. I think you don't understand how I'm generating the chunks though. I do one chunk per frame, if there is one to generate, so I'm never rendering more than one a frame, because that would cause massive stuttering when moving. It slows down because of having to search through 20x20 positions for existing chunks. I know about frustum culling, though it's not a priority because the frame rate is massively CPU bottlenecked, rendering the chunks is very fast.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 13
• 30
• 9
• 16
• 12