Использование алгоритма Midpoint Displacement с помощью рекурсии

Question

ПРЕДИСЛОВИЕ

Я должен извиниться, но я считаю себя очень плохо реализации алгоритмов, поскольку я не делал такого рода программ много, поэтому, пожалуйста, постарайтесь не сердиться меня. Я нарисовал довольно много изображений понимания, как я должен это решить, но я не могу найти способ сам, поэтому я прошу вас о помощи.

ВВЕДЕНИЕ

Я пытался реализовать алгоритм Midpoint Displacement для моего горного фона местности в моей игре, используя рекурсию. Я занимаюсь своей игрой в Unreal Engine 4 - кажется, не эффективный способ рисования точек в 2D, поскольку UE4 в основном поддерживает 2D только с помощью плагина Paper2D, поэтому я пытаюсь реализовать алгоритм с помощью tilemap и плит. Таким образом, вопрос я задаю вполне конкретные ...

ФАКТИЧЕСКОГО ПРОБЛЕМА

Поэтому в основном то, что я прямо сейчас, это tilemap с шириной 256 и высотой 64, а числа плитки после разделения должно быть как на рисунке ниже (мы должны вычесть один из каждого номера плитки из-за того, что плитки начинаются с 0, а не с 1):

Вот как номера плитки должны быть после использования алгоритма смещения Midpoint и как они теперь помещаются в текстовый файл в редакторе Unreal Engine 4, используя мою ошибочную реализацию:

Как я понимаю, количество вызовов функций экспоненциально после каждого деления (2 по мощности какого-либо значения). Я на самом деле не очень уверен, что рекурсия - лучший способ использования этого алгоритма, поэтому не стесняйтесь прерывать здесь.

Итак, вот какой-то код. Я рисую первый, средний и последний вручную, а остальные точки просто перемещаются влево от плитки.

В первой, средней и последней плитки окрашены в верхней части и и функции алгоритма Midpoint Смещение в нижней части изображения (шероховатость неиспользованная переменная в данный момент.

//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 один раз внутри себя.Его нужно вызывать дважды, чтобы создать двукратное ветвящееся дерево вызовов, которое вы показываете на диаграмме, где вы получаете удвоение количества фрагментов на каждой итерации (битва «итерация» является некорректным, когда это рекурсивный алгоритм).

Во-вторых, вы не вычисляете высоты в соответствии с алгоритмом смещения средней точки. В частности, где вы вычисляете среднюю точку? И где вы его вытесните? Где вы включаете значение шероховатости?

На каждом уровне рекурсии вам необходимо пройти две высоты, по одному на каждом конце диапазона, который вы раскалываете. Затем найдите среднее значение из двух и вытесните его случайным количеством и используйте это, чтобы установить положение средней точки. Затем переписывайте между двумя концами диапазона и середины.

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

Вы, вероятно, получите лучшие результаты, если вы передаете высоты вокруг как поплавки и только конвертировать в int при вызове SetCell. Играйте со значением шероховатости (0.2f произвольно).