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

Ответ 1

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

Ответ 2

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

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

Кроме того, это: Алгоритмы для бесконечного юниверса

Ответ 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" в них, - это не самый быстрый способ сделать это, но он показывает идею.

Ответ 4

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

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

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

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

Ответ 5

Не можете ли вы просто SHA1 идентификатор галактики, EG:

Галактика 1

Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab

Галактика 2

Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0

Галактика 3

Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb

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

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

356a
da4b
77de

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

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

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

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

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

Etc и т.д.

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

Если у вас есть Galaxy 1 с 20 000 планет, вы можете сделать:

Sha1('1:340') = bc02ab36f163baee2a04cebaed8b141505cc26b5

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

Ответ 6

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

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

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

• Пока вы можете просто использовать PRNG и каждый раз комбинировать координаты галактики с "семенем", вы получите только "белый шум" в лучшем случае без дополнительных атрибутов. Функция шума намного лучше подходит для работы, так как она может быть выбрана или даже настроена так, чтобы вы могли смотреть на твист/сглаженный/спиральный вид/и т.д. Результаты. На примерах поиск текстурных изображений, которые были сделаны с использованием шума perlin. Я ожидаю, что вы увидите, что с той же функцией шума, которую вы можете создать, например, тысячи случайных облаков, но, регулируя функцию шума в соответствии с вашими потребностями (а не только семенами или координатами), вместо этого вы можете получить лаву или галактики. Однако его настройка может быть тривиальной.

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

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

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

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

Ответ 7

Я не думаю, что на самом деле в этой "галактике" есть очень много информации, которую вы не могли сохранить на сегодняшних компьютерах. Пусть предположим, что у галактики 100 звезд, и что каждая звезда имеет 10 планет, и каждая планета имеет 3 луны. Это 100 звезд + 1000 планет + 3000 лун, которые вы должны отслеживать, что составляет 4 100 тел.

Вот что мы можем отслеживать для планеты.

Mass X, Y, Z позиция Длина дня (время поворота на собственной оси) Длина года Население Объем ресурсов для 50 различных ресурсов

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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

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

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

PD: Я делаю тот же тип игры;)

Ответ 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/
Infiniverse: http://www.infiniverse-game.com/

Ответ 11

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

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

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

Ответ 12

Вы можете создать псевдослучайное число из N цифр из определенного семени ( "номер матери" ). Затем вы делите цифры на группы и используйте их для ответа на свои вопросы.

Пример: N = 20

- > одна цифра: сколько дополнительных переходов?
- > три цифры: семя для генерации соответствующих длин каждого доступного прыжка
- > шесть цифр: семена для создания этой солнечной системы
- > десять цифр: семя для создания нового 20-значного семенного материала для каждой связанной солнечной системы.

Затем повторите. Каждая система (со стабильными орбитами и т.д.) Генерируется в момент времени 0, и вам нужно будет рассчитать, как она выглядит сейчас.

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

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

Ответ 13

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

Предположим, у вас есть фиксированная сетка из 256x256 систем в каждой плоскости и 16 плоскостей во вселенной. Каждый самолет имеет до 512 торговых станций и до 8 ссылок на другие самолеты. Все торговые станции и ссылки находятся на фиксированной позиции. Ваше начальное начальное значение должно быть не менее 2 ^ 76 для кодирования всех возможных юниверсов. Добавьте еще несколько объектов (планеты, корабли,...), и число растет экспоненциально.

Изменить: Это немного меньше, если вы не разрешаете более одной торговой станции или ссылки в каждой системе. Я бы использовал некоторое постоянное хранилище, возможно, встроенную базу данных, такую ​​как Firebird или sqlite. Кстати, я сейчас разрабатываю такую ​​игру.

Ответ 14

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

Представьте себе гексагональную сетку, а в каждой вершине - солнечную систему. Поскольку мы находимся на шестиугольной сетке, из любой вершины происходит только три строки. Один из них всегда горизонтальный, а два других - диагонали. Если мы дадим начальному семени значение n, мы можем дать солнечной системе, которая горизонтально связана с начальной точкой значением n + 1, другие получают значения n + 2 и n-2.

О, дерьмо. Мы не обязательно получим сетку. Черт возьми. Повторим попытку.

Ответ 15

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

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

Создайте подвиги каждой системы на основе этого семени.

Существует несколько известных алгоритмов генерации случайных семян.

Дайте Mersenne twister трещины

Ответ 16

Пока вы вызываете srandom() с тем же семенем, вы получите одинаковые значения из random(). Итак, просто запустите все в звездной системе с одного вызова srandom()... Тогда вам нужно будет только сохранить 1 целое (семя) для всей звездной системы. Теперь это сжатие!

Ответ 17

Это мое второе, улучшенное решение. Игрок начнет свою работу в случайно генерируемой солнечной системе. Каждая система соединена между 1 и 4 другими системами. Подумайте о них как о системах север, юг, восток и запад. Если игрок должен был пройти через северный прыжок, он будет доставлен в систему, чье семя еще одно, чем система раньше. Если он отправится на юг, семена для этой системы будут на один меньше. 2+ и 2- для востока и запада соответственно. Расстояния до этих систем (в парсеках или светлых годах или что-то еще) рассчитываются с использованием семян систем и направления, из которого вы прибываете. Таким образом, размер галактики ограничен только максимальным и минимальным количеством, используемым для хранения семян.

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

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

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

Ответ 18

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

Ответ 19

Математически вы хотите случайным образом/псевдослучайно генерировать Undirected, Connected Graph. На этом графике каждая node будет представлять собой солнечную систему, и каждое ребро будет затвором перехода.

1) Создайте N узлов и произвольно назначьте каждую пространственную координату. Эти узлы в конечном итоге станут вашими солнечными системами.

2) Генерировать ребра, используя алгоритм триангуляции Deluanay. Я предлагаю триангуляцию Deluanay, потому что он создаст довольно красивую карту без каких-либо ворот, пересекающих друг друга, но вы можете использовать любой алгоритм, который вы хотите. Я действительно не знаю, что вы ищете.

3) Если вы использовали триангуляцию Deluanay, я предлагаю вам устранить определенное количество ребер, чтобы создать "разреженность". Это сделает карту более интересной, поскольку определенные местоположения станут транспортными узлами, а другие - просто остановками пит-стопа.

4) Сохраните этот график. Это ваша вселенная. Не смешивайте и не выбрасывайте свою вселенную. Храните его так же эффективно, как вы хотите, но не удаляйте никакой информации.

5) Назначьте каждое node семя и используйте это семя для генерации каждой солнечной системы.

6) Поздравляем, теперь у вас есть вселенная с произвольным количеством солнечных систем и прыгающих ворот.