Математический вопрос: процедурная генерация галактики
Я собираюсь сделать космическую / торговую / боевую игру, которая полностью генерируется процедурно. Но я знаю, что хранить все детали всей галактики в памяти невозможно. В результате я подумал, что могу использовать семя для генерации солнечной системы, и из этой солнечной системы вы можете использовать прыжковые врата для путешествий в другие солнечные системы. Проблема в том, что если я прыгаю в другую солнечную систему из стартовой, мне нужно иметь возможность вернуться к точно такой же стартовой солнечной системе с точно такими же характеристиками (планеты, астероиды и т. Д.).
По сути, мне нужно создать целую галактику из одного числа. И из этого единственного числа, которое генерирует одну солнечную систему, я должен быть в состоянии генерировать все другие солнечные системы, которые связаны с первой, и все солнечные системы, которые связываются с ними, и так далее. И каждая солнечная система должна оставаться точно такой же по характеристикам, если я вернусь к ним. Кроме того, количество ссылок из каждой солнечной системы может быть либо случайным, либо фиксированным, по вашему выбору. Случайно было бы лучше, хотя.
19 ответов
Если вы чувствуете себя смелым, вы можете сделать хуже, чем посмотреть, как Ян Белл сделал это для оригинальной версии Elite
Проверьте эту серию на Gamasutra:
Процедурная вселенная в реальном времени, первые четыре ссылки
Кроме того, это: Алгоритмы для бесконечной вселенной
Вот основная идея, насколько я понимаю. Скажем, вы попали в звездную систему № 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' в них, не самый быстрый способ сделать это, но это показывает идею.
Взгляните на оригинальную игру Worms. Я думаю, что заявлено, что около 4 миллиардов возможных уровней. Каждый уровень генерировался на основе короткой начальной строки из 20 символов. Это определило
- тема уровня (арктика, лес и тд...)
- форма ландшафта
- скользкость земли
- размещение готовых деталей уровня (снеговики, камни...)
- размещение вашей команды червей, мин и ящиков с оружием.
Если вам понравился уровень, вы можете записать начальную строку и использовать ее для восстановления того же уровня на более позднем этапе.
Это пример очень сложной, но детерминированной функции с одним входным параметром. Я думаю, что это основная концепция того, что вам нужно.
Разве вы не можете просто SHA1 ID галактики, например:
Галактика 1
Sha1(1) = 356a192b7913b04c54574d18c28d46e6395428ab
Галактика 2
Sha1(2) = da4b9237bacccdf19c0760cab7aec4a8359010b0
Галактика 3
Sha1(3) = 77de68daecd823babbb58edb1c8e14d7106e83bb
Затем вы можете сегментировать код, т.е.
Первые 4 символа = количество планет
356a
da4b
77de
Вам понадобится какой-то алгоритм "строка в число", одним простым будет взять код ASCII каждого нечислового символа, а затем умножить их все вместе или что-то в этом роде.
Итак, теперь мы знаем, сколько планет в нашей галактике, как насчет размеров галактики x,y,z?
Следующие 9 символов = Размеры Галактики (x,y,z)
Тот же принцип, что и выше, превратить код в большое число. Также проведите несколько проверок на чувствительность, вам не нужна галактика размером 10 миль × 10 миль × 10 миль с 20 миллионами планет. Имейте какой-нибудь взвешенный алгоритм, например, минимальный размер равен # планет * 10000. Вам нужно будет поиграть с числами, чтобы убедиться, что все диапазоны совместимы и выбранные символы из хеша фактически дают вам разумный диапазон.
Или вместо этого вы можете выбрать случайное число между минимальным и максимальным размером галактики, но использовать постоянное начальное число ГСЧ, такое как идентификатор галактики! Таким образом, размеры галактики являются "случайными" для наблюдателя, но они всегда будут одинаковыми.
И т. Д.!
Это один из способов получить свойства вашей Вселенной, но как насчет свойств планеты? Как население и другие вещи?
Если у вас есть Galaxy 1 с 20000 планет, вы можете сделать:
Sha1('1:340') = bc02ab36f163baee2a04cebaed8b141505cc26b5
То есть, первая галактика, планета 340. Затем вы можете просто скомбинировать этот код так, как вам хочется. Преимущество использования хэша в том, что каждая планета должна иметь совершенно уникальный код.
Я думаю, что стоит отметить, что
генератор, который выдает один и тот же случайный вывод для одного и того же входа, называется генератором псевдослучайных чисел "PRNG". Как правило, вы даете ему один "начальный" входной номер в самом начале, а затем просто извлекаете из него случайные числа, вызывая его без дальнейшего ввода. Примечание: вы не можете "вернуться" к более раннему номеру, по крайней мере, не начав с начала.
PRNG-подобная функция, которая вызывается с координатами в качестве входных данных для каждого вызова, обычно является функцией "шума". Здесь у вас нет проблемы "невозможно вернуться" - просто вызовите "более ранний" ввод снова. Шумовая функция использует PRNG (в качестве бэкэнда или, по крайней мере, может), который все еще можно посеять с самого начала, поэтому вы не потеряете функцию "Вселенная из одного числа".
Хотя вы можете просто использовать PRNG и объединять координаты галактики в "семя" каждый раз, вы в лучшем случае получите только "белый шум", без дополнительных атрибутов. Шумовая функция намного лучше подходит для работы, так как ее можно выбрать или даже отрегулировать, чтобы дать вам мозаичный / сглаженный / спиральный вид / и т.д. Результаты. Для поиска примеров текстур изображений, которые были сделаны с использованием перлин шума. Я ожидаю, что вы увидите, что с помощью одной и той же шумовой функции вы можете создавать, например, тысячи случайных облаков, но, подстраивая шумовую функцию под свои нужды (не только зерно или координаты), вы можете получить вместо этого лаву или галактику. Регулировка не может быть тривиальной, хотя.
Количество входных координат для каждого вызова определяет количество измерений функции шума, поэтому для двумерной карты (или текстуры и т. Д.) Вы можете использовать двухмерную функцию шума. Затем вы называете это как noise2d(x,y) каждый раз.
В вашей ситуации я бы попробовал 3-мерную функцию симплексного шума (симплекс от автора перлин-шума, рекомендуется как лучший).
Каждая координата-тройка звездной системы затем дает одно число результата. Следующее решение будет: что представляет число? Чтобы эффективно использовать функцию сглаживания симплексного шума, я бы сопоставил меньшие числа с более пустыми солнечными системами и более высокие числа с системами с большей массой. Или, может быть, лучше для каждой системы вызывать симплексный шум несколько раз с подкоординатами. Числа результата среднего размера тогда - планеты, маленькие числа - вакуум или астероиды. Большие числа звезд и т. Д.
Тема неактивна и старая, но поиск может закончиться здесь, как и моя.
Случайное семя для каждой солнечной системы - жизнеспособное решение, но у меня есть ощущение, что вы тут не туда лаете.
Может ли игрок сделать что-нибудь, чтобы изменить то, что там? (Скажем, что-то построить, добыть истощаемый ресурс и т. Д.?) Если это так, вам все равно придется сохранить состояние.
Может ли игрок посмотреть, на что это было похоже, без необходимости возвращаться туда? (А если он не может, то почему бы и нет?!) Собираетесь ли вы искать это или вы собираетесь регенерировать всю солнечную систему только для того, чтобы узнать об этом информацию? (Решение PRNG не позволяет вам получить только часть солнечной системы, вы должны сделать все это.)
Сколько деталей в любом случае нужно сохранить?
Я не думаю, что в "галактике" действительно так много информации, которую нельзя было бы хранить на современных компьютерах. Давайте предположим, что галактика имеет 100 звезд, и что каждая звезда имеет 10 планет, и что у каждой планеты есть 3 луны. Это 100 звезд + 1000 планет + 3000 лун, которые вы должны отслеживать, что составляет 4100 тел.
Вот что мы можем отследить для планеты.
Масса X,Y,Z позиция Длина дня (время, чтобы вращаться вокруг своей оси) Длина года Население Количество ресурсов для 50 различных ресурсов
Предполагая, что каждому значению требуется двойное значение для его хранения, и у нас есть 57 значений для хранения (давайте округлим его до 100 и скажем 100), тогда у нас будет 100 значений * 8 байт * 4100 тел = 3 280 000 байт. Теперь это 3 мегабайта данных. Это может показаться много, но на самом деле это не так много. Кроме того, я не думаю, что вы действительно хотите иметь так много звезд в одной галактике. Игра действительно будет слишком большой, чтобы ее можно было исследовать, и, вероятно, станет неуправляемо большой, чтобы попытаться фактически смоделировать все, что происходит в данной галактике.
Рассмотрим этот вариант. Если вы возьмете игру, подобную SimCity, и посмотрите на каждый квадрат на городской сетке как на потенциальную планету, и тогда вы поймете, сколько информации можно сохранить в небольшом файле, чтобы вам не приходилось ничего генерировать случайным образом.
Я использую 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/
Предположим, вы начинаете с семени для галактики, то есть 1234, берете это семя и генерируете 10000 случайных чисел, каждое из которых представляет звездную систему. Когда вы приближаетесь к звезде, вы берете случайное число звезды и используете его в качестве начального числа для новой случайной функции. Сгенерируйте случайное число для количества небесных тел, вращающихся вокруг звезды, и сгенерируйте одно число для каждого тела (всегда используя вторую случайную функцию) и так далее. Я не знаю, поможет ли это вам, но вы должны помнить, что случайные функции внутренне хаотичны, для начального условия вся функция изменяется.
Семя звезд в галактике должно давать всегда одни и те же звезды, семя звезд должно давать одни и те же тела и т. Д.
Вы всегда можете сделать вещи интереснее, используя статистику, расчеты плотности, улучшение результатов. Всегда проверяйте, чтобы функции давали одинаковый результат для одного и того же ввода.
Извините, если мой английский отстой, я из Аргентины, и английский не является одним из моих тренированных качеств: p
PD: я делаю игру такого же типа;)
Пока вы вызываете srandom () с тем же начальным числом, вы получите те же значения из random (). Итак, просто основывайте все в звездной системе на одном вызове srandom ()... Тогда вам нужно будет хранить только 1 целое число (начальное число) для всей звездной системы. Теперь это сжатие!
Я смутно припоминаю, как это делалось раньше. В начале 90-х фракталы были в моде, и я помню одну компанию, предлагающую миры программистам игр. Они создали целую бесконечную вселенную, полную галактик с солнцами и планетами, вплоть до долин и текстур мест на планетах. Они предлагали разработчикам игр найти подходящую виртуальную недвижимость. Разработчики игр получат программное обеспечение для его рендеринга и использования вместе с точными координатами, которые им необходимы в этой фрактальной вселенной.
Я несколько минут гуглил по "фрактальной игре мир планеты вселенная" и тому подобное, но не нашел их. Возможно, это была Пандромеда, но я не могу вспомнить.
Вы должны изучить фракталы для этой идеи. Все, что вам нужно, это непрерывное поле чисел, которое вы можете воссоздать из начального числа, а затем представить эти числа в виде звезд, планет и спутников с различными свойствами.
Если вы используете генератор псевдослучайных чисел, вы можете гарантировать, что каждое сгенерированное вами случайное число будет отображаться в том же порядке из заданного начального числа. Код для генерации системы с заданным номером будет выглядеть одинаково каждый раз, когда вы его генерируете.
Используйте первое число из потока псевдослучайных чисел, чтобы сгенерировать число "ворот". Пройдите через все ворота и получите значение из числового потока для назначения и заполнения каждой целевой системы.
Создайте особенности каждой системы на основе этого семени.
Существует несколько известных алгоритмов генерации случайных семян.
Дай твёрдому Мерсенну трещину
Вот что я придумала. Не знаю, если это будет финальная версия, хотя.
Представьте себе гексагональную решетку и в каждой вершине солнечную систему. Поскольку мы находимся на гексагональной сетке, из любой вершины идет только три линии. Один всегда горизонтальный, а два других - диагонали. Если мы дадим начальному семени значение n, мы можем дать солнечной системе, которая горизонтально соединена с начальной точкой, значение n+1, остальные получат значения n+2 и n-2.
О дерьмо. Мы не обязательно получим сетку. Черт. Давай еще раз попробуем.
Вы можете создать псевдослучайное число из N цифр из определенного начального числа ("номер матери"). Затем вы разделяете цифры на группы и используете их для ответов на ваши вопросы.
Пример: N= 20
-> одна цифра: сколько дополнительных прыжковых ворот?
-> три цифры: начальное число для генерации соответствующих длин каждого доступного прыжка
-> шесть цифр: семя для создания этой солнечной системы
-> десять цифр: начальное число для создания нового начального числа из 20 цифр для каждой связанной солнечной системы
Тогда рекурсивно. Каждая система (со стабильными орбитами и т. Д.) Генерируется в момент времени 0, и вам придется рассчитать, как она выглядит сейчас.
Конечно, этот подход, начиная с материнской системы, будет означать, что чем дальше текущая система от материнской системы, тем больше времени требуется для формирования ее данных. Кроме того, этот путь создает дерево, а не сеть (чего я и ожидал).
Я думаю, что было бы лучше генерировать координаты - использовать полярные координаты на плоскости и, возможно, эллипсоид в трех измерениях.
Я подозреваю, что самая большая проблема, с которой вы столкнетесь, - это система именования, которая бы назвала все эти объекты таким образом, чтобы он был последовательным и значимым для игрока - хотя у нас есть схемы систематического именования реальных объектов. Я забыл, нарушил ли соглашение об именах Elite после определенного момента...
Это мое второе, улучшенное решение. Игрок начнет игру в случайно сгенерированной солнечной системе. Каждая система подключена от 1 до 4 других систем. Думайте о них как о северной, южной, восточной и западной системах. Если игрок должен был пройти через северные ворота, он попадет в систему, чье начальное число на одну единицу больше, чем в предыдущей системе. Если он пойдет на юг, семя для этой системы будет на одно меньше. 2+ и 2- для востока и запада соответственно. Расстояния до этих систем (в парсеках, световых годах и т. Д.) Рассчитываются исходя из начального числа систем и направления, из которого вы прибываете. Таким образом, размер галактики ограничен только максимумом и минимумом числа, используемого для хранения семян.
Отверстия для перехода в другие галактики будут расположены на определенном расстоянии от стартовой системы. Следующая галактика будет просто продолжением этой галактики в том смысле, что числа семян будут увеличиваться таким же образом, и что система, которая находится на другом конце галактической варп-дыры, будет просто "востоком" или "севером". "подключение из стартовой системы.
Кстати, такое использование приращения семян приводит к паутине, в отличие от вышеупомянутого решения. Кроме того, вы можете видеть, что этот метод использует четырехугольники, в то время как вышеупомянутое решение использовало шестиугольники, что сделало невозможным создание сети.
Конечно, все это основано на предположении, что все начальные числа будут генерировать случайную последовательность чисел, которая отличается от любой другой последовательности. Это делает так, чтобы каждая система была уникальной.
Если вы действительно хотите вернуться в фиксированное состояние, я не думаю, что процедурная генерация из одного значения - это правильный путь.
Предположим, у вас есть фиксированная сетка из 256х256 систем в каждой плоскости и 16 плоскостей во вселенной. Каждый самолет имеет до 512 торговых станций и до 8 ссылок на другие самолеты. Все торговые станции и ссылки находятся на фиксированной позиции. Ваше начальное начальное значение должно быть не менее 2^76, чтобы закодировать все возможные вселенные. Добавьте еще несколько объектов (планеты, корабли,...), и их число будет расти в геометрической прогрессии.
Изменить: Это немного меньше, если вы не разрешаете более одной торговой станции или ссылку в каждой системе. Я бы использовал некоторое постоянное хранилище, может быть, встроенную базу данных, такую как Firebird или sqlite. Кстати, я сейчас разрабатываю такую игру.
Математически вы хотите случайным образом / псевдослучайно сгенерировать неориентированный связанный граф. На этом графике каждый узел был бы солнечной системой, а каждый край - прыжковыми воротами.
1) Создайте N узлов и случайным образом назначьте каждому пространственную координату. Эти узлы со временем станут вашими солнечными системами.
2) Генерация ребер с использованием алгоритма Deluanay триангуляции. Я предлагаю триангуляцию Делуана, потому что она создаст довольно красивую карту без пересекающихся друг с другом ворот, но вы можете использовать любой алгоритм, который захотите. Я действительно не знаю, что вы ищете.
3) Если вы использовали триангуляцию Делуана, я предлагаю вам исключить определенное количество ребер для создания "разреженности". Это сделает карту более интересной, поскольку некоторые места станут транспортными узлами, а другие - просто пит-стопами.
4) Сохраните этот график. Это твоя вселенная. Не теряй и не выбрасывай свою вселенную. Храните его так эффективно, как хотите, но не удаляйте информацию.
5) Назначьте каждому узлу семя и используйте это семя для создания каждой солнечной системы.
6) Поздравляем, теперь у вас есть вселенная с произвольным числом Солнечных Систем и Прыжков.