这个中点位移算法的'roughness constant'是多少，我该如何修改呢？

Question

我从 "Midpoint displacement algorithm example" 中获取了代码，对其进行了一些清理，然后将其重新调整为作为 1D 线性地形生成器工作。下面是我的 doMidpoint() 方法的新版本：

public boolean setMidpointDisplacement(int x1, int x2) {
      // Exit recursion if points are next to eachother
      if (x2 - x1 < 2) {
          return false;
      }

      final int midX = (x1 + x2) / 2;
      final int dist = x2 - x1;
      final int distHalf = dist / 2;

      final int y1 =  map[x1];
      final int y2 = map[x2];
      final int delta = random.nextInt(dist) - distHalf;    // +/- half the distance
      final int sum = y1 + y2;
      map[midX] = (sum + delta) / 2;  // Sets the midpoint

      // Divide and repeat
      setMidpointDisplacement(x1, midX);
      setMidpointDisplacement(midX, x2);

      return true;

}

该代码似乎运行良好并生成了可行的地形（您可以看到 how I've tested it，带有基本的 GUI）

看完"Generating Random Fractal Terrain" and "Mid Point Displacement Algorithm"，我的问题是：

如何识别此代码隐式使用的 'roughness constant'？然后，我该如何改变它？

此外，这可能与我的主要问题直接相关，也可能不直接相关，但我注意到代码将 y 值的总和添加到 "delta"（变化量）并除以这乘以 2——虽然这与求和然后加上 delta/2 相同。这对 'roughness constant' 有什么影响吗？我想我可以做

map[midX] = sum/2 + delta/K;

而 K 现在代表 'roughness constant'，但我不确定这是否准确，因为它似乎允许我控制平滑但不直接控制 "how much the random number range is reduced each time through the loop" 由 "Generating Random Fractal Terrain".

定义

正如我之前所说，我将找到的 2D MDP 噪声发生器移植到 1D 版本中——但我相当确定我做的很准确，所以这不是任何问题的根源。

Answer 1

How can I identify the 'roughness constant' implicitly utilized by this code?

在cited中，粗糙度是你减少最大随机位移的量。由于您的位移是 random.nextInt(dist) = dist*random.nextDouble()，您的 dist = x2-x1 并且您使用这个距离的一半从一个递归步骤转到另一个递归步骤，因此 roughness == 1 （在引用的术语中）

And then, how can I change it?

public boolean setMidpointDisplacement(int x1, int x2, int roughness) {
  // Exit recursion if points are next to eachother
  if (x2 - x1 < 2) {
      return false;
  }

  // this is 2^-roughness as per cited
  // you can pass it precalculated as a param, using it as such here
  // is only to put it into a relation with the cited
  double factor=1.0/(1<<roughness);

  final int midX = (x1 + x2) / 2;
  final int dist = x2 - x1;
  final int distHalf = dist / 2;

  final int y1 =  map[x1];
  final int y2 = map[x2];
  // and you apply it here. A cast will be necessary though
  final int delta = factor*(random.nextInt(dist) - distHalf);    // +/- half the distance

  final int sum = y1 + y2;
  map[midX] = (sum + delta) / 2;  // Sets the midpoint

  // Divide and repeat
  setMidpointDisplacement(x1, midX, roughness);
  setMidpointDisplacement(midX, x2, roughness);

  return true;

}

Additionally, and this may or may not be directly related to my major question, but I've noticed that the code adds the sum of the y-values to the "delta" (change amount) and divides this by 2

他们的方法的优点是只需 division 即可完成。当您使用 ints 时，单个 div 的累积截断误差会更小（更不用说更快了）。

这个中点位移算法的'roughness constant'是多少，我该如何修改呢？

What is the 'roughness constant' of this midpoint displacement algorithm, and how can I modify it?

algorithm

recursion

graph

procedural-generation

terrain