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

Question

前言

我必须道歉，但我认为自己在实现算法方面非常糟糕，因为我没有做过太多这种编程，所以请不要生我的气。我已经画了很 multimap 来理解我应该如何解决这个问题，但是我自己找不到方法，所以我请求你的帮助。

简介

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

实际问题

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

下面是使用中点位移算法后图 block 编号应该如何显示，以及它们现在如何使用我的错误实现在虚幻引擎 4 编辑器中放置在图 block map 中:

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

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

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

//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 一次。它需要被调用两次才能生成您在图表中显示的双重分支调用树，每次迭代时您都会将图 block 数量加倍(顺便说一句，“迭代”在使用时有点用词不当递归算法)。

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

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

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);
}

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