通过递归使用中点位移算法

Question

前言

我必须道歉，但我认为自己在实现算法方面非常糟糕，因为我没有做过太多这种编程，所以请不要生我的气。我画了很多图想知道怎么解决，但是我自己找不到方法，求大家帮忙。

简介

我一直在尝试使用递归为我的游戏中的山地地形背景实施中点位移算法。我在 Unreal Engine 4 中玩我的游戏 - 似乎没有一种在 2D 中绘制点的有效方法，因为 UE4 基本上仅通过 Paper2D 插件支持 2D，因此我尝试使用 tilemap 和 tiles 来实现该算法。所以我问的问题很具体...

实际问题

所以基本上我现在拥有的是一个宽度为 256 高度为 64 的瓦片地图。分割后的瓦片编号应该如下图所示（我们必须从每个瓦片编号中减去一个，因为瓷砖从 0 而不是 1 开始的事实）：

下面是使用中点位移算法后的图块编号以及它们在 Unreal Engine 4 编辑器中的图块地图中的放置方式，现在使用我的错误实现：

据我了解，函数调用的次数在每次除法后呈指数增长（2 的某个值的幂）。我实际上不太确定递归是否是使用此算法的最佳方式，所以请随时打扰。

所以，这是一些代码。我手动绘制了第一个、中间和最后一个点，其余点只是进一步移动到图块地图的左侧。

第一个，中间和最后一个瓦片在顶部着色，中点位移算法在图片底部起作用（粗糙度是一个未使用的变量。

//IRRELEVANT CODE ABOVE
back->SetCell(0, FMath::RandRange(30, testTilemap->MapHeight - 1), contrast_purple);
back->SetCell(testTilemap->MapWidth-1, FMath::RandRange(30, testTilemap->MapHeight - 1), contrast_purple);
back->SetCell(FMath::FloorToInt((0 + testTilemap->MapWidth - 1) / 2), FMath::RandRange(30, testTilemap->MapHeight - 1), contrast_purple);
// Terrain generation
useMidpointDisplacement(FMath::FloorToInt((0 + testTilemap->MapWidth-1)/2), testTilemap->MapHeight, 6, 6);
}

int AProcedural_Map::useMidpointDisplacement(int width, int height, int iteration, float roughness)
{

if (iteration < 1) {
    return 0;
}
back->SetCell(FMath::FloorToInt(width - FMath::Pow(2, iteration)), FMath::RandRange(30, height - 1), contrast_purple);
back->SetCell(FMath::FloorToInt(width + FMath::Pow(2, iteration)), FMath::RandRange(30, height - 1), contrast_purple);

iteration--;

useMidpointDisplacement(FMath::FloorToInt((0 + width)/2), height, iteration, roughness);
return 0;
}

SetCell 函数使用的参数如下：

平铺 X
平铺 Y
平铺纹理

我希望有足够的信息让您理解我的问题。如果没有，请不要犹豫，让我提供更多信息。提前致谢！

Answer 1

您的实施存在两个主要问题：

首先，您只是在自身内部递归调用 useMidpointDisplacement 一次。它需要被调用两次才能生成您在图表中显示的双重分支调用树，每次迭代时您都会将图块数量加倍（顺便说一句 "iteration" 有点用词不当当它是递归算法时）。

其次，您没有根据中点位移算法计算高度。具体来说，你在哪里计算中点？你在哪里取代它？你在哪里合并粗糙度值？

在递归的每一层，您需要传入两个高度，一个在您要拆分的范围的两端。然后找到两者的平均值并将其替换为随机量并使用它来设置中点位置。然后在范围的两端和中点之间递归。

int AProcedural_Map::useMidpointDisplacement(int width, int leftHeight, int rightHeight, int iteration, float roughness)
{    
    if (iteration < 0) {
        return 0;
    }
    // compute midpoint:
    int midpointHeight = (leftHeight + rightHeight) / 2;

    // displace it (incorporate roughness here):
    int range = FMath::FloorToInt(FMath::Pow(2, iteration) * roughness);
    midpointHeight += FMath::RandRange(-range, range);

    // clamp:
    if(midpointHeight < 0) midpointHeight = 0;
    if(midpointHeight >= testTilemap->MapHeight) midpointHeight = testTilemap->MapHeight - 1;

    back->SetCell(width, midpointHeight, contrast_purple);

    iteration--;

    // recurse the two sides:
    useMidpointDisplacement(FMath::FloorToInt(width - FMath::Pow(2, iteration)), leftHeight, midpointHeight, iteration, roughness);
    useMidpointDisplacement(FMath::FloorToInt(width + FMath::Pow(2, iteration)), midpointHeight, rightHeight, iteration, roughness);

    return 0;
}

在顶层，为第一个中点调用它，而不是在调用之前计算它：

//IRRELEVANT CODE ABOVE
int leftHeight = FMath::RandRange(30, testTilemap->MapHeight - 1);
int rightHeight = FMath::RandRange(30, testTilemap->MapHeight - 1);
back->SetCell(0, leftHeight, contrast_purple);
back->SetCell(testTilemap->MapWidth-1, rightHeight, contrast_purple);

// Terrain generation
useMidpointDisplacement(FMath::FloorToInt((testTilemap->MapWidth-1)/2), leftHeight, rightHeight, 6, 0.2f);
}

如果将高度作为浮点数传递并且仅在调用 SetCell 时转换为整数，您可能会获得更好的结果。调整粗糙度值（0.2f 是任意的）。

通过递归使用中点位移算法

Using Midpoint Displacement algorithm by using recursion

c++

algorithm

recursion

procedural-generation