Как я могу создать "неограниченный" мир?

Question

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

Суть в том, чтобы иметь мир, в котором все данные генерируются случайным образом по запросу, но детерминистическим способом.

В настоящее время я сосредотачиваюсь на большой 2D-карте, на которой должна быть возможность отображать любую часть без знания окружающих частей.

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

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

EDIT: Забыл ссылку на мой вопрос.

РЕДАКТИРОВАТЬ 2: Я думаю, мне придется уточнить, что важно, чтобы две смежные части карты, сгенерированные отдельно, должны плавно соединяться друг с другом.

РЕДАКТИРОВАТЬ 3: В комментариях была запрошена дополнительная информация.

Вот изображение, взятое со страницы о фрактале и Perlin Noise , очень похожее на то, что я делал ранее (поскольку моя лучшая попытка, вероятно, использовала Perlin Noise):

http://www.neilblevins.com/cg_education/fractal_noise/perlin_fractal_max_levels2.jpg

Думайте о черных пикселях как о глубоком море, а белые о пикселях как о вершинах гор. Это то, что мне нужно, простая двухмерная карта высот.

Что я хочу сделать, это выбрать любой прямоугольник из очень большого мира (в диапазоне MAXINT * MAXINT пикселей) и сгенерировать его. Если бы я сгенерировал какую-либо часть изображения выше, он должен получить точно такие же пиксели, как если бы я сгенерировал большую часть, охватывающую меньшую.

Теперь к вопросам Unreason:

Требуемая производительность : Моя главная цель - пошаговая RPG, поэтому производительность может быть довольно низкой, но я думаю, что было бы очень интересно узнать, возможно ли создать быстрый алгоритм.

Требования к памяти : желательно, чтобы ничего не создавалось предварительно, но, кроме этого, использование памяти должно соответствовать любой обычной игре или приложению.

Необходимые детали : Ну, если вы посмотрите на изображение, вы получите идею. Хотя было бы очень хорошо, если бы можно было уменьшать и перемещать изображение без необходимости сначала рассчитывать карту с максимально увеличенным уровнем.

Необходимые типы объектов и свойства объектов для генерации : Ничего особенного, я доволен ландшафтом в соответствии с изображением выше. Но я признаю, что думал о подобной установке, где все очень очень большой город. Это был бы другой вопрос.

РЕДАКТИРОВАТЬ 4: Надеюсь, последний.

Хорошо, после прочтения кажется, что Perlin Noise - это то, что нужно. У меня есть еще один вопрос (если кто-то захочет ответить сейчас, когда я принял один (фактически два) ответа :)).

Функция шума Перлина принимает удвоение. Каков диапазон для этих двойников? [0-1 [? Или я могу с удовольствием отправить мои большие целые числа?

Answer 1

Обычно все генераторы ландшафта / мира работают так, как вы описали - они способны создавать обширные (случайные) миры из очень ограниченных входных данных (набора параметров).

Итак, вы можете захотеть наложить дополнительные ограничения на ваш вопрос.

Если что-то сработает для вас или вы только начинаете искать - взгляните на различные фокусы и подходы здесь .

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

Взгляните также на процедурную генерацию (особенно «смотрите также» и «внешние ссылки»).

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

EDIT : Вот реализация 'плазменных фракталов' (смещение средней точки) в обработке .

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

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

Answer 2

Terrains обычно генерируются с фракталами.

Простым методом является алгоритм Plasma Cloud, также известный как Алгоритм смещения средней точки . Общая идея:

1. Установите некоторые значения высоты для углов области.
2. Разделите прямоугольник на 4 меньших прямоугольника.
3. Рассчитать высоту для новых точек как среднее значение от окружающих точек и добавить к этому значение случайного смещения
4. Рекурсивно разделите каждый прямоугольник на меньшие прямоугольники и соответственно уменьшите величину смещения.

Случайное значение генерируется генератором псевдослучайных чисел. Если вы дадите конкретное начальное число в начале, всегда генерируется одна и та же последовательность чисел.

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

Плазменное облако дает довольно реалистичные ландшафты, но в долгосрочной перспективе они становятся скучными. Следовательно, более сложные алгоритмы (Perlin Noise, Ridged Perlin и т. Д.) Могут использоваться дополнительно. Чтобы получить больше разнообразия, вы можете использовать один фрактал (с низким разрешением) для настройки параметров другого фрактала, который вычисляет фактические значения.

Фракталы также можно использовать для создания текстур и рельефных изображений.

Хорошим примером программы, которая генерирует ландшафты с фракталами и другими процедурными методами, является Terragen . Terragen генерирует фотореалистичные изображения, поэтому он медленный, но у него есть предварительный просмотр OpenGL, который создает пейзаж на лету.

Редактировать: Проблема с Plasma Cloud заключается в том, что вы не можете создать одну точку (или небольшую область) без создания всей области. Это потому, что обычно он использует генератор случайных чисел, который зависит от предыдущего значения случайного числа.

Однако вам не нужен статистически хороший генератор случайных чисел для генерации ландшафта. Таким образом, вы можете заменить функцию rand некоторой функцией, которая вычисляет случайное число из координат X и Y вместо предыдущего значения. Примерно так (не проверено):

const int a = 0x7fffffff / 48271;
const int b = 0x7fffffff % 48271;

int displacement(int x, int y)
{
    int     seed, result;

    seed = x ^ ((y << 1) & 0x2AAAAAAA) ^ ((y >> 1) & 0x33333333);
    result = 48271 * (seed % a) - b * (seed / a);

    Return (result & 0xffff);
}

Выше было изменено из фактического генератора случайных чисел, так что начальное число рассчитывается по x и y. Но, может быть, даже какой-нибудь более простой функции будет достаточно.

Edit2 : Чтобы создать бесконечный мир , вы можете начать, например, с прямоугольника 10 x 10 км. Используйте функцию смещения выше, чтобы установить начальные высоты для углов прямоугольника, в пределах которого находится ваше целевое местоположение. Затем начните разбивать квадраты с помощью алгоритма Plasma Cloud. Вам нужно только разделить и рассчитать те квадраты, которые вас интересуют, чтобы вы быстро достигли целевой области (это очень похоже на бинарный поиск).

Answer 3

Посмотрите на Perlin Noise, это тип детерминированных случайных данных, названный в честь его изобретателя Кена Перлина. Если вы ищете «Perlin Noise» или «Ken Perlin», вы найдете массу статей о процедурных текстурах и генерации ландшафта.

Answer 4

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

В дополнение к Perlin Noise, поиск фрактального ландшафта. Это может привести к очень натуралистическому рыхлению местности.

Answer 5

Здесь перечислены некоторые статьи .

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

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