Процедурная генерация бесконечного мира

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

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

Здесь я расскажу о том, как я это сделал. Хотя я использовал процедурную генерацию для создания ландшафта для 2D-платформерной игры, эти методы также работают для генерации игровых структур, спрайтов, текстур и звуков.

Случайные числа

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

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

Другими словами, функция, которая отображает свои входы на свои выходы непредсказуемым, но повторяемым образом.

Вот пример одной такой функции, которая возвращает непредсказуемые значения от 0 до 255.

Функция имеет только один входной параметр. Чтобы сгенерировать 2D-рельеф, мне нужна была функция, которая давала повторяемый вывод для каждой (x,y)coordinate в мире. Чтобы использовать указанную выше функцию, мне нужно было сопоставить x и yvalues ​​с одним числом.

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

Вывод этого результата на плоскости выглядит так:

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

Фрактальный шум

Шум здесь выглядит достаточно случайным, но довольно резким и не очень естественным. Более естественного эффекта можно добиться, объединив несколько слоев шума разного масштаба.

Каждый слой создается путем «увеличения» шума, пропуска пикселей и интерполяции значений между ними.

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

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

Есть более сложные подходы к интерполяции. (Шум Перлина - хорошо известный пример.) Однако показанная здесь простая линейная интерполяция достаточна для мира, который я хотел создать.

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

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

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

Игровой мир

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

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

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

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

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

Наконец, чтобы ограничить игрока по горизонтали, я создал эффект острова, изменяя порог по оси x, а также по оси y. Я сделал это, сместив ycoordinate в соответствии с квадратом xcoordinate.

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

Об александре

Я инженер-программист из Лондона. Я помогаю компаниям создавать веб-приложения.