12
\$\begingroup\$

The diamond square algorithm is a fractal terrain (heightmap) generating algorithm. You can find a nice description how it works here:

http://www.gameprogrammer.com/fractal.html (Used as a reference.)

http://www.playfuljs.com/realistic-terrain-in-130-lines/ (Great JS implementation, perhaps you might want to steal his renderer. Take a look here what this algorithm is capable of http://demos.playfuljs.com/terrain/.)

The general idea is that you have 4 corners as seeds (a), and calculate the height of the center point by averaging those four corners and adding a random value e.g. between -0.5 and 0.5 (b). If you apply this to the grid you get again a grid of diamonds (squares turend 45°) and you repeat the same (c,d), but the random range gets smaller, e.g. -0.125 to 0.125 etc. enter image description here

Your program must accept a number of inputs:

  • An integer l=1,2,3,... that determines the size of the square grid with side length 2^l+1. At l=10 you will have to store about one million numbers.
  • Four seeds (floating point) for each corner
  • A parameter 0<h<1 that determines the roughness (H in the link) that means how big the random range is initially
  • Parameters a,b that represent initial lower and upper bounds for the random range and get multiplied by h in each refinement step. (The random number is uniformly chosen between a and b.

The output must consist of the finished 2d grid.

So the rough algorithm would look like this:

Create a square grid with sidelength 2^l+1
Place seed values in the corners
Repeat:
  |  Perform square steps
  |  Refine Range: a = a*h; b=b*h;
  |  Perform diamond steps
  |  Refine Range

There is one detail you should be aware of: At the boundary of the grid, you will only have three vertices of the diamond, so you should also only calculate the average of those three points.

A visualization of some examples (please tell us what parameters you used) is optional but appreciated, and does of course not add to the byte count.

A slight variated implementation of this algorithm can be found here: Parallel projected voxel terrain generator

I created a small drawing function in javascript for displaing heightmaps in 2d as grayscale image. http://jsfiddle.net/flawr/oy9kxpsx/

If anyone of you is into fancy 3d and can make a script to view maps in 3d let me know!=)

\$\endgroup\$
8
\$\begingroup\$

Java, 1017 bytes

Input is a space separated list like so: l s1 s2 s3 s4 h a b.

Output is an 2d-array containing the numbers.

Program:

import java.util.*;import static java.lang.Math.*;class C{public static void main(String[]a){int b=a.length,d=0;float[]c=new float[b];for(;d<b;){c[d]=Float.parseFloat(a[d++]);}e=(int)(pow(2,c[0])+1);f=new float[e][e];f[0][0]=c[1];f[0][e-1]=c[2];f[e-1][0]=c[3];f[e-1][e-1]=c[4];g=c[5];float h=c[6],i=c[7];s(0,0,e-1,e-1,h,i);System.out.print(Arrays.deepToString(f));}static int e;static float[][]f;static float g;static void s(int q,int r,int s,int t,float h,float i){if(s-q<2|t-r<2|q<0|r<0|s>=e|t>=e)return;float o,p;int m=(q+s)/2,n=(r+t)/2;f[m][n]=(float)(a(q,r,s,r,q,t,s,t)+random()*(i-h)-h);d(m,r,m-q,o=h*g,p=i*g);d(q,n,m-q,o,p);d(m,t,m-q,o,p);d(s,n,m-q,o,p);}static void d(int x,int y,int e,float h,float i){float o,p;f[x][y]=(float)(a(x,y-e,x+e,y,x,y+e,x-e,y)+random()*(i-h)-h);s(x-e,y-e,x,y,o=h*g,p=i*g);s(x,y-e,x+e,y,o,p);s(x-e,y,x,y+e,o,p);s(x,y,x+e,y+e,o,p);}static float a(int...j){float k=0,l=0;for(int d=0;d<j.length;d+=2){if(j[d]<0|j[d+1]<0|j[d]>=e|j[d+1]>=e)continue;l++;k+=f[j[d]][j[d+1]];}return k/l;}}

Program that is indented and displays the map:

import java.util.*;
import java.awt.image.*;
import java.awt.*;
import javax.swing.*;
import static java.lang.Math.*;

class D{

    public static void main(String[]a){
        int b=a.length,d=0;
        float[]c=new float[b];
        for(;d<b;){
            c[d]=Float.parseFloat(a[d++]);
        }
        e=(int)(pow(2,c[0])+1);
        f=new float[e][e];
        f[0][0]=c[1];
        f[0][e-1]=c[2];
        f[e-1][0]=c[3];
        f[e-1][e-1]=c[4];
        g=c[5];
        float h=c[6],i=c[7];
        s(0,0,e-1,e-1,h,i);
        showImage(f);
    }

    static int e;
    static float[][]f;
    static float g;

    static void s(int q,int r,int s,int t,float h,float i){
        if(s-q<2|t-r<2|q<0|r<0|s>=e|t>=e)
            return;
        float o,p;
        int m=(q+s)/2,n=(r+t)/2;
        f[m][n]=(float)(a(q,r,s,r,q,t,s,t)+random()*(i+h)-h);
        d(m,r,m-q,o=h*g,p=i*g);
        d(q,n,m-q,o,p);
        d(m,t,m-q,o,p);
        d(s,n,m-q,o,p);
    }

    static void d(int x,int y,int e,float h,float i){
        float o,p;
        f[x][y]=(float)(a(x,y-e,x+e,y,x,y+e,x-e,y)+random()*(i-h)+h);
        s(x-e,y-e,x,y,o=h*g,p=i*g);
        s(x,y-e,x+e,y,o,p);
        s(x-e,y,x,y+e,o,p);
        s(x,y,x+e,y+e,o,p);
    }

    static float a(int...j){
        float k=0,l=0;
        for(int d=0;d<j.length;d+=2){
            if(j[d]<0|j[d+1]<0|j[d]>=e|j[d+1]>=e)
                continue;
            l++;
            k+=f[j[d]][j[d+1]];
        }
        return k/l;
    }

    public static void showImage(float[][] f){
        float maxHeight = Float.MIN_VALUE;
        float minHeight = Float.MAX_VALUE;
        for (float[] row : f){
            for (float height : row){
                if (height > maxHeight){
                    maxHeight = height;
                }
                if (height < minHeight){
                    minHeight = height;
                }
            }
        }
        int e = f.length;
        BufferedImage image = new BufferedImage(e, e, BufferedImage.TYPE_INT_RGB);
        for (int x = 0; x < e; x++){
            for (int y = 0; y < e; y++){
                Color color = Color.getHSBColor((float)((f[x][y] - minHeight)/(maxHeight - minHeight)), 1, 1);
                image.setRGB(x,y,color.getRGB());
            }
        }
        JFrame frame = new JFrame("Picture");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new JComponent(){

            @Override
            public void paint(Graphics g){
                g.drawImage(image, 0, 0, getWidth(), getHeight(), null);
            }

        });
        frame.setVisible(true);
        frame.setBounds(0,0,e,e);
    }

}

Here is a function in Java to show a map:

public static void showImage(float[][] map){
    float maxHeight = Float.MIN_VALUE;
    float minHeight = Float.MAX_VALUE;
    for (float[] row : map){
        for (float height : row){
            if (height > maxHeight){
                maxHeight = height;
            }
            if (height < minHeight){
                minHeight = height;
            }
        }
    }
    int size = map.length;
    BufferedImage image = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB);
    for (int x = 0; x < size; x++){
        for (int y = 0; y < size; y++){
            Color color = Color.getHSBColor((float)((map[x][y] - minHeight)/(maxHeight - minHeight)), 1, 1);
            image.setRGB(x,y,color.getRGB());
        }
    }
    JFrame frame = new JFrame("Picture");
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.add(new JComponent(){

        @Override
        public void paint(Graphics g){
            g.drawImage(image, 0, 0, getWidth(), getHeight(), null);
        }

    });
    frame.setVisible(true);
    frame.setBounds(0,0,size,size);
}

All of these images have a size of 7. The 4 seeds are 5, 10, 15, and 20.

a and b are -10 and 10 respectively.

Roughness starts at .1 and increments by .1 up to 1.

OneTwoThreeFourFiveSixSevenEightNineTen

Terrain generating code coming soon!!!

Images coming soon!!!

\$\endgroup\$
  • \$\begingroup\$ Thank you very much! Could you perhaps provide a class around that with all the necessary imports so no big modification is needed? That would be awesome! \$\endgroup\$ – flawr Dec 23 '14 at 22:55
  • \$\begingroup\$ @flawr I'm working on it. \$\endgroup\$ – TheNumberOne Dec 23 '14 at 22:57
  • \$\begingroup\$ Just got it working, if you know how to do it, it would be great if you could make the window show up 'uncollapsed'. At least on my machine you have to draw it open every time you start it. Here is how I completed the class: pastebin.com/pRAMst4d \$\endgroup\$ – flawr Dec 23 '14 at 23:03
  • \$\begingroup\$ This looks awesome! I especially like the elegant way you are dealing with the boundaries where one vertice is missing=) \$\endgroup\$ – flawr Dec 24 '14 at 10:16
  • \$\begingroup\$ @flawr The window won't be collapsed when you open it now. \$\endgroup\$ – TheNumberOne Dec 24 '14 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.