ランダム地形生成 Part1～パーリンノイズ

ランダム地形生成とは

ランダム地形生成は言葉の通り、人の手でゲーム世界を作るではなく
プログラムが勝手にそのゲーム世界を生成することです。
しかし、その生成結果は本当に全くランダムなのでしょうか？

実はそうでもありません。
全くランダムで生成すると、その結果は混乱しすぎとなり、極不自然に見えてしまいます。
つまり、何かの方法で周りの情報を考慮に含み、生成したものです。
なので、ランダムだと言いても、ただランダムで生成した訳でもありません。

最近この技術を使うゲームがどんどん出ていて（有名なのはMinecraftとか、Terarriaとか、Starboundとか）
私も興味でそれについてちょっと勉強しましたので、分かったことを共有したいと思います。
もちろん、ただこの技術を使いたいであれば
Unityのアセットストアに出来上がったアセットはいっぱいあるので、別に原理など分からなくてもいいです。
実現原理に興味ある方は続きを読んでいただければと思います。

以下は一部の効果図です。

ランダム地形生成のコアはハイトマップ

では、ランダム地形生成と言って、一体何を生成し、ゲームは何を元にその地形を表示するんでしょう。

答えはハイトマップです。

ハイトマップとはゲーム世界の座標とその座標にあるポイントの高さのマッピングです。

例えば、2D世界のハイトマップはx座標とその座標にあるポイントの高さ（y座標）のマッピングで、
y軸が高さとなっている3D世界の場合は(x, z)座標とその座標にあるポイントの高さ（y座標）のマッピングです。

ご覧の通りに、特定な軸が高さを表示する故で、ハイトマップの次元数は必ず世界の次元数より一つ少ないです。

画像で表示すると、1Dハイトマップはウェーブのようなグラフに見え、2Dハイトマップはグレースケールのイメージに見えます。

このような値の波動はノイズと呼ばれ、ノイズを生成する関数がノイズ関数です。
つまり、ランダム地形生成の本質はノイズ関数のアウトプットです。

パーリンノイズとは

自然な地形を生成出来るノイズは変化が柔らかなノイズです。
このようなノイズを生成出来るノイズ関数は色々あります。
有名なのはダイアモンドスクエアアルゴリズム（Diamond Square）、パーリンノイズアルゴリズム（Perlin Noise）とシンプレックスノイズアルゴリズム（Simplex Noise）。

ここで全部を説明するには文章が長くなるので、一番使われるパーリンノイズのみ説明していただきます。

一般的なノイズ生成と違って、パーリンノイズは一気に全座標の高さを直接に生成するではなく
一定数の座標にあるポイントの勾配をランダムで生成し、それから各座標周りの勾配を利用してその座標の高さを計算することです。

勾配というのは一定の方向に沿って高さの増やすスピードです。
つまり、その方向の険しさです。

直線の方程式で表示するとy = k * x + bのkです。

勾配が生成されるポイントの高さは0と設定され（b = 0）、ポイントの間の距離は同じになっています。

これから勾配が生成られるポイントをコントロールポイントと言います。

計算便利のため、隣のコントロールポイントの間の距離はすべて正規化されます。
つまり、隣のコントロールポイントの間の距離は1と設定します。
勾配自体の値は特に制限を設けていないですが、険しい過ぎると効果が不自然なので、一応は-1から1までに設定した方がいいと思います。
計算された座標の高さは常にその座標周りのコントロールポイントからの影響しか受けません。

1Dパーリンノイズについて

1Dパーリンノイズとは

まずは理解しやすい1Dパーリンノイズから説明します。
1Dノイズなので、勾配も1Dになっています。
1Dの世界で一つの座標周りのコントロールポイントは右側と左側それぞれ一つあるので
その座標の高さはその座標両側の勾配利用して計算されます。

1Dパーリンノイズは2Dゲームの地形生成以外、色んなところも使えます。
例えば、AIの歩き線路をリアルに見えるのに出発点から終点まで直線ではなく、適当な偏移値を入れるとか。

勾配の利用方法

勾配の利用方法は簡単に言えば、ステップが三つあります。

1. 高さを計算したい座標（xとします）とx両側にあるコントロールポイント（i0とi1とします）の間の符号付き相対距離（u0とu1とします）を算出します。
2. i0とi1にある勾配をg0とg1とし、u0とu1をそれぞれの直線方程式に代入して応じる勾配のみに従った場合のxの高さn0とn1計算します。
3. 補間関数（F(t)とします、補間関数の選定は人によって違いますが、一番簡単なのはF(t) = tです）を使ってn0とn1を補間します。
   原則はコントロールポイントから離れるほどそのコントロールポイントから受ける影響も少ないようにします。補間した結果（nxとします）はxの高さとなります。

各変数の計算式は以下となります。

上記の変数を図で表示すると、以下となります。

実装例

理論の後はコードを見ましょう。
以下は1Dパーリンノイズの実装例です。
分かりやすいのが一番の目的なので、最適化は殆ど行っておりません。
ノイズをもっと柔らかくさせるため
使う補間関数はパーリンさんの発表で推奨された五次多項式です。

float F(float t)
{
  return t * t * t * (t * (6 * t - 15) + 10);
}

private void CalculateNoise()
{		
  int ctrl_point_count = 6;
  float[] gradients = new float[ctrl_point_count];
		
  for (int ctrl_point = 0; ctrl_point < ctrl_point_count; ++ctrl_point)
  {
    gradients[ctrl_point] = GetRandomGradientForControlPoint(ctrl_point);
  }
		
  int scaling = 256;
  int noise_size = (ctrl_point_count - 1) * scaling;
  float[] noise = new float[noise_size];
  for (int t = 0; t < noise_size; ++t)
  {
    float x = (float)t / noise_size * (ctrl_point_count - 1);
    int i0 = (int)t;
    int i1 = i0 + 1;
		
    float g0 = gradients[i0];
    float g1 = gradients[i1];
		
    float u0 = x - i0;
    float u1 = u0 - 1;
    float n0 = g0 * u0;
    float n1 = g1 * u1;
		
    float nx = n0 * (1 - F(u0)) + n1 * F(u0);
    noise[t] = nx;
  }
}

2Dパーリンノイズについて

2Dパーリンノイズとは

1Dパーリンノイズの後に、2Dパーリンノイズについて説明します。

2Dが一見複雑ですが、実際は1Dとほっぼ変わっていません。ただ一つの座標の高さを計算するために使うコントロールポイントが二つ増えったたけです。

最初から言っていた通り、ある座標の高さは周りのコントロールポイントの勾配を利用して計算されます。
1Dの場合、周りのコントロールポイントというと、両側にある二つのコントロールポイントです。

では2Dの場合はどうでしょう。
答えは計算される座標四角のコントロールポイントです。

図で表示すれば以下となりますが
一つ注意すべきなのはこの図にある勾配の方向が示すのは1Dのような険しさではなく、高さの上がる方向です。
高さを色で表示すると（白さ＝高さ）、勾配ベクターの方向は黒から白への変更方向です。

険しさを示すのはその勾配ベクターの長さです。

勾配の利用方法

2Dバージョンの計算方法を簡単に言うと
座標の四角にある四つのコントロールポイントを二つ一組にして、1Dの方法で各組それぞれの結果を計算します。
最後は各組の計算結果を元にも一度1Dの方法で計算すれば最終結果となります。

具体的なステップは以下となります。

1. 高さを計算したい座標（(x, z)とします）とx四角にあるコントロールポイント（(i0, j0)、(i0, j1)、(i1, j0)、(i1, j1)とします）の間の符号付き相対距離（それぞれを(u0, v0)、(u0, v1)、(u1, v0)、(u1, v1)とします）を算出します。
2. 四つのコントロールポイントにある勾配をg00、g01、g10、g11とし、(u0, v0)、(u0, v1)、(u1, v0)、(u1, v1)のそれぞれの勾配との外積n00、n01、n10、n11を計算し、応じる勾配のみに従った場合の高さとします。
3. 補間関数F(t)を使ってn00とn10を補間し、n01とn11も補間します。補間した結果（nx0とnx1とします）をもう一度F(t)で補間した結果（nxzとします）は(x,y )の高さとなります。

計算公式は以下です。

1Dのように画像で表示すると以下となります。
注意すべきなのは(i0, j0)、(i0, j1)、(i1, j0)、(i1, j1)が青い線が示している座標であり
nx0、nx1、nxzは青い線が示しているところの高さであります。

実装例

1Dと一緒に2Dの実装例を提示します。

private float Interpolate(float from, float to, float percent, Func<float, float> f)
{
  float f_out = f(percent);
  return from * (1 - f_out) + to * f_out;
}

private float F(float t)
{
  return (float)(6.0 * Math.Pow(t, 5.0) - 15.0 * Math.Pow(t, 4.0) + 10 * Math.Pow(t, 3.0));
}

private void CalculateNoise()
{
  int ctrl_points_per_row = 6;
  int ctrl_points_per_column = 6;
  Vector<float>[,] gradients = new Vector<float>[ctrl_points_per_column, ctrl_points_per_row];

  for (var c = 0; c < ctrl_points_per_column; ++c)
    for (var r = 0; r < ctrl_points_per_row; ++r)
    {
      gradients[c, r] = GetRandomGradient();
    }

  int scaling = 256;
  int noise_size_x = (ctrl_points_per_row - 1) * scaling;
  int noise_size_z = (ctrl_points_per_column - 1) * scaling;
  float[,] noise = new float[noise_size_z, noise_size_x];

  for (int scaled_z = 0; scaled_z < noise_size_z; ++scaled_z)
  {
    float z = (float)scaled_z / noise_size_z * (ctrl_points_per_column - 1);

    for (int scaled_x = 0; scaled_x < noise_size_x; ++scaled_x)
    {
      float x = (float)scaled_x / noise_size_x * (ctrl_points_per_row - 1);

      int i0 = (int)x;
      int j0 = (int)y;
      int i1 = i0 + 1;
      int j1 = j0 + 1;

      var g00 = gradients[i0, j0];
      var g10 = gradients[i1, j0];
      var g01 = gradients[i0, j1];
      var g11 = gradients[i1, j1];

      float u0 = x - i0;
      float u1 = u0 - 1;
      float v0 = z - j0;
      float v1 = v0 - 1;

      float n00 = g00.DotProduct(ConstructVector(u0, v0));
      float n10 = g10.DotProduct(ConstructVector(u1, v0));
      float n01 = g01.DotProduct(ConstructVector(u0, v1));
      float n11 = g11.DotProduct(ConstructVector(u1, v1));

      float nx0 = Interpolate(n00, n10, u0, F);
      float nx1 = Interpolate(n01, n11, u0, F);

      float nxy = Interpolate(nx0, nx1, v0, F);

      noise[scaled_z, scaled_x] = nxy;
    }
  }
}