Использование алгоритма смещения средней точки с помощью рекурсии
ПРЕДИСЛОВИЕ
Я должен извиниться, но я считаю себя очень плохим в реализации алгоритмов, так как я мало занимался этим видом программирования, поэтому, пожалуйста, постарайтесь не сердиться на меня. Я нарисовал довольно много картинок с пониманием того, как мне решить эту проблему, но я не могу найти способ сам, поэтому я прошу вашей помощи.
ВСТУПЛЕНИЕ
Я пытался реализовать алгоритм Midpoint Displacement для моего фона горной местности в моей игре с помощью рекурсии. Я делаю свою игру в Unreal Engine 4 — кажется, что не существует эффективного способа рисования точек в 2D, поскольку UE4 в основном поддерживает 2D только с помощью плагина Paper2D, поэтому я пытаюсь реализовать алгоритм, используя tilemap и тайлы. Так что вопрос, который я задаю, довольно специфичен …
АКТУАЛЬНАЯ ПРОБЛЕМА
Итак, в основном то, что у меня есть сейчас, это карта тайлов с шириной 256 и высотой 64. И числа тайлов после деления должны быть такими, как на рисунке ниже (мы должны вычесть одно из каждого номера тайла из-за того, что тайлы начинаются от 0, а не от 1):
Вот как должны быть номера плиток после использования алгоритма Midpoint Displacement и как они размещаются в карте тайлов в редакторе 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
- текстура плитки
Надеюсь, вам хватит информации, чтобы понять мою проблему. Если нет, не стесняйтесь просить меня предоставить больше информации. Заранее спасибо!
Решение
Есть две основные проблемы с вашей реализацией:
Во-первых, вы вызываете 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 произвольно).
Другие решения
Других решений пока нет …