如何实现中点位移算法

Question

我正在尝试在我的游戏中实现程序生成。我想真正掌握和理解所有必要的算法，而不是简单地复制/粘贴现有代码。为此，我尝试自己实现了一维中点位移。我使用这里的信息编写和指导我的代码。下面是我的完整代码，它不会报错，但结果似乎不正确。

srand(time(NULL));

const int lineLength = 65;
float range = 1.0;
float displacedLine[lineLength];

for (int i = 0; i < lineLength; i++)
{
    displacedLine[i] = 0.0;
}

for (int p = 0; p < 100; p++)
{
    int segments = 1;
    for (int i = 0; i < (lineLength / pow(2, 2)); i++)
    {
        int segs = segments;
        for (int j = 0; j < segs; j++)
        {
            int x = floor(lineLength / segs);
            int start = (j * x) + 1;
            int end = start + x;
            if (i == 0)
            {
                end--;
            }
            float lo = -range;
            float hi = +range;
            float change = lo + static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / (hi - lo)));

            int center = ((end - start) / 2) + start;
            displacedLine[center - 1] += change;
            segments++;
        }
        range /= 2;
    }
}

我到底犯了哪些错误，该如何进行更正？

我得到的结果类似于这样：

但是我期望的结果应该是这样的：

- rmaes4

---

那么你期望什么样的结果，以及这些结果与你的代码产生的结果相比如何？ - Simon

我不太确定如何正确地将我的点渲染成线，因此我粗略地尝试了一下，结果似乎不正确。 - rmaes4

@Simon，我添加了图片以澄清我的结果。 - rmaes4

Answer 1

答案非常简单，顺便说一下，我很惊讶你能够调试出代码中所有潜在的偏差错误。以下这行是错误的：

displacedLine[center - 1] += change;

你正确计算了中心索引和变化量，但是你忽略了变化应该应用于高度中点。也就是说：

displacedLine[center - 1] = (displacedLine[start] + displacedLine[end]) / 2;
displacedLine[center - 1] += change;

我相信你明白这个想法。

- Jonas Bötel

Answer 2

问题似乎在于您仅更改了每个线段的中点，而没有按比例更改其余部分，使其距离每个端点到中点的距离相等。以下代码似乎可以给您带来更接近您所需的结果：

#include <iostream>
#include <cstdlib>
#include <math.h>
#include <algorithm>

using namespace std;

void displaceMidPt (float dline[], int len, float disp) {
    int midPt = len/2;
    float fmidPt = float(midPt);
    for (int i = 1; i <= midPt; i++) {
        float ptDisp = disp * float(i)/fmidPt;
        dline[i] += ptDisp;
        dline[len-i] += ptDisp;
    }
}

void displace (float displacedLine[], int lineLength, float range) {
    for (int p = 0; p < 100; p++) {
        int segs = pow(p, 2);
        for (int j = 0; j < segs; j++) {
            float lo = -range;
            float hi = +range;
            float change = lo + static_cast <float> (rand()) / (static_cast <float> (RAND_MAX / (hi - lo)));
            int start = int(float(j)/float(segs)*float(lineLength));
            int end = int(float(j+1)/float(segs)*float(lineLength));
            displaceMidPt (displacedLine+start,end-start,change);
            }
        range /= 2;
    }
}

void plot1D (float x[], int len, int ht = 10) {
    float minX = *min_element(x,x+len);
    float maxX = *max_element(x,x+len);
    int xi[len];
    for (int i = 0; i < len; i++) {
        xi[i] = int(ht*(x[i] - minX)/(maxX - minX) + 0.5);
    }
    char s[len+1];
    s[len] = '\0';
    for (int j = ht; j >= 0; j--) {
        for (int i = 0; i < len; i++) {
            if (xi[i] == j) {
                s[i] = '*';
            } else {
                s[i] = ' ';
            }
        }
        cout << s << endl;
    }
}

int main () {
    srand(time(NULL));

    const int lineLength = 65;
    float range = 1.0;
    float displacedLine[lineLength];

    for (int i = 0; i < lineLength; i++) {
        displacedLine[i] = 0.0;
    }

    displace (displacedLine,lineLength,range);
    plot1D (displacedLine,lineLength);
    return 0;
}

以这种方式运行时，它会产生以下结果：

$ c++ -lm displace.cpp
$ ./a
                                  *
                              *       *
                                 * ***
                             * *       *             *
                         * **            ****       * **
      * ***  ****  *   *                *    **         *
     * *   **    ** ***   *     *                * *
   **                                          **        *
  *                     *                         *       ***
**                                                            ***
                                                             *

- Simon