algorithm - 这个中点位移算法的 '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"和 "Mid Point Displacement Algorithm" ，我的问题是:

如何识别此代码隐含使用的“粗糙度常数”？然后，我该如何改变它？

此外，这可能与我的主要问题直接相关，也可能不直接相关，但我注意到代码将 y 值的总和添加到“delta”(变化量)并将其除以 2 - - 虽然这与求和然后加上 delta/2 相同。这对“粗糙度常数”有什么影响吗？我想我可以做

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

K 现在代表“粗糙度常数”，但我不确定这是否准确，因为它似乎允许我控制平滑但不直接控制“多少随机数每次循环都会减少范围”，如“生成随机分形地形”所定义。

就像我之前说过的，我将我发现的 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

他们的方法的优点是只需要一个部门就可以完成。当您使用 int 时，单个 div 的累积截断错误会更小(更不用说更快了)。