# Any ideas on reducing lag in terrain generation?

Ok so here's the deal. I've written an isometric engine that generates terrain based on camera values using 2D perlin noise. I planned on doing 3D but first I need to work out the lag issues I'm having. I will try to explain how I am doing this so that maybe someone can spot where I am going wrong. I know it should not be this laggy.

There is the abstract class Block which right now just contains render(). BlockGrass, etc. extend this class and each has code in the render function to create a textured quad at the given position.

Then there is the class Chunk which has the function Generate() and setBlocksInArea(). Generate uses 2D perlin noise to make a height map and stores the heights in a 2D array. It stores the positions of each block it generates in blockarray[x][y][z]. The chunks are 8x8x128.

In the main game class there is a 3D array called blocksInArea. The blocks in this array are what gets rendered. When a chunk generates, it adds its blocks to this array at the correct index. It is like this so chunks can be saved to the hard drive (even though they aren't yet) but there can still be optimization with the rendering that you wouldn't have if you rendered each chunk separately.

Here's where the laggy part comes in:

When the camera moves to a new chunk, a row of chunks generates on the end of the axis that the camera moved on. But it still has to move the other chunks up/down in the blocksInArea (render) array. It does this by calculating the new position in the array and doing the Chunk.setBlocksInArea():

for(int x = 0; x < 8; x++){
for(int y = 0; y < 8; y++){
nx = x+(coordX - camCoordX)*8
ny = y+(coordY - camCoordY)*8
for(int z = 0; z < height[x][y]; z++){
blockarray[x][y][z] = Game.blocksInArea[nx][ny][z];
}
}
}


My reasoning was that this would be much faster than doing the perlin noise all over again, but there are still little spikes of lag when you move in between chunks.

Edit: Would it be possible to create a 3 dimensional array list so that shifting of chunks within the array would not be neccessary?

• Pure reasoning doesn't often work where performance is concerned. Have you tried running a performance profile to find out where your time is really going? – Patrick Hughes Dec 3 '11 at 16:36
• I don't even know what that is. I'll look it up. – l5p4ngl312 Dec 3 '11 at 19:29
• @l5p4ngl312: programmers.stackexchange.com/questions/79946/79995#79995 Everyone knows 95% of the time is spent in 5% of the code. But not everyone realizes that the 5% is usually going to be different than what you think it is, a lesson they must figure out over time the hard way. The only way to know which part of your code is causing the lag is to run it through a performance profiler, which tells you which code takes longest to run. – BlueRaja - Danny Pflughoeft Jan 2 '12 at 18:39
• Are you having performance issues or lag issues? The two are not really the same. Lag deals with latency issues (failure to respond to input etc. in a timely manner) whereas performance deals with the inability to get an amount of work done (render a frame, etc.) in a timely manner. – notlesh Jun 19 '12 at 0:28

Chunk your map - at least in the z,x dimensons (longitude and latitude NOT height) if it's an isometric game, make the chunks as big as can be fit on the screen at one time - and maintain the 9 chunks around the camera in memory.

build a structure for each chunk, be it an octree, or quad or whatever, but try to store it as a 1D array.

it should have methods along the lines of: generate(), load(), save()

only generate once - as the character moves around, cache chunks to the disk, as they're simple arrays, loading and saving them should be very efficient.

Try to steer clear of nested objects, building a huge array of objects isn't terribly efficient when you can do the same thing with a well ordered array.

If this is a minecraft style map, where there is depth to tiles, then a 3 dimensional dataset (converted into a 1D array) is ok, if you're just storing the height and type of tiles, you can do that in a single number using bitwise operators, with 128 levels, and 128 tiles your tile data can be stored in a single byte. Meaning your entire map can be stored as series of bytes.

• +1 for avoiding OOP. When I wrote my voxel engine, I saw a more than 100x speedup by converting my lists of Block objects to integer arrays. – Wackidev Jun 18 '12 at 18:41

It sounds like you're maintaining an array of blocks currently visible on screen, with indices based on the camera position. This requires you to shuffle things around the array whenever the camera moves. Instead, your array indices should be based on position in the world, and the drawing routine should loop through a range of indices based on the camera position. This way you do not need to copy anything around; when the camera moves you just index into a different spot in the array.

You can still load and unload chunks as the camera moves around, but this way when a chunk loads it always goes to the same spot in the array regardless of where the camera is. Parts of the world array that are off-screen may be empty, with no tiles loaded.

Also, why do you have 3D arrays of tiles instead of 2D arrays? And why is the height dimension 128? Maybe I'm misunderstanding how your system works, but terrain would typically only have one tile at each horizontal position. If you have 1 valid tile and 127 empty tiles in each column, you're wasting a lot of time and memory on the empty ones. If that's the case, you should get rid of the empty tiles - just store a 2D array of tiles and their heights (as integers).

• Sorry I failed to mention the world is infinite... And it isn't a standard isometric game where there is like one height level. It can go up to 128 but usually generates up to around 64. You cannot base the indices on camera position because you can't have an infinite array. Whoa I just thought of something. Would it be possible to use an ArrayList? – l5p4ngl312 Dec 3 '11 at 8:08
• OK, with an infinite world you'll need a more sophisticated data structure, but it should still be possible to make this work without expensive copying around every time the camera moves. You could use linked lists of tiles, for instance. I'm not familiar enough with Java to know whether an ArrayList is the right thing. You might have to build a customized data structure yourself. As for the height, do you mean you have 128 possible heights for tiles, or you need up to 128 actual tiles stacked at the same horizontal position? – Nathan Reed Dec 3 '11 at 19:22
• 128 possible that will be stored/rendered. I will look into linked lists. I tried running generation on a separate thread. It eliminated the lag but the chunks shifting is visible so you see black flashes (at least I think that's why). – l5p4ngl312 Dec 3 '11 at 19:31

Don't copy all the data; just collect the visible chunks and render each one. It sounds like you considered this:

but there can still be optimization with the rendering that you wouldn't have if you rendered each chunk separately.

I think you are probably wrong here. Rendering chunks separately creates many opportunities for saving effort, and doing what you're doing has the cost of shifting large amounts of data around. Could you explain what optimization you are trying to make possible?

It sounds like you're writing a Minecraft-style engine (infinite random voxel terrain, height limit w/ terrain at halfway point, chunks). So am I: here's my code. My world is not infinite, but the rendering subsystem doesn't care about that — it breaks things into chunks itself and never looks at the entirety of the world (other than for fast indexing). Rendering chunks individually means that when a block is updated and needs to be rerendered, only the one chunk's geometry needs to be recalculated (for new hidden surface removal, etc.).

If I were to try to render the entire visible world together, I would have to rebuild the entire vertex array whenever the camera moved (at great expense) because the newly-visible terrain doesn't necessarily have the same number of vertices as the newly-hidden (opposite camera motion direction) terrain. Furthermore, per-frame I test each chunk's bounding box against the view frustum, which is a cheap test which greatly reduces the cost of the invisible parts of a complex scene.

(Note: I am working in JavaScript (and WebGL), so my work is somewhat more CPU-bound than yours probably is.)