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

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

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

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

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

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

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

ОБНОВЛЕНИЕ 2: Думаю, мне нужно пояснить, что важно, чтобы две смежные части карты, созданные отдельно, должны были плавно соединяться друг с другом.

ОБНОВЛЕНИЕ 3: В комментариях была запрошена дополнительная информация.

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

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

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

Теперь к неразумным вопросам:

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

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

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

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

ОБНОВЛЕНИЕ 4: Надеюсь, последний.

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

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

Ответ 1

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

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

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

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

Посмотрите также на процедурное поколение (особенно "см. также" и "внешние ссылки" ).

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

ИЗМЕНИТЬ: Здесь реализация "фракталов плазмы" (смещение средней точки) в processing.

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

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

Ответ 2

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

Ответ 3

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

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

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

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

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

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

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

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

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

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

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. Вам нужно всего лишь разбить и рассчитать те квадраты, которые вас интересуют, поэтому вы быстро достигнете целевой области (это очень похоже на двоичный поиск).

Ответ 4

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

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

Ответ 5

There are some papers listed здесь перечислены некоторые документы.

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

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