int step_size = (some number, probably GCD(array_x, array_y))   // I used array_x = 2 * step_size, array_y = step_size

while ( step_size >= 1 ) do:
    square_step across entire array
    diamond_step across entire array
done

for x from 0 to array_x by step_size do:
    for y from 0 to array_y by step_size do:
        (square step or diamond step, as appropriate)

package midpoint;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;


public class HeightField {
       
        public enum WrapMode {
                Bicylindrical {
                        public int index ( int x, int y, int width, int height ) {
                                x %= width;
                                if ( x < 0 ) {
                                        x += width;
                                }
                                y %= height;
                                if ( y < 0 ) {
                                        y += height;
                                }
                                return y * width + x;
                        }
                },
                /**
                 * In the X direction, map as if the world were a cylinder.
                 * In the Y direction, if we overflow above, flow down on the opposite
                 * side; if we overflow below, flow up on the opposite side.
                 * Do the Y direction first so we only need to normalise width once.       
                 */
                Spherical {
                        public int index ( int x, int y, int width, int height ) {
                                // Y / Height
                                if ( y >= height ) {
                                        // height, minus the amount we exceeded height by
                                        y = height - (y % height);
                                        x += width / 2;
                                } else if ( y < 0 ) {
                                        // 0, plus the amount we were "too low" by
                                        y = - ( y % height );
                                        x += width / 2;
                                }
                                if ( y == height ) {
                                        y = height - 1;
                                }
                               
                                // X / Width
                                x %= width;
                                if ( x < 0 ) {
                                        x += width;
                                }
                               
                                return y * width + x;
                        }
                };
               
                public abstract int index ( int x, int y, int width, int height );
        }

        protected final int width, height;
        protected final WrapMode wrap;
       
        /**
         * "Two-dimensional" array, in row-major order.
         */
        protected final int[] array;
       
        public HeightField ( int width, int height, WrapMode wrap ) {
                this.width = width;
                this.height = height;
                this.wrap = wrap;
                array = new int[width * height];
        }

        public int get ( int x, int y ) {
                return array [ wrap.index ( x, y, width, height ) ];
        }
       
        public void set ( int x, int y, int value ) {
                array [ wrap.index ( x, y, width, height ) ] = value;
        }
       
        public int getWidth() {
                return width;
        }
       
        public int getHeight() {
                return height;
        }
       
        public void writeImage ( String fileName ) throws IOException {
                writeImage ( new File ( fileName ) );
        }
       
        public void writeImage ( File file ) throws IOException {
                BufferedImage img = new BufferedImage (
                                width,
                                height,
                                BufferedImage.TYPE_INT_RGB
                );

                for ( int y = 0; y < height; ++y ) {
                        for ( int x = 0; x < width; ++x ) {
                                int h = clamp ( get(x, y), 0, 255 );
                                int rgb;
                                if ( h < 128 ) {
                                        rgb = (h << 16) | (h << 8) | 255;
                                        /*
                                } else if ( h < 128 ) {
                                        rgb = (h + 30) << 16 | (h + 15) << 8 | h;
                                } else if ( h < 196 ) {
                                        rgb = (h - 128) << 16 | h << 8;
                                         */
                                } else {
                                        rgb = (h << 16) | (h << 8) | h;
                                }
                                img.setRGB (
                                                //( x + width / 2 ) % width,
                                                x,
                                                y,
                                                rgb
                                );
                        }
                }

                boolean written = ImageIO.write (
                                img,
                                "BMP",
                                file
                );
               
                if ( !written ) {
                        throw new IOException ( "Failed to write image!" );
                }
        }


       
        /**
         *
         */
        protected void normalize ( int bottom, int top ) {
                int min = top, max = bottom;
                int range = top-bottom;
                for ( int i = 0, j = width * height; i < j; ++i ) {
                        int h = array[i];
                        min = Math.min(min, h);
                        max = Math.max(max, h);
                }
               
                // Now we know that the entire heightmap lies in [min,max].
                // We re-scale so that min->bottom, max->top
                float difference = max - min;
                for ( int i = 0, j = width * height; i < j; ++i ) {
                        int h = array[i];
                        array[i] = Math.round ( range * ( h - min ) / difference );
                }
        }
       
        protected static int clamp ( int value, int min, int max ) {
                if ( value < min ) {
                        return min;
                }
                if ( value > max ) {
                        return max;
                }
                return value;
        }
}

package midpoint;

import java.io.IOException;
import java.text.NumberFormat;
import java.util.Random;
import java.util.Scanner;

import midpoint.HeightField.WrapMode;

public class Main {

        public static void main(String[] args) throws IOException {
               
                // Configuration
                final int HEIGHT_MAX = 255;
                final int L = 512;
                final int MX = 2 * L;
                final int MY = L;
               
               
                HeightField hf = new HeightField ( MX, MY, WrapMode.Spherical );

                long seed;
                Scanner in = new Scanner ( System.in );
                System.out.println ( "Enter a seed value (0 to "+Long.MAX_VALUE+")" );
                seed = in.nextLong();
               
                NumberFormat nf = NumberFormat.getInstance();
                nf.setMaximumFractionDigits(1);
                nf.setMinimumFractionDigits(1);

                for ( float persist = 0.1f; persist < 1; persist += 0.1f ) {
                        String persistString = nf.format ( persist );
                               
                        long start = System.currentTimeMillis();
                        midpointDisplacement ( hf, L, MX, MY, HEIGHT_MAX, persist, seed );
                        hf.normalize ( 0, 256 );
                        hf.writeImage ( "hf_"+persistString+".bmp" );
                        long end = System.currentTimeMillis();

                        System.out.println (
                                        "DONE [persist = "+persistString+"] " +
                                        "("+(end-start)+" milliseconds)"
                        );
                }
        }

        protected static void midpointDisplacement (
                        final HeightField hf,
                        final int L,
                        final int MX,
                        final int MY,
                        int range,
                        final float persist,
                        final long seed
        )
        {
                /*
                 * NOTE:
                 * A is (x1, y1)
                 * B is (x2, y2)
                 * A,B,C,D are the original "corner" points
                 *         
                 *          G
                 *
                 *      B       D
                 *     
                 *  H       E       I
                 *     
                 *      A       C
                 *     
                 *          F
                 */
               
               
                Random r = new Random(seed);

                for ( int y = 0; y < MY; y += L ) {
                        for ( int x = 0; x < MX; x += L ) {
                                hf.set ( x, y, r.nextInt ( 256 ) );
                        }
                }
               
                int step = L;
                int halfStep = L / 2;
                int x2, y2, midx, midy;

                while ( step >= 1 ) {
                        // Diamond step across entire array...
                        for ( int y1 = 0; y1 < MY; y1 += step ) {
                                for ( int x1 = 0; x1 < MX; x1 += step ) {
                                        x2 = x1 + step;
                                        y2 = y1 + step;
                                        midx = x1 + halfStep;
                                        midy = y1 + halfStep;

                                        final int sum =
                                                hf.get(x1,y1) + hf.get(x1,y2) +
                                                hf.get(x2,y1) + hf.get(x2,y2);

                                        hf.set (
                                                        midx,
                                                        midy,
                                                        sum / 4 + perturb ( r, range )
                                        );
                                }
                        }

                        // Square step across entire array...
                        for ( int y1 = 0; y1 < MY; y1 += step ) {
                                for ( int x1 = 0; x1 < MX; x1 += step ) {
                                        x2 = x1 + step;
                                        y2 = y1 + step;
                                        midx = x1 + halfStep;
                                        midy = y1 + halfStep;

                                        /*      x1  mx  x2
                                         *          G
                                         *
                                         *      B   4   D       y2
                                         *     
                                         *  H   1   E   2   I   midy
                                         *     
                                         *      A   3   C       y1
                                         *     
                                         *          F
                                         */
                                        int A = hf.get ( x1, y1 );
                                        int B = hf.get ( x1, y2 );
                                        int C = hf.get ( x2, y1 );
                                        int D = hf.get ( x2, y2 );
                                        int E = hf.get ( midx, midy );
                                        int F = hf.get ( midx, y1 - halfStep );
                                        int G = hf.get ( midx, y2 + halfStep );
                                        int H = hf.get ( x1 - halfStep, midy );
                                        int I = hf.get ( x2 + halfStep, midy );

                                        hf.set ( x1, midy, (A+B+E+H) / 4 ); // 1
                                        hf.set ( x2, midy, (C+D+E+I) / 4 ); // 2
                                        hf.set ( midx, y1, (A+C+E+F) / 4 ); // 3
                                        hf.set ( midx, y2, (B+D+E+G) / 4 ); // 4
                                }
                        }

                        // Prepare for next iteration...
                        range *= persist;
                        step /= 2;
                        halfStep /= 2;
                }
        }

        protected static int perturb ( Random r, int range ) {
                if ( range == 0 ) return 0;
                return r.nextInt ( range * 2 ) - range;
        }
}