3
\$\begingroup\$

I wrote a small JavaScript implementation of the Diamond-Square height map/texture algorithm and the result is much more industrial-looking than I expected. I can trace a diamond pattern throughout (maybe I should have expected that given the name? 😉 ).

Any idea what I could be doing wrong?

A screenshot of my result

Here's the code I'm using:

const textureCanvas = document.getElementById('texture');
const ctx = textureCanvas.getContext('2d');

const levelInput = document.getElementById('level');
const topLeftHeightInput = document.getElementById('tl');
const topRightHeightInput = document.getElementById('tr');
const bottomLeftHeightInput = document.getElementById('bl');
const bottomRightHeightInput = document.getElementById('br');

levelInput.addEventListener('input', render);
topLeftHeightInput.addEventListener('input', render);
topRightHeightInput.addEventListener('input', render);
bottomLeftHeightInput.addEventListener('input', render);
bottomRightHeightInput.addEventListener('input', render);


render();

function render () {
  const level = Number(levelInput.value);
  const span = Math.pow(2,level) + 1;
  textureCanvas.width = span;
  textureCanvas.height = span;

  // initialize height data container
  const heightData = Array(span);
  for (let x = 0; x < span; x++) {
    heightData[x] = Array(span);
  }

  // compute heights via Diamond Square algorithm
  heightData[0][0] = Number(topLeftHeightInput.value);
  heightData[span - 1][0] = Number(topRightHeightInput.value);
  heightData[0][span - 1] = Number(bottomLeftHeightInput.value);
  heightData[span - 1][span - 1] = Number(bottomRightHeightInput.value);
  const maxHeight = Math.max(
    heightData[0][0],
    heightData[span - 1][0],
    heightData[0][span - 1],
    heightData[span - 1][span - 1],
    diamondSquare(heightData, level) // performs diamond square algorithm
  );

  // convert heights to image data for canvas
  const imageData = ctx.createImageData(span, span);
  const { data } = imageData;
  for (let y = 0; y < span; y++) {
    for (let x = 0; x < span; x++) {
      const brightness = Math.round(heightData[x][y] / maxHeight * 255);
      data[y * span * 4 + x * 4 + 0] = brightness; // r
      data[y * span * 4 + x * 4 + 1] = brightness; // g
      data[y * span * 4 + x * 4 + 2] = brightness; // b
      data[y * span * 4 + x * 4 + 3] = 255;        // a
    }
  }

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


// implementation based on visual description at:
// https://en.wikipedia.org/wiki/Diamond-square_algorithm#Visualization
// NOTE: mutates heightData.
function diamondSquare (heightData, level) {
  let maxHeight = 0;

  if (level < 1) {
    return maxHeight;
  }

  const interval = Math.pow(2, level);
  const half = Math.pow(2, level - 1);

  // diamond step
  for (let yOffset = 0; yOffset + 1 < heightData.length; yOffset += interval) {
    for (let xOffset = 0; xOffset + 1 < heightData.length; xOffset += interval) {
      heightData[xOffset + half][yOffset + half] = (
        heightData[xOffset + 0][yOffset + 0] +
        heightData[xOffset + half * 2][yOffset + 0] +
        heightData[xOffset + 0][yOffset + half * 2] +
        heightData[xOffset + half * 2][yOffset + half * 2]
      ) / 4 + Math.random() * interval;

      maxHeight = Math.max(
        maxHeight,
        heightData[xOffset + half][yOffset + half]
      );
    }
  }

  // square step
  for (let yOffset = 0; yOffset + 1 < heightData.length; yOffset += interval) {
    for (let xOffset = 0; xOffset + 1 < heightData.length; xOffset += interval) {
      const noTopCorner = yOffset <= 0;
      heightData[xOffset + half][yOffset + 0] = (
        (noTopCorner ? 0 : heightData[xOffset + half][yOffset - half]) +
        heightData[xOffset + half][yOffset + half] +
        heightData[xOffset + 0][yOffset + 0] +
        heightData[xOffset + half * 2][yOffset + 0]
      ) / (noTopCorner ? 3 : 4) + Math.random() * interval;
      const noBottomCorner = yOffset + half * 2 + 1 >= heightData.length;
      heightData[xOffset + half][yOffset + half * 2] = (
        heightData[xOffset + half][yOffset + half] +
        (noBottomCorner ? 0 : heightData[xOffset + half][yOffset + half * 3]) +
        heightData[xOffset + 0][yOffset + half * 2] +
        heightData[xOffset + half * 2][yOffset + half * 2]
      ) / (noBottomCorner ? 3 : 4) + Math.random() * interval;
      const noLeftCorner = xOffset <= 0;
      heightData[xOffset + 0][yOffset + half] = (
        heightData[xOffset + 0][yOffset + 0] +
        heightData[xOffset + 0][yOffset + half * 2] +
        (noLeftCorner ? 0 : heightData[xOffset - half][yOffset + half]) +
        heightData[xOffset + half][yOffset + half]
      ) / (noLeftCorner ? 3 : 4) + Math.random() * interval;
      const noRightCorner = xOffset + half * 2 + 1 >= heightData.length;
      heightData[xOffset + half * 2][yOffset + half] = (
        heightData[xOffset + half * 2][yOffset + 0] +
        heightData[xOffset + half * 2][yOffset + half * 2] +
        heightData[xOffset + half][yOffset + half] +
        (noRightCorner ? 0 : heightData[xOffset + half * 3][yOffset + half])
      ) / (noRightCorner ? 3 : 4) + Math.random() * interval;

      maxHeight = Math.max(
        maxHeight,
        heightData[xOffset + half][yOffset + half],
        heightData[xOffset + half][yOffset + 0],
        heightData[xOffset + half][yOffset + half * 2],
        heightData[xOffset + 0][yOffset + half],
        heightData[xOffset + half * 2][yOffset + half]
      );
    }
  }

  return Math.max(maxHeight, diamondSquare(heightData, level - 1));
}
  <h1>Diamond Square texturing</h1>
  <div id="inputs">
    <label>
      Level <input id="level" type="number" step="1" min="1" max="20" value="8">
    </label>
    <br/>
    <label>
      Top-left-height
      <input id="tl" type="number" step="0.1" min="0" max="20" value="2">
    </label>
    <br/>
    <label>
      Top-right-height
      <input id="tr" type="number" step="0.1" min="0" max="20" value="17">
    </label>
    <br/>
    <label>
      Bottom-left-height
      <input id="bl" type="number" step="0.1" min="0" max="20" value="4">
    </label>
    <br/>
    <label>
      Bottom-right-height
      <input id="br" type="number" step="0.1" min="0" max="20" value="9">
    </label>
  </div>
  <canvas id="texture"></canvas>
  

\$\endgroup\$
2
\$\begingroup\$

Your code cites the Wikipedia article, which in turn has a section called "Artifacts and Extensions" that observes a potential problem:

The diamond-square algorithm was analyzed by Gavin S. P. Miller in SIGGRAPH 1986 who described it as flawed because the algorithm produces noticeable vertical and horizontal "creases" due to the most significant perturbation taking place in a rectangular grid.

And a solution:

The grid artifacts were addressed in a generalized algorithm introduced by J.P. Lewis. In this variant the weights on the neighboring points are obtained by solving a small linear system motivated by estimation theory, rather than being fixed.

Some of these artifacts are present in the example image on Wikipedia. Here's the original image & a copy where I've flagged some of the artifacts. I marked 'high artifacts' in yellow & 'low artifacts' in pink:

enter image description here enter image description here

I did the flagging by free hand, so they might be off by a few pixels here & there, but we can noticed some trends: the artifacts tend to manifest as horizontal & vertical lines & the lines tend to align with each in a grid pattern. Your are also grid aligned, but tend to show up as lines cutting at 45 degrees. So I think there's something else going on here. If I understand your code correctly, it looks like you're doing a diamond step & a square step for each level - my understanding is that the diamond and square steps are supposed to be performed alternately.

\$\endgroup\$
  • \$\begingroup\$ note: at the moment I can't add illustrations describing the problem or solution. Assuming no one else adds them for me, I'll try to add them in later today. \$\endgroup\$ – Pikalek Nov 20 '17 at 16:14
  • \$\begingroup\$ Are you sure I even implemented the wikipedia version correctly? None of the images I google for diamond square texture resemble my result very closely. And thanks for the help! If you're able to add illustrations I'd appreciate it. \$\endgroup\$ – Ben Wiley Nov 20 '17 at 19:12
  • \$\begingroup\$ I've revised my answer to include some illustrations, and some conjecture about your problem. I also removed some stuff that didn't apply to this problem - I had some info that applied to certain implementation of value noise, but not diamond-square - sorry for the confusion. \$\endgroup\$ – Pikalek Nov 20 '17 at 23:46

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.