Chapter 45

中点変位法

miku
miku
2021.11.15に更新

noise() はパーリンノイズというアルゴリズムが使用されており次の章で実装をするが、複雑なアルゴリズムなので、それより簡単な方法でノイズ関数を作っておきたい。

この章では中点変位法というアルゴリズムでノイズを作成する。

一次元

y座標が同じである2点を用意する。便宜上、点線を引いているが実際に線を引く必要はない。

2点の間に中点を用意する。このアルゴリズムでは中点を次々と追加していくのだが、このまま点同士を繋いでも直線にしかならない。

なので、前もって決めておいた h を利用する。中点の y の値を -h / 2 ~ h / 2 の範囲で移動する。

実際に移動した例。

新たに中点を作り、上下にランダムに移動する。ただし、hの値は前回の半分にする。点と点の間がある程度狭まったら、分割するのをやめて線で結ぶ。

let points, nexts;

function setup() {
  createCanvas(windowWidth, windowHeight);

  stroke(240);
  noFill();

  points = [];

  divide({ x: 0, y: height / 2 }, { x: width, y: height / 2 }, 100);
  points.push({ x: width, y: height / 2 });

  let px = points[0].x;
  let py = points[0].y;
  for (let i = 1; i < points.length; i++) {
    const x = points[i].x;
    const y = points[i].y;

    line(px, py, x, y);

    px = x;
    py = y;
  }
}

function divide(a, b, h) {
  if (abs(a.x - b.x) < 1) {
    points.push({ x: a.x, y: a.y });
    return;
  }

  const c = lerp2d(a, b, 0.5);
  c.y += random(-h, h);

  divide(a, c, h / 2);
  divide(c, b, h / 2);
}

function lerp2d(a, b, t) {
  return { x: lerp(a.x, b.x, t), y: lerp(a.y, b.y, t) };
}

二次元の中点変位法

const minSize = 1;
const maxSize = 256; // 2の倍数にする
const min = 0;
const max = 1;

function setup() {
  createCanvas(windowWidth, windowHeight);
  noStroke();

  generateHeightmap(0, 0, maxSize, random(), random(), random(), random());
}

function generateHeightmap(x, y, size, tl, tr, bl, br) {
  if (size === minSize) {
    const value = (tl + tr + bl + br) / 4;
    fill(value * 256);
    rect(x, y, minSize, minSize);
  } else {
    let midPoint = (tl + tr + bl + br) / 4 + getRandomHeight(size);
    if (midPoint < min) {
      midPoint = min;
    }
    if (max < midPoint) {
      midPoint = max;
    }
    const top = (tl + tr) / 2;
    const bottom = (bl + br) / 2;
    const left = (tl + bl) / 2;
    const right = (tr + br) / 2;

    size /= 2;
    generateHeightmap(x, y, size, tl, top, left, midPoint);
    generateHeightmap(x + size, y, size, top, tr, midPoint, right);
    generateHeightmap(x, y + size, size, left, midPoint, bl, bottom);
    generateHeightmap(x + size, y + size, size, midPoint, right, bottom, br);
  }
}

function getRandomHeight(value) {
  return ((random() - 0.5) * value) / maxSize;
}

中点変位法でのノイズ利用例

ノイズの滑らかさを利用してマップ生成に利用されることもある。代表的なのはマインクラフトなどだ。

const minSize = 1;
const maxSize = 256; // 2の倍数にする
const space = 2;
let noise2d;

function setup() {
  createCanvas(windowWidth, windowHeight);
  rectMode(CENTER);
  noStroke();

  noise2d = [];
  for (let i = 0; i < maxSize; i++) {
    noise2d[i] = [];
  }

  generateHeightmap(0, 0, maxSize, random(), random(), random(), random());

  for (let y = 0; y < maxSize; y++) {
    for (let x = 0; x < maxSize; x++) {
      const v = noise2d[y][x];
      if (v <= 0.325) {
        fill("#5e539e");
      } else if (v <= 0.5) {
        fill("#5584c5");
      } else if (v <= 0.53125) {
        fill("#7ac1a5");
      } else if (v <= 0.5625) {
        fill("#a2d7a4");
      } else if (v <= 0.6875) {
        fill("#d3d599");
      } else if (v <= 0.875) {
        fill("#808080");
      } else {
        fill("#fff");
      }

      rect(x * space, y * space, space, space);
    }
  }
}

function generateHeightmap(x, y, size, tl, tr, bl, br) {
  if (size === minSize) {
    const value = (tl + tr + bl + br) / 4;
    noise2d[y][x] = value;
  } else {
    let midPoint = (tl + tr + bl + br) / 4 + getRandomHeight(size);
    midPoint = constrain(midPoint, 0, 1);
    const top = (tl + tr) / 2;
    const bottom = (bl + br) / 2;
    const left = (tl + bl) / 2;
    const right = (tr + br) / 2;

    size /= 2;
    generateHeightmap(x, y, size, tl, top, left, midPoint);
    generateHeightmap(x + size, y, size, top, tr, midPoint, right);
    generateHeightmap(x, y + size, size, left, midPoint, bl, bottom);
    generateHeightmap(x + size, y + size, size, midPoint, right, bottom, br);
  }
}

function getRandomHeight(value) {
  return ((random() - 0.5) * value) / maxSize;
}