Diamond-Square implementation produces too high values

Question

I have implemnted a Diamond-Square function, which produces a heightmap. The implementation seems to work correctly at first glance.

Those are only two examples but one can already see that the output values seem to be overall pretty high. There are only few really dark values. i. E. if you look at the heightmaps (produced by diamond square) in this paper you can see that they are not as homogeneous as mine. There is a lot more offset between different regions. There are regions which look like craters.

I was not able to figure out if the reason for this behaviour is wrong parametrization or implementation. Although example implementations on the web do vary a little I think I got the basic idea.

I am working on a flat typed array. The parameters I am passing to the function are:

• sideLength
  • As I have a flat array representing a 2D matrix I am passing the grids side length for further calculations. I pass a value of 257 here.
• maxHeight
  • The highest output value possible. I am passing 255 here, because I am later using the output in order to render the heightmap on a canvas.
• roughness
  • This is a offset value I am using in the square step in order to produce more random height offsets. Here I usually take a value around 50 here.

I am calling the Heightmap function in order to get the output:

/**
 * Creates a heightmap based on parameters passed.
 * @param {number} sideLength - Side length of a the resulting grid array. Diamond-Square can only have a size (2^n)+1.
 * @param {number} maxHeight - Max height value for the heightmap's values.
 * @param {number} roughness - A factor which is used as offset value for the heightmap. Defines the roughness of a heightmap.
 * @returns {Float32Array} - A flat `Float32Array` representing a 2D-grid with size `sideLength * sideLength`.
 */
static HeightMap(sideLength, maxHeight, roughness) {

    const n = Math.log(sideLength - 1) / Math.log(2);
    if (n < 0 || n % 1 != 0) {
        throw "Invalid side length in Diamond Square: Side Length has to be in range of `(2^n) + 1`.";
    }

    let gridArray = new Float32Array(sideLength * sideLength);
    this._initGrid(gridArray, sideLength, maxHeight);
    this._seed(gridArray, sideLength, roughness);

    return gridArray;
}

Here first the "grid" is being initiated:

/**
 * Sets the initial corner values for a Diamond-Square grid.
 * @param {Float32Array} gridArray - An `Float32Array` with its values (ideally) set to `0`.
 * @param {number} sideLength - Side length of a the resulting grid array. Diamond-Square can only have a size `(2^n)+1`.
 * @param {number} maxHeight - Max height value for the heightmap's values.
 * @returns {Float32Array} - A flat `Float32Array` representing a 2D-grid with its NW, NE, SE and SW values initialized.
 */
static _initGrid(gridArray, sideLength, maxHeight) {

    gridArray[0] = MathHelper.RandomInt(0, maxHeight); // NW
    gridArray[sideLength - 1] = MathHelper.RandomInt(0, maxHeight); // NE
    gridArray[sideLength * sideLength - 1] = MathHelper.RandomInt(0, maxHeight); // SE
    gridArray[sideLength * sideLength - sideLength] = MathHelper.RandomInt(0, maxHeight); // SW

    return gridArray;
}

Afterwards the HeightMap function calls _seed which is basically the Diamond-Square loop:

/**
 * Performs the Diamond Square (aka. Midpoint displacement) algorithm on a given flat TypedArray.
 * @param {Float32Array} gridArray - An (Diamond-Square-initialized) `Float32Array`.
 * @param {number} sideLength - Side length of a the resulting grid array.
 * @param {number} roughness - A factor which is used as offset value for the heightmap. Defines the roughness of a heightmap.
 * @returns {Float32Array} - Returns a ready to use heightmap produced by the Diamond-Square algorithm.
 */
static _seed(gridArray, sideLength, roughness) {
    let step = Math.sqrt(gridArray.length) - 1;
    let size = Math.sqrt(gridArray.length) - 1;
    let currentRoughness = roughness;

    while (step / 2 >= 1) {

        let numSquares = (Math.pow(size, 2)) / (Math.pow(step, 2));
        let perRowSquares = Math.floor(Math.sqrt(numSquares));
        for (let i = 0; i < perRowSquares; i++) {
            for (let j = 0; j < perRowSquares; j++) {
                const nwIndex = this._getNWIndex(i, j, step, sideLength);
                const cornerValues = this._getCornerValues(nwIndex, gridArray, sideLength, step);
                this._diamondStep(nwIndex, cornerValues, gridArray, sideLength, step, currentRoughness);
                this._squareStep(nwIndex, cornerValues, gridArray, sideLength, step, currentRoughness);
            }
        }

        currentRoughness /= 2.0;
        step /= 2;
    }

    return gridArray;
}

Note I am calculating position indices based on the index of the current north west index. For that purpose I have a function:

/**
 * Returns the array index for the north-west value for the current step.
 * @param {number} i - Current row, I guess.
 * @param {number} j - Current column, I guess.
 * @param {number} stepSize - Current step size.
 * @param {number} sideLength - Grid's side length.  
 * @returns {number} - Returns the index for current north-west value.
 */
static _getNWIndex(i, j, stepSize, sideLength) {
    return (i * (stepSize * sideLength)) + j * stepSize;
}

Because all four corner values are used in the diamond and in the square step I have a function for that too:

/**
 * Return an array holding the north-west, north-east, south-west and south-east values for the current step.
 * @param {number} nwIndex - North-West index for current step. 
 * @param {Float32Array} gridArray - The corner values for the current step.  
 * @param {number} sideLength - Grid's side length. 
 * @param {number} stepSize - Current step size.  
 * @returns {Float32Array} - Returns the typed array the function of operating on.
 */
static _getCornerValues(nwIndex, gridArray, sideLength, stepSize) {
    return [
        gridArray[nwIndex], // NW
        gridArray[nwIndex + stepSize], // NE
        gridArray[nwIndex + stepSize * sideLength], // SW
        gridArray[nwIndex + stepSize + stepSize * sideLength] // SE
    ];
}

Last but not least I have the _diamondStep and the _sqaureStep:

/**
 * Performs the Diamond Step by setting the center value for the current step.
 * @param {number} nwIndex - North-West index for current step.
 * @param {number[]} cornerValues - The corner values for the current step.
 * @param {Float32Array} gridArray - Array holding heightmap data. Function will write to this array.
 * @param {number} sideLength - Grid's side length. 
 * @param {number} stepSize - Current step size.
 * @returns {Float32Array} - Returns the typed array the function of operating on.
 */
static _diamondStep(nwIndex, cornerValues, gridArray, sideLength, stepSize, roughness) {

    // Center point. Calculated from "East - `stepSize / 2`"
    gridArray[(((nwIndex + stepSize * sideLength) + stepSize) - (stepSize * sideLength) / 2) - stepSize / 2]
        = (cornerValues[0] + cornerValues[1] + cornerValues[2] + cornerValues[3]) / 4 + (roughness * MathHelper.RandomInt(-1, 1));

    return gridArray;
}

/**
 * Performs the Square Step by setting the north, east, south and west values for the current step.
 * @param {number} nwIndex - North-West index for current step.
 * @param {number[]} cornerValues - The corner values for the current step. 
 * @param {Float32Array} gridArray - Array holding heightmap data. Function will write to this array. 
 * @param {number} sideLength - Grid's side length.  
 * @param {number} stepSize - Current step size. 
 * @param {number} roughness - Roughness factor for the current step.
 * @returns {Float32Array} - Returns the typed array the function of operating on.
 */
static _squareStep(nwIndex, cornerValues, gridArray, sideLength, stepSize, roughness) {

    const average = (cornerValues[0] + cornerValues[1] + cornerValues[2] + cornerValues[3]) / 4;
    const value = average + (roughness * MathHelper.RandomInt(-1, 1));

    // N
    gridArray[nwIndex + (stepSize / 2)] = value;
    // E
    gridArray[((nwIndex + stepSize * sideLength) + stepSize) - (stepSize * sideLength) / 2] = value;
    // S
    gridArray[(nwIndex + stepSize * sideLength) + stepSize / 2] = value;
    // W
    gridArray[(nwIndex + stepSize * sideLength) - (stepSize * sideLength) / 2] = value;

    return gridArray;
}

As I mentioned before the implementation seems to work. Still I wonder if the overall "whiteness" is caused by wrong parametrization or worng implementation?

Here is a working fiddle:

function HeightMap(sideLength, maxHeight, roughness) {

  const n = Math.log(sideLength - 1) / Math.log(2);
  if (n < 0 || n % 1 != 0) {
    throw "Invalid side length in Diamond Square: Side Length has to be in range of `(2^n) + 1`.";
  }

  let gridArray = new Float32Array(sideLength * sideLength);
  _initGrid(gridArray, sideLength, maxHeight);
  _seed(gridArray, sideLength, roughness);

  return gridArray;
}


function _initGrid(gridArray, sideLength, maxHeight) {

  gridArray[0] = RandomInt(0, maxHeight); // NW
  gridArray[sideLength - 1] = RandomInt(0, maxHeight); // NE
  gridArray[sideLength * sideLength - 1] = RandomInt(0, maxHeight); // SE
  gridArray[sideLength * sideLength - sideLength] = RandomInt(0, maxHeight); // SW

  return gridArray;
}


function _seed(gridArray, sideLength, roughness) {
  let step = Math.sqrt(gridArray.length) - 1;
  let size = Math.sqrt(gridArray.length) - 1;
  let currentRoughness = roughness;

  while (step / 2 >= 1) {

    let numSquares = (Math.pow(size, 2)) / (Math.pow(step, 2));
    let perRowSquares = Math.floor(Math.sqrt(numSquares));
    for (let i = 0; i < perRowSquares; i++) {
      for (let j = 0; j < perRowSquares; j++) {
        const nwIndex = _getNWIndex(i, j, step, sideLength);
        const cornerValues = _getCornerValues(nwIndex, gridArray, sideLength, step);
        _diamondStep(nwIndex, cornerValues, gridArray, sideLength, step, currentRoughness);
        _squareStep(nwIndex, cornerValues, gridArray, sideLength, step, currentRoughness);
      }
    }

    currentRoughness /= 2.0;
    step /= 2;
  }

  return gridArray;
}


function _diamondStep(nwIndex, cornerValues, gridArray, sideLength, stepSize, roughness) {
  gridArray[(((nwIndex + stepSize * sideLength) + stepSize) - (stepSize * sideLength) / 2) - stepSize / 2] =
    (cornerValues[0] + cornerValues[1] + cornerValues[2] + cornerValues[3]) / 4 + (roughness * RandomInt(-1, 1));

  return gridArray;
}

function _squareStep(nwIndex, cornerValues, gridArray, sideLength, stepSize, roughness) {

  const average = (cornerValues[0] + cornerValues[1] + cornerValues[2] + cornerValues[3]) / 4;
  const value = average + (roughness * RandomInt(-1, 1));

  // N
  gridArray[nwIndex + (stepSize / 2)] = value;
  // E
  gridArray[((nwIndex + stepSize * sideLength) + stepSize) - (stepSize * sideLength) / 2] = value;
  // S
  gridArray[(nwIndex + stepSize * sideLength) + stepSize / 2] = value;
  // W
  gridArray[(nwIndex + stepSize * sideLength) - (stepSize * sideLength) / 2] = value;

  return gridArray;
}

function _getCornerValues(nwIndex, gridArray, sideLength, stepSize) {
  return [
    gridArray[nwIndex], // NW
    gridArray[nwIndex + stepSize], // NE
    gridArray[nwIndex + stepSize * sideLength], // SW
    gridArray[nwIndex + stepSize + stepSize * sideLength] // SE
  ];
}

function _getNWIndex(i, j, stepSize, sideLength) {
  return (i * (stepSize * sideLength)) + j * stepSize;
}

function GenerateIterations(max) {
  let iterations = [];
  for (let n = 0; n < max; n++) {
    iterations.push(Math.pow(2, n) + 1);
  }
  return iterations;
}

function Grayscale(canvasName, data, rows, cols) {
  let canvas = document.getElementById(canvasName);
  let ctx = canvas.getContext("2d");

  let imageData = ctx.createImageData(cols, rows);

  for (let i = 0; i < data.length; i++) {
    const color = data[i];
    imageData.data[i * 4] = color;
    imageData.data[i * 4 + 1] = color;
    imageData.data[i * 4 + 2] = color;
    imageData.data[i * 4 + 3] = 255;
  }

  ctx.putImageData(imageData, 0, 0);
}

function RandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

let terrainGrid = HeightMap(257, 255, 50);
Grayscale('grayscaleCanvas', terrainGrid, 257, 257);

.greyscaleCanvas {
  border: solid 1px black;
}

<canvas id="grayscaleCanvas" class="greyscaleCanvas" width="257px" height="257px"></canvas>

Answer 1

So I reworked the code a bit based on my understanding of how this algorithm works. It's entirely possible this still isn't working correctly, but I think this code will be a bit easier for you to work with regardless.

I think I also found a few issues in your algorithm based on my understanding of the diamond-square steps I read on Wikipedia:

function HeightMap(sideLength, maxHeight, roughness) {

  const n = Math.log(sideLength - 1) / Math.log(2);
  if (n < 0 || n % 1 != 0) {
    throw "Invalid side length in Diamond Square: Side Length has to be in range of `(2^n) + 1`.";
  }

  let gridArray = new Array(sideLength);
  for (var i = 0; i < gridArray.length; i++) {
    gridArray[i] = new Float32Array(sideLength);
    }
  gridArray = _initGrid(gridArray, sideLength, maxHeight);
    gridArray = _seed(gridArray, sideLength, roughness);
  return gridArray;
}


function _initGrid(gridArray, sideLength, maxHeight) {

  gridArray[0][0] = RandomInt(0, maxHeight); // NW
  gridArray[0][sideLength-1] = RandomInt(0, maxHeight); // NE
  gridArray[sideLength-1][sideLength-1] = RandomInt(0, maxHeight); // SE
  gridArray[sideLength-1][0] = RandomInt(0, maxHeight); // SW

  return gridArray;
}


function _seed(gridArray, sideLength, roughness) {
  let step = sideLength - 1;
  let size = sideLength - 1;
  let currentRoughness = roughness;

    let run_num = 0
  while (step / 2 >= 1) {
    console.log(run_num)
        run_num = run_num + 1
    let numSquares = Math.pow(size, 2) / Math.pow(step, 2);
    let perRowSquares = Math.floor(Math.sqrt(numSquares));
    for (let i = 0; i < perRowSquares; i++) {
      for (let j = 0; j < perRowSquares; j++) {
        row = i*step
        col = j*step
        const squareCornerValues = _getSquareCornerValues(gridArray, row, col, step)
        gridArray = _diamondStep(squareCornerValues, row, col, step, gridArray, currentRoughness);
        gridArray = _squareStep(row, col, step, gridArray, sideLength, currentRoughness)
       // _squareStep(diamondMidPoints, gridArray, step, currentRoughness);
      }
    }

    currentRoughness /= 2.0;
    step /= 2;
  }
  return gridArray;
}


function _diamondStep(squareCornerValues, i, j, step, gridArray, currentRoughness) {
  gridArray[row+step/2][col+step/2] = (squareCornerValues[0] + squareCornerValues[1] + squareCornerValues[2] + squareCornerValues[3] ) / 4  + (currentRoughness * RandomInt(-1, 1));
  return gridArray;
}

function _squareStep(row, col, step, gridArray, sideLength, currentRoughness) {

  let diamondMidPoints = [[row, col+step/2], //top
                                                [row+step/2, col], //left
                            [row+step, col+step/2], //right
                            [row+step/2, col+step] //bottom
                             ];
  for (let z = 0; z < diamondMidPoints.length; z++){
    corners = _get_diamond_corners(diamondMidPoints[z], step, sideLength, gridArray);
    gridArray[diamondMidPoints[z][0]][diamondMidPoints[z][1]] = (corners[0] + corners[1] + corners[2] + corners[3]) /4  + (currentRoughness * RandomInt(-1, 1));
  }

  return gridArray;
}

function _getSquareCornerValues(gridArray, row, col, step) {
  return [
    gridArray[row][col], // NW
    gridArray[row][col+step], // NE
    gridArray[row+step][col], // SW
    gridArray[row+step][col+step] // SE
  ];
}

function _get_diamond_corners(diamondMidPoints, step, sideLength, gridArray){
    row = diamondMidPoints[0];
  col = diamondMidPoints[1];
  top_coord = [(row  - step/2 + sideLength) % sideLength, col];
  left_coord = [row, (col - step/2 + sideLength) % sideLength];
  right_coord = [row, (col + step/2 + sideLength) % sideLength];
  bottom_coord = [(row + step/2 + sideLength) % sideLength, col];
  return [gridArray[top_coord[0]][top_coord[1]],
                gridArray[left_coord[0]][left_coord[1]],
          gridArray[right_coord[0]][right_coord[1]],
          gridArray[bottom_coord[0]][bottom_coord[1]]
             ];
}

function Grayscale(canvasName, data, rows, cols) {
  let canvas = document.getElementById(canvasName);
  let ctx = canvas.getContext("2d");

  let imageData = ctx.createImageData(cols, rows);

  for (let i = 0; i < data.length; i++) {
    const color = data[i];
    imageData.data[i * 4] = color;
    imageData.data[i * 4 + 1] = color;
    imageData.data[i * 4 + 2] = color;
    imageData.data[i * 4 + 3] = 255;
  }

  ctx.putImageData(imageData, 0, 0);
}

function RandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}


let terrainGrid = HeightMap(257, 255, 50);
terrainList = []
for (let q=0; q < 257; q++) {
  terrainList.push.apply(terrainList, terrainGrid[q])
}
Grayscale('grayscaleCanvas', terrainList, 257, 257);

The first thing I did was change this to use 2-dimensional array indexing. This made the averaging in the square step way easier (I was able to wrap around the edges of the matrix much more simply).

I also changed it to use the actual row and column values in the array where it was simpler instead of block coordinates.

I don't think you were initially calculating the square step correctly. The corners you were using were relevant to the diamond step, but you were just averaging those for the square step instead of finding the averages based on the calculated midpoint value and the relevant subset of corners (see the Wikipedia images on diamond square to see what I mean).

Here's a JSFiddle with everything, hope this is more what you want. (Note: if anything isn't done idiomatically, it's because I'm not great at Javascript): https://jsfiddle.net/z6so4xyc/15/