patterncsharpMinor

Improving Terrain Generation Time in C#

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

generationimprovingtimeterrain

Problem

I am working on making my code run smoother, since I will be using it a lot in a game in development, but I am stumped. Is there any way I could make this run faster? Improvements to the terrain generation and image drawing are both welcome.

```
internal class Terrain
{
public Terrain(Content content)
{
Random random = new Random();
int seed = random.Next(content.MaxSeed - content.MinSeed) + content.MinSeed;
int offset = 10000;
int sideLength = content.MapSize - 1;
int halfSideLength;
int average;
int yTop;
int yBottom;

content.Map[0 , 0] = seed;
content.Map[content.MapSize - 1 , 0] = seed;
content.Map[0 , content.MapSize - 1] = seed;
content.Map[content.MapSize - 1 , content.MapSize - 1] = seed;

content.Screen = "GeneratingTerrain";
while (sideLength > 0)
{
halfSideLength = sideLength / 2;

for (int x = 0; x = 0.5)
{
average += random.Next(offset);
}
else
{
average -= random.Next(offset);
}

content.Map[x + halfSideLength , y + halfSideLength] = average;
}
}

for (int x = 0; x content.MapSize - 1) yBottom = y - halfSideLength;

average = content.Map[x , y]
+ content.Map[x + sideLength , y]
+ content.Map[x + halfSideLength , yTop]
+ content.Map[x + halfSideLength , yBottom];
average /= 4;

content.Map[x + halfSideLength , y] = average;
}
}

for (int x = 0; x content.MapSize - 1) xRight = x - halfSideLength;

average = content.Map[x , y]
+ content.Map[x , y + sideLength]

Solution

Your algorithm for iterating over the map is quite strange. It appears that you're trying to generate the mid point of the 4 corners in the first loop. In the second loop, you then generate the mid points of the vertical sides of the quad. (Though it seems like at least one of the points will be uninitialized when this happens.) And the third loop generates the mid points of the horizontal sides. Finally, you make a final pass to ensure that none of the values are out of range. Then you cut the tile size in half and iterate until you've filled the array.

You could do this all in one loop, I believe. I have to admit that I don't actually know C#, so this will be a little pseudo-codey. Sorry about that. Here's how I've done it the past.

First, you need a structure that holds the coordinates of a rectangle. Something like this:

struct Rect {
    int left;
    int bottom;
    int right;
    int top;
} Rect;

Next, we generate the 4 corners of the map with the seed value and put it into a queue.

content.Map [ 0, 0 ] = seed;
content.Map [ sideLength, 0 ] = seed;
content.Map [ 0, sideLength ] = seed;
content.Map [ sideLength, sideLength ] = seed;
Queue processQueue; // A queue to hold elevation data
Rect firstRect = { 0, 0, sideLength, sideLength };
processQueue.add (firstRect);

Now we'll pull a record out of the queue, divide it into 4 smaller rectangles, set the values of those positions in the map, and add the 4 smaller rectangles back into the queue.

// Divide each rect and add it back to the queue
int numPasses = log2(sideLength);
while (numPasses > 0)
{
    int numElements = processQueue.size();
    for (int i = 0; i < numElements; i++)
    {
        // Get the next Rect out of the queue
        Rect nextRect = processQueue.dequeue();

        // Set the center point to the average of the 4 corners
        int midX = (nextRect.left + nextRect.right) / 2;
        int midY = (nextRect.bottom + nextRect.top) / 2;
        content.Map [ midX, midY ] = average (content.Map, Rect); 

        // Divide it into 4 smaller rectangles
        Rect rect1 = { nextRect.left, nextRect.bottom, midX, midY };
        Rect rect2 = { midX, nextRect.bottom, nextRect.right, midY };
        Rect rect3 = { nextRect.left, midY, midX, nextRect.top };
        Rect rect4 = { midX, midY, nextRect.right, nextRect.top };

        // Set the values of the midpoints of the 4 edges
        int randomOffset = random.Next(offset * 2) - offset;
        content.Map [ midX, nextRect.bottom ] = 
            ((content.Map [ nextRect.left, nextRect.bottom ] +
            content.Map [ nextRect.right, nextRect.bottom) / 2) + 
            randomOffset;
        //... do the same for the mid point on the top, the left, and the right

        // Add the 4 smaller rects to the queue
        processQueue.add (rect1);
        processQueue.add (rect2);
        processQueue.add (rect3);
        processQueue.add (rect4);
    }
    numPasses--;
}

In this case the average() function calculates the average at the 4 corners of the passed-in rectangle:

int average (MapType m, Rect r)
{
    return (m [ r.left, r.bottom] +
            m [ r.left, r.top ] +
            m [ r.right, r.bottom ] +
            m [ r.right, r.top ]) / 4;
}

You can also clamp the part where you calculate the midpoint so you don't ever go above the max or below the minimum if you need to.

I should note that this will only hit every element in your map array if the dimensions are powers of 2. I believe your code had the same limitation, though, if I'm understanding it correctly.

Code Snippets

struct Rect {
    int left;
    int bottom;
    int right;
    int top;
} Rect;

content.Map [ 0, 0 ] = seed;
content.Map [ sideLength, 0 ] = seed;
content.Map [ 0, sideLength ] = seed;
content.Map [ sideLength, sideLength ] = seed;
Queue<Rect> processQueue; // A queue to hold elevation data
Rect firstRect = { 0, 0, sideLength, sideLength };
processQueue.add (firstRect);

// Divide each rect and add it back to the queue
int numPasses = log2(sideLength);
while (numPasses > 0)
{
    int numElements = processQueue.size();
    for (int i = 0; i < numElements; i++)
    {
        // Get the next Rect out of the queue
        Rect nextRect = processQueue.dequeue();

        // Set the center point to the average of the 4 corners
        int midX = (nextRect.left + nextRect.right) / 2;
        int midY = (nextRect.bottom + nextRect.top) / 2;
        content.Map [ midX, midY ] = average (content.Map, Rect); 

        // Divide it into 4 smaller rectangles
        Rect rect1 = { nextRect.left, nextRect.bottom, midX, midY };
        Rect rect2 = { midX, nextRect.bottom, nextRect.right, midY };
        Rect rect3 = { nextRect.left, midY, midX, nextRect.top };
        Rect rect4 = { midX, midY, nextRect.right, nextRect.top };

        // Set the values of the midpoints of the 4 edges
        int randomOffset = random.Next(offset * 2) - offset;
        content.Map [ midX, nextRect.bottom ] = 
            ((content.Map [ nextRect.left, nextRect.bottom ] +
            content.Map [ nextRect.right, nextRect.bottom) / 2) + 
            randomOffset;
        //... do the same for the mid point on the top, the left, and the right

        // Add the 4 smaller rects to the queue
        processQueue.add (rect1);
        processQueue.add (rect2);
        processQueue.add (rect3);
        processQueue.add (rect4);
    }
    numPasses--;
}

int average (MapType m, Rect r)
{
    return (m [ r.left, r.bottom] +
            m [ r.left, r.top ] +
            m [ r.right, r.bottom ] +
            m [ r.right, r.top ]) / 4;
}

Context

StackExchange Code Review Q#92712, answer score: 3

Revisions (0)

No revisions yet.