Технология генерации бесконечных миров в компьютерных играх развивалась постепенно. 3 Использование процедурной генерации началось с игры «Elite» 1984 года. 3

Некоторые ранние примеры применения этой технологии:

• Rescue on Fractalus. 1 Игра 1985 года, в которой использовались фракталы для процедурного создания в реальном времени скалистых гор чужой планеты. 1
• River Raid. 1 Игра Activision 1982 года, в которой использовалась псевдослучайная числовая последовательность, генерируемая сдвиговым регистром. 1

Со временем технология значительно продвинулась, что привело к созданию таких игр, как «Minecraft» и «No Man's Sky», которые предлагают сложные и масштабные миры. 3

Для реализации процедурной генерации используются различные алгоритмы, например:

• BSP-деревья. 2 Простой алгоритм, который заключается в рекурсивном разделении областей на две части. 2
• Алгоритм туннелирования. 2 Основная идея — пробить туннели и комнаты в полностью заполненном пространстве. 2
• Клеточные автоматы. 2 Основная идея — смоделировать «живой» организм — клетку, которая определяет, к какому типу относится та или иная ячейка карты. 2
• Алгоритмы из категории «шумов». 2 Это псевдослучайные алгоритмы для генерации текстур. 2 Они позволяют получить бесконечные области, состоящие из значений от -1 до 1, после чего данные числа могут использоваться для получения карты уровня. 2