Diamonds and Squares Algorithm not working

Question

I am working on making fractal terrain, but no matter what try, it always comes out looking completely random. I have been following the Diamonds and Squares algorithm as explained here. What can I do to fix this problem?

This is my Terrain Class:

package game;

import java.util.Random;

public class Terrain {

    Panel panel;

    public Terrain(Panel panel) {
        this.panel = panel;
        generateTerrain();
    }

    private void generateTerrain() {
        Random rand = new Random();

        int seed = rand.nextInt(panel.colors.length);
        int sideLength = panel.mapSize - 1;
        int halfSideLength;
        int average;

        panel.map[0][0] = seed;
        panel.map[panel.mapSize - 1][0] = seed;
        panel.map[0][panel.mapSize - 1] = seed;
        panel.map[panel.mapSize - 1][panel.mapSize - 1] = seed;

        while (sideLength > 0) {
            halfSideLength = sideLength / 2;
            for (int x = 0; x < panel.mapSize - 1; x += sideLength) {
                for (int y = 0; y < panel.mapSize - 1; y += sideLength) {
                    average = panel.map[x][y]
                            + panel.map[x + sideLength][y]
                            + panel.map[x][y + sideLength]
                            + panel.map[x + sideLength][y + sideLength];
                    average /= 4;
                    average += rand.nextInt(8);
                    panel.map[x + halfSideLength][y + halfSideLength] = average;
                }
            }
            for (int x = 0; x < panel.mapSize - 1; x += sideLength) {
                for (int y = 0; y < panel.mapSize - 1; y += sideLength) {
                    average = panel.map[x][y]
                            + panel.map[x + halfSideLength][y]
                            + panel.map[x][y + sideLength]
                            + panel.map[x + halfSideLength][y + halfSideLength];
                    average /= 4;
                    panel.map[x][y] = average;
                    if (x == 0) {
                        panel.map[panel.mapSize - 1][y] = average;
                    }
                    if (y == 0) {
                        panel.map[x][panel.mapSize - 1] = average;
                    }
                }
            }
            sideLength /= 2;
        }
    }
}

and this is my Panel Class:

package game;

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Panel extends JPanel implements ActionListener {

    Terrain currentTerrain;

    boolean upPressed = false;
    boolean rightPressed = false;
    boolean downPressed = false;
    boolean leftPressed = false;

    int tileSize = 1;
    int mapSize = 1025;

    int deltaX = 0;
    int deltaY = 0;
    int x = 0;
    int y = 0;

    int map[][] = new int[mapSize][mapSize];

    Color[] colors = {
        new Color(0, 0, 180),
        new Color(0, 0, 255),
        new Color(0, 150, 255),
        new Color(255, 255, 180),
        new Color(220, 220, 120),
        new Color(200, 200, 60),
        new Color(0, 200, 0),
        new Color(0, 180, 0),
        new Color(0, 160, 0),
        new Color(0, 140, 0),
        new Color(0, 120, 0),
        new Color(0, 100, 0),
        new Color(0, 80, 0),
        new Color(0, 60, 0),
        new Color(0, 40, 0),
        new Color(40, 40, 40),
        new Color(60, 60, 60),
        new Color(80, 80, 80),
        new Color(100, 100, 100),
        new Color(120, 120, 120),
        new Color(255, 255, 255)
    };


    public Panel(Main main) {
        setPreferredSize(main.getSize());
        setFocusable(true);
        setBackground(Color.WHITE);
        add(new KeyBindings(this));
        currentTerrain = new Terrain(this);
        new Timer(1000 / 120, this).start();
    }

    private void tick() {
        if (upPressed) {
            deltaY += 10;
        } else if (downPressed) {
            deltaY -= 10;
        }
        if (rightPressed) {
            deltaX -= 10;
        } else if (leftPressed) {
            deltaX += 10;
        }
        repaint();
    }

    @Override
    public void actionPerformed(ActionEvent e) {
        tick();
    }

    @Override
    public void paintComponent(Graphics g) {
        super.paintComponent(g);

        x = 0;
        y = 0;

        for (int[] rowData : map) {
            for (int cellData : rowData) {
                int v = cellData;
                if(v < 0) {
                    v = 0;
                } else if(v > colors.length - 1) {
                    v = colors.length - 1;
                }
                g.setColor(colors[v]);
                g.fillRect(x + deltaX, y + deltaY, tileSize, tileSize);
                x += tileSize;
                if(x == mapSize * tileSize) {
                    x = 0;
                    y += tileSize;
                }
            }
        }
    }
}

Answer 1

You've got the diamond stage of the algorithm wrong. The centres of the diamonds are the midpoints of the square's sides. They are best treated in two separate loops: One for the vertical midpoinst and the second for the horizontal midpoints. At the edge of the map, the tips of the diamnds will reach out of the map. You can solve that by "folding" them into the map, so that for example at the left edge, the right point is considered twice.

So the code should be:

function generateTerrain() {
    int seed = rand.nextInt(colors.length);
    int sideLength = mapSize - 1;
    int halfSideLength;
    int average;
    int offset = 8;

    map[0][0] = seed;
    map[mapSize - 1][0] = seed;
    map[0][mapSize - 1] = seed;
    map[mapSize - 1][mapSize - 1] = seed;

    while (sideLength > 0) {
        halfSideLength /= 2;
        for (int x = 0; x < mapSize - 1; x += sideLength) {
            for (int y = 0; y < mapSize - 1; y += sideLength) {
                average = map[x][y]
                        + map[x + sideLength][y]
                        + map[x][y + sideLength]
                        + map[x + sideLength][y + sideLength];
                average /= 4;
                average += rand.nextInt(offset);

                map[x + halfSideLength][y + halfSideLength] = average;
            }
        }

        for (int x = 0; x < mapSize - 1; x += sideLength) {
            for (int y = 0; y < mapSize; y += sideLength) {
                int yTop = y - halfSideLength;
                int yBottom = y + halfSideLength;

                if (yTop < 0) yTop = y + halfSideLength;
                if (yBottom > mapSize - 1) yBottom = y - halfSideLength;

                average = map[x][y]
                        + map[x + sideLength][y]
                        + map[x + halfSideLength][yTop]
                        + map[x + halfSideLength][yBottom];
                average = /= 4;

                map[x + halfSideLength][y] = average;
            }
        }

        for (int x = 0; x < mapSize; x += sideLength) {
            for (int y = 0; y < mapSize - 1; y += sideLength) {
                int xLeft = x - halfSideLength;
                int xRight = x + halfSideLength;

                if (xLeft < 0) xLeft = x + halfSideLength;
                if (xRight > mapSize - 1) xRight = x - halfSideLength;

                average = map[x][y]
                        + map[x][y + sideLength]
                        + map[xRight][y + halfSideLength]
                        + map[xRight][y + halfSideLength];
                average /= 4;

                map[x][y + halfSideLength] = average;
            }
        }

        sideLength /= 2;
    }
}

(Note: I've worked from your code, but converted it into Javascript and back, so that there are probably some Java blunders still in it. But I think the idea of the two loops is clear.)

This will give very noisy maps. Usually, the random offset (8 in your code) is reduced by a constant factor every time you halve the side length. The smoothness of the map can be controlled with this parameter and it is interesting to play with it. In your case, the parameter is 1.0. A good factor for realistic maps is around 0.65.

There's another problem of your method: You use narrow integers throughout. I use "narrow" here to mean, that the granularity of the integers, namely 1, is equal to a colour change in your map. That doesn't give a lot of range for random variation within one colour. It might be a good idea to either use floating-point numbers or integers of a wider range for map generation and then map these values to your colours.

For example, say you use floating-point numbers between 0.0 and 1.0: You could then map values below 0.1 to dark green, below 0.2 to light green and so on until you get white for values above 0.9. That would give a smoother banded appearence like in the cloud picture below the section of the article you linked.

Another thing is that you start with a random value at the corners and then clamp values to the range of colours when printing the map. The random offset you add is always positive, so if you start with a "high" colour, you are very likely to get a mostly white picture. In fact, you won't get any colour below your starting value. You could start with a middle colour and allow both negative and positive random offsets to circumvent this. Or you could normalize the map based on the lowest and highest values after generating it.