Функция случайного заполнения для генерации карты?

28

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

Однако, если мир бесконечен, возвращение туда, где игрок уже был прежде, поднимает проблему. Игра должна помнить, как все было на самом деле.

Итак, я подумал - «Как Minecraft решает эту проблему?» и я подумал про себя, что они должны использовать какую-то функцию случайных чисел с начальным числом, которое может и идти вперед, и назад, и таким образом воссоздавать старые плитки точно так же, как они были, но в новых случаях.

Что вы думаете об этом?

Матиас Ликкегор Лоренцен
источник
Как мой ответ на +5, а вопрос только на +2? Это один из лучших вопросов на первой странице прямо сейчас.
2
Разве Minecraft просто не хранит фрагменты, которые вы уже посетили / модифицировали?
FxIII
@FxIII: Minecraft должен, потому что вы можете изменить ландшафт. Если вы не можете этого сделать, хранение кусков, вероятно, является пустой тратой или, по крайней мере, чрезмерным усложнением.
@Joe Wreschnig: Хорошо, хорошо ... Я боялся, что пропустил что-то действительно большое!
FxIII

Ответы:

20

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

Два очень тесно связаны. Функция шума может имитировать генератор случайных чисел, переходя в другое значение каждый раз , - например noise(1), noise(2)и так далее. А генератор случайных чисел, помещенный в гигантский стол, может выполнять функцию шума. В обоих случаях вы используете не тот инструмент для работы.

Minecraft , в частности , использования Перлин шума , тип шума , который дешев , чтобы вычислить, и имеет желаемое свойство быть непрерывным , как много размеров , как вам нужно - если график , f(x)чтобы f(x + 1), там не будет никаких резких скачков. Это делает его очень полезным для многих вещей, таких как модуляция текстуры, объемные облака и газы, а также генерация рельефа.

Если вы ищете реализацию, с которой можно начать играть, улучшенный генератор шума Perlin Кена Перлина - одна из самых простых реализаций.


источник
3
Обратите внимание, что многие генераторы случайных чисел используют начальное число и будут генерировать одинаковый набор чисел с одинаковым начальным числом.
Thedaian
3
@thedaian: что не особенно полезно в этом случае, если вы не хотите регенерировать каждое число; функция шума позволяет получить 500-е число без необходимости генерировать 499 до этого.
Имеется ли алгоритм Perlin Noise, можно ли его откалибровать? Предположим, я хочу, чтобы алгоритм с большей вероятностью генерировал пачку настенных плиток, а затем пачку космических плиток.
Матиас Ликкегор Лоренцен
3
Вы не прочитали и не поняли ссылки, которые я дал за шесть минут.
1
Этот ответ был бы в комплекте с блоге Notch в: notch.tumblr.com/post/3746989361/terrain-generation-part-1
deceleratedcaviar
3

Minecraft контролирует свое поколение, создавая семя уровня, которое используется для заполнения всех генераций случайных чисел в игре. Если чанк не существует на диске при его запросе, он будет сгенерирован с использованием функции генерирования Notch на основе начального уровня уровня; затем он сохраняется на диск для дальнейшего использования.

Звучит так, будто вы пытаетесь добиться подобного поведения, так что это безопасный путь.

Keeblebrox
источник
2

Как отметил Джо, вы ищете хеш-функцию. Как правило, случайные функции - это просто хеш-функции, заполненные последним возвращаемым числом. Так что, если он Random()вернется Hash(seed)=1234, второй вызов Random()вернется Hash(1234), и так далее.

Если вы ищете простую функцию хеширования для псевдослучайных чисел, посмотрите MurMurHash . Я реализовал это в C # и могу опубликовать его где-нибудь, если вам интересно. Более подробную информацию о Perlin Noise, который использует такую ​​хеш-функцию, можно найти здесь , а его реализация на C # - здесь .

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

dlras2
источник
-1. Хеш-шум Перлина, в данном случае, не имеет никакого сходства с методами, используемыми в MMH или других криптографических процедурах хеширования; тот код C # - мусор, который, кажется, просто делает линейную интерполяцию между случайными значениями; он требует гораздо больше памяти, чем собственный шум Perlin, и, вероятно, работает медленнее.
1
@Joe - мне жаль, что ты так сильно относишься к реализации Perlin Noise. Perlin Noise сам по себе является концепцией превращения хэш-функции в непрерывную шумовую функцию. Я очень эффективно генерировал много Perlin Noise с MurMurHash. Что касается кода C #, это пример того, как программно определить значение одной точки в 2D Perlin Noise. Я бы никогда не использовал его в работе, но, на мой взгляд, его легче пройти, чем код, который вы опубликовали.
dlras2
1
ОП не знал о шуме или хэшировании, поэтому я просто попытался предоставить ссылки в надежде, что они проведут дальнейшее расследование и самостоятельно решат, как реализовать то, что им нужно сделать.
dlras2
«Perlin Noise сам по себе является концепцией превращения хэш-функции в непрерывную шумовую функцию». Нет, шум Перлина - это одна из функций непрерывного шума, изобретенная Кеном Перлином (а не та, которую он назвал «симплекс-шум»). Не все функции непрерывного шума являются шумом Перлина; не все функции непрерывного шума являются даже градиентным шумом, частным примером которого является шум Перлина; то, что вы связали, это не градиентный шум, а ценный шум.
Код в вашей ссылке «легче пройти», потому что это не шум Перлина; это не так гладко; он использует гораздо больше ресурсов; короче, легче пройти, потому что это тупее.