Carl Custav Mäeorg Carl Custav Mäeorg - 3 months ago 29
C++ Question

Using Midpoint Displacement algorithm by using recursion

FOREWORD

I must apologize, but I consider myself extremely bad at implementing algorithms as I've not done this kind of programming much, so please try not to be angry with me. I've drawn quite many pictures of understanding how should I solve this, but I can' t find the way myself, thus I'm asking for your help.

INTRODUCTION

I've been trying to implement Midpoint Displacement algorithm for my mountain terrain background in my game by using recursion. I'm doing my game in Unreal Engine 4 - there seems not to be an effecient way of drawing points in 2D as UE4 basically supports 2D only by Paper2D plugin, so I try to implement the algorithm by using tilemap and tiles. So the question I ask is quite specific...

THE ACTUAL PROBLEM

So basically what I have right now, is a tilemap with width of 256 and height of 64. And the tile numbers after division should be like in the picture below (we have to subtract one from each tile number due to the fact that tiles start from 0 and not from 1):

Here's how the tile numbers should be after using Midpoint Displacement algorithm and how they're placed in the tilemap in Unreal Engine 4 editor now using my faulty implementation:

Midpoint Displacement algorithm

As I understand it, the count of the function calls is exponential after each division (2 in power of some value). I'm not actually very sure whether recursion is the best way of using this algorithm, so feel free to interrupt here.

So, here's some code.
I draw the first, middle and the last manually and the rest of the points just move further to the left side of the tilemap.

The first, middle and the last tile colored at top and and Midpoint Displacement algorithm function at the bottom of the picture (roughness is an unused variable at the moment.

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


The arguments SetCell function uses are the following:


  • tile X

  • tile Y

  • tile texture



I hope there's enough information for you to understand my problem. If not, don' t hesitate to ask me to provide more information. Thank you in advance!

Answer

There's two main problems with your implementation:

Firstly, you are only recursively calling useMidpointDisplacement once inside itself. It needs to be called twice in order to produce the two-fold branching call-tree that you show in your diagram, where you get a doubling of the number of tiles at each iteration (btw "iteration" is kind of a misnomer when it's a recursive algorithm).

Secondly, you aren't computing the heights according to the midpoint displacement algorithm. Specifically, where do you compute the mid-point? And where do you displace it? Where do you incorporate the roughness value?

At each level of recursion, you need to pass in two heights, one at each end of the range you are splitting. Then find the average of the two and displace it by a random amount and use that to set the midpoint position. Then recurse between the two ends of the range and the midpoint.

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

At the top level, call it for the first midpoint, instead of computing that before the call:

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

You will probably get better results if you pass the heights around as floats and only convert to int when calling SetCell. Play around with the roughness value (0.2f is arbitrary).