Математический вопрос: процедурная генерация галактики

Question

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

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

Answer 1

Если вы чувствуете себя смелым, вы можете сделать хуже, чем посмотреть, как Ян Белл сделал это для оригинальной версии Elite

Answer 2

Посмотри эту серию на Гамасутре:

Процедурная вселенная в реальном времени, первые четыре ссылки

Также это: Алгоритмы для бесконечной вселенной

Answer 3

Вот основная идея, насколько я понимаю. Скажем, вы попали в звездную систему № 42 и вам нужно выяснить, что в ней есть. Он имеет nplanets планет - число от 0 до 10, скажем:

>>> star_system = 42
>>> nplanets = hash('nplanets%d' % star_system) % (10 + 1)
>>> nplanets
4

Хорошо, так что на планете # 2, сколько космических станций находится на орбите там в начале игры? Найдите число от 0 до 3:

>>> planet = 2
>>> nstations = hash('nstations%d/%d' % (star_system, planet)) % (3 + 1)
>>> nstations
1

И так далее. Числа являются хеш-функцией индексов (звездная система № 42, в нашем случае планета № 2), приведенных к соответствующему диапазону. Поскольку хэш-функции являются детерминированными, но «случайными», они всегда одинаковы, но выглядят случайным образом для игрока.

Конечно, хеширование строк с длинными последовательностями, такими как 'nstations' в них, не самый быстрый способ сделать это, но это показывает идею.

Answer 4

Взгляните на оригинальную Worms игру. Я думаю, что заявлено, что около 4 миллиардов возможных уровней. Каждый уровень генерировался на основе короткой начальной строки из 20 символов. Это определяется

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

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

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

Answer 5

Разве вы не можете просто SHA1 ID галактики, например:

Галактика 1

Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab

Galaxy 2

Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0

Galaxy 3

Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb

Затем вы можете сегментировать код, т.е.: 1011 *

Первые 4 символа = Количество планет

356a
da4b
77de

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

Итак, теперь мы знаем, сколько планет в нашей галактике, как насчет размеров галактики x, y, z?

Следующие 9 символов = Размеры Galaxy (x, y, z)

Тот же принцип, что и выше, превратить код в большое число. Также проведите несколько проверок на чувствительность, вам не нужна галактика размером 10 миль х 10 миль х 10 миль с 20 миллионами планет. Имейте какой-нибудь взвешенный алгоритм, например, минимальный размер равен # планет * 10000. Вам нужно будет поиграть с числами, чтобы убедиться, что все диапазоны совместимы, а выбранные символы из хеша действительно дают вам разумный диапазон.

Или, вместо этого, вы можете выбрать случайное число между минимальным и максимальным размером галактики, но использовать постоянное зерно ГСЧ, такое как идентификатор галактики! Таким образом, размеры галактики являются «случайными» для наблюдателя, но каждый раз они будут одинаковыми.

и т. Д.!

Это один из способов получения свойств вашей Вселенной, но как насчет свойств планеты? Как население и другие вещи?

Если у вас есть Галактика 1 с 20000 планет, вы можете сделать:

Sha1('1:340') = bc02ab36f163baee2a04cebaed8b141505cc26b5

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

Answer 6

Думаю, стоит отметить, что

1. генератор, который выдает одинаковый случайный вывод для одного и того же входа, называется генератором псевдослучайных чисел, "PRNG". Обычно вы даете ему один начальный номер в самом начале, а затем просто вытягиваете случайные числа из него, вызывая его без дальнейшего ввода. Примечание: вы не можете «вернуться» к более раннему номеру, по крайней мере, не начав с начала.

2. PRNG-подобная функция, которая вызывается с координатами в качестве входных данных для каждого вызова, обычно является функцией "шума". Здесь у вас нет проблемы «невозможно вернуться» - просто вызовите «более ранний» ввод снова. Шумовая функция использует PRNG (в качестве бэкэнда или, по крайней мере, может), который все еще можно посеять с самого начала, поэтому вы не потеряете функцию «Вселенная из одного числа».

3. Хотя вы можете просто использовать PRNG и объединять координаты галактики в «семя» каждый раз, вы в лучшем случае получите только «белый шум», без дополнительных атрибутов. Шумовая функция намного лучше подходит для работы, так как ее можно выбрать или даже отрегулировать, чтобы дать вам мозаичный / сглаженный / спиральный вид / и т.д. Результаты. Для поиска примеров текстурных изображений, которые были сделаны с использованием перлин-шума. Я ожидаю, что вы увидите, что с той же шумовой функцией вы можете создать, например, тысячи случайных облаков, но, настроив функцию шума в соответствии с вашими потребностями (а не только семенами или координатами), вы можете вместо этого получить лаву или галактику. Однако его настройка может быть не тривиальной.

4. Количество входных координат для каждого вызова определяет количество измерений функции шума, поэтому для двумерной карты (или текстуры и т. Д.) Вы можете использовать двухмерную функцию шума. Затем вы называете это как noise2d (x, y) каждый раз.

В вашей ситуации я бы попробовал 3-мерную функцию симплексного шума (симплекс от автора перлин-шума, рекомендуется как лучший).

Каждый триплет координат звездной системы дает вам одно число результата. Следующее решение будет: что представляет число? Чтобы эффективно использовать функцию сглаживания симплексного шума, я бы сопоставил меньшие числа с более пустыми солнечными системами и более высокие числа с системами с большей массой. Или, может быть, лучше, для каждой системы вызывать симплексный шум несколько раз с подкоординатами. Числа результата среднего размера тогда - планеты, маленькие числа - вакуум или астероиды. Большие числа звезд и т. Д.

Тема неактивна и устарела, но поиск может закончиться, как у меня.

Answer 7

Я не думаю, что в «галактике» действительно так много информации, которую нельзя было бы хранить на современных компьютерах. Давайте предположим, что галактика имеет 100 звезд, и что каждая звезда имеет 10 планет, и что у каждой планеты есть 3 луны. Это 100 звезд + 1000 планет + 3000 лун, которые вы должны отслеживать, что составляет 4100 тел.

Вот вещи, которые мы можем отслеживать для планеты.

Масса X, Y, Z позиция Продолжительность дня (время вращения по своей оси) Продолжительность года Население Количество ресурсов для 50 различных ресурсов

Если предположить, что каждому значению требуется двойное значение для его хранения, и у нас есть 57 значений для хранения (давайте округлим его до 100), то получим 100 значений * 8 байт * 4100 тел = 3 280 000 байт. Теперь это 3 мегабайта данных. Это может показаться много, но на самом деле это не так много. Кроме того, я не думаю, что вы действительно хотите иметь так много звезд в одной галактике. Игра действительно будет слишком большой, чтобы ее можно было исследовать, и, вероятно, станет неуправляемо большой, чтобы попытаться фактически смоделировать все, что происходит в данной галактике.

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

Answer 8

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

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

Может ли игрок посмотреть, на что это было похоже, без необходимости возвращаться туда? (И если он не может, то почему бы и нет ?!) Собираетесь ли вы искать это или вы собираетесь восстановить всю солнечную систему, просто чтобы получить информацию об этом? (Решение PRNG не позволяет вам получить только часть солнечной системы, вам нужно сделать все это.)

Сколько деталей в любом случае нужно сохранить?

Answer 9

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

Семя для звезд в галактике должно давать всегда одинаковые звезды, семя для звезд должно давать одинаковые тела и т. Д.

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

Извините, если мой английский отстой, я из Аргентины, и английский не является одним из моих тренированных качеств: p

PD: я играю в тот же тип;)

Answer 10

Я использую Mersenne Twister. Это PRNG, который принимает в качестве своего начального массива любую длину.
Например, я хочу сгенерировать галактику по координатам x = 25, y = 72. Я заново инициирую твистер с семенами [25,72].
Если я хочу создать 1138-ю планету в этой галактике, я использую [25,72,1138].
Страна? [25,72,1138,10]
Город? [25,72,1138,10,32]
и т. д.
С помощью этого метода вы можете генерировать миллиарды триллионов миллиардов объектов, используя только одно число (одно перед координатой x, в нашем случае перед 25). Сейчас есть несколько проектов, которые его используют.
Noctis: anynowhere.com/
Бесконечная вселенная: http://www.infiniverse -game.com /