Генерация случайных чисел в программировании: PRNG, seed и RNG в играх

Генерация случайных чисел в программировании в основном опирается на генераторы случайных чисел типа псевдослучайных (PRNG), которые используют начальное значение seed из системного времени, аппаратного шума или пользовательского ввода для создания последовательностей, выглядящих случайными. Псевдослучайные числа генерируются по детерминированным алгоритмам вроде линейного конгруэнтного метода или Mersenne Twister, но при хорошей энтропии в seed закономерностей по времени суток не возникает — распределение остаётся равномерным. В играх вроде Lineage 2 или WoW RNG в играх чаще работает в реальном времени через встроенные PRNG, хотя иногда применяют предгенерированные массивы для скорости и баланса.

Содержание

• Как устроена генерация случайных чисел в программировании
• Генератор случайных чисел: псевдослучайные числа и их алгоритмы
• Какие данные используются для создания случайных значений (seed и энтропия)
• Алгоритм генерации случайных чисел: линейный конгруэнтный метод и Mersenne Twister
• Есть ли закономерности в распределении случайных чисел в зависимости от времени суток
• Генерация случайных чисел в Python, C и Java: примеры кода
• RNG в играх: как работают генераторы случайных чисел в Lineage 2 и WoW
• Методы генерации случайных чисел в играх — реальное время или заранее подготовленные массивы
• Источники
• Заключение

Как устроена генерация случайных чисел в программировании

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

Сердце системы — генератор случайных чисел (ГСЧ или RNG). Он стартует с seed — начального значения, которое “запускает” цепочку вычислений. Дальше алгоритм крутит эту цепочку, выдавая числа, которые статистически неотличимы от хаоса. Но если угадать seed, всю последовательность можно воспроизвести. Простой пример: в старых играх seed часто брали из времени — и хакеры это эксплуатировали.

Различают PRNG (псевдо) и TRNG (истинно случайные, на аппаратной энтропии). Первый — для игр и симуляций, второй — для крипты. А вы знали, что слабый ГСЧ может сломать даже казино в коде?

Генератор случайных чисел: псевдослучайные числа и их алгоритмы

Псевдослучайные числа — это не магия, а математика. PRNG берёт простое уравнение и итеративно его крутит. Классика — линейный конгруэнтный генератор (LCG). Но есть и монстры вроде Mersenne Twister, который выдаёт 2^19937-1 бит без повторений — хватит на миллиарды лет.

Почему не истинная случайность? TRNG медленные и дороги: они ловят тепловой шум или радиоактивный распад. PRNG? Миллиарды чисел в секунду. Идеально для генерации случайных чисел в программировании. Только вот паттерны: если seed плохой, числа “скучнеют” — слишком много чётных или кластеры нулей.

Тесты вроде DIEHARD или NIST проверяют: проходит ли распределение χ², покер-тест или спектральный анализ? Если нет — генератор в помойку.

Какие данные используются для создания случайных значений (seed и энтропия)

Seed — это топливо. Без него PRNG молчит. Что кормить?

Сначала банальщина: системное время. srand(time(NULL)) в C — миллисекунды с полуночи. Дешёво, но предсказуемо: если два вызова подряд, seed одинаковый. Лучше миксовать: время + PID процесса + счётчик.

Энтропия — ключ. Аппаратные источники: шум клавиатуры, мыши, микрофона, сетевого трафика. В Linux — /dev/urandom собирает это в пул. Windows? CryptGenRandom. Для паранойи — RDRAND на Intel, ловит хаос из кольцевых осцилляторов.

А пользователь? Ввод с клавиатуры — отличный seed. В крипте собирают гигабайты энтропии перед стартом. Без неё генератор случайных чисел — как сломанный рулет.

Алгоритм генерации случайных чисел: линейный конгруэнтный метод и Mersenne Twister

Давайте в формулы. Линейный конгруэнтный генератор (LCG):

$$X_{n+1} = (a \cdot X_n + c) \mod m$$

Где $a$ — множитель, $c$ — приращение, $m$ — модуль (часто $2^{32}$). Параметры выбраны по Халтону: $a=1664525$, $c=1013904223$. Просто? rand() в C часто на нём.

Mersenne Twister круче. Темперный алгоритм с состоянием 624x32 бита. Период огромный, проходит все тесты. В Python — random модуль на нём, Java — java.util.Random.

Код LCG на Python:

def lcg(seed, a=1664525, c=1013904223, m=2**32):
 while True:
 seed = (a * seed + c) % m
 yield seed / m # Нормализуем в [0,1)

Быстро. Но для игр — MT, чтоб не было “горячих” и “холодных” зон.

Есть ли закономерности в распределении случайных чисел в зависимости от времени суток

А вот и засада. Если seed — только время в секундах, то да: ночью мало энтропии, днём — трафик. Утром все стартуют программы — кластеры похожих seed. Результат? Лёгкие паттерны: больше “высоких” чисел в пиковые часы.

Но современные системы миксуют. Статья на Хабре подтверждает: с /dev/urandom или CryptGenRandom распределение равномерно круглосуточно. Тесты NIST на миллиардах сэмплов — χ² близко к 1.

Почему кажется иначе? В старых играх seed от тиков — и бац, “нефарт по утрам”. Реально? Миф. Статистика побеждает: за сутки энтропия сглаживает. Проверьте сами — запустите 10^6 rand() в разное время.

Генерация случайных чисел в Python, C и Java: примеры кода

Практика. Генерация случайных чисел в Python — random на MT:

import random
import time
random.seed(time.time()) # Seed от времени
print(random.randint(1, 100)) # 1-100

C — классика:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
 srand(time(NULL));
 printf("%d\n", rand() % 100 + 1);
 return 0;
}

Java:

import java.util.Random;
public class RNG {
 public static void main(String[] args) {
 Random r = new Random(System.currentTimeMillis());
 System.out.println(r.nextInt(100) + 1);
 }
}

Генерация случайных чисел в C медленнее без оптимизаций. Для крипты — OpenSSL RAND_bytes. А в псевдослучайные числа в Python — secrets модуль для безопасности.

RNG в играх: как работают генераторы случайных чисел в Lineage 2 и WoW

В RNG что это в играх? Random Number Generator для дропов, критов, заточки. Lineage 2: шанс на +10 меч — 0.1%, но rng в Lineage 2 часто жалуют на “сухость”. WoW — лутбоксы, рейды: каждый бросок через серверный PRNG.

Сервер держит seed, синхронизирует с клиентами. Mersenne Twister популярен — предсказуем только при знании состояния. Анализ на Sacralium показывает: RNG балансирует экономику, но игроки видят стрики — психология, не алгоритм.

Методы генерации случайных чисел в играх — реальное время или заранее подготовленные массивы

Реальное время доминирует. При мобкилл — вызов rand() на сервере. Быстро, гибко: динамические шансы по скиллам. Но трафик? В MMORPG миллионы вызовов — MT справляется.

Предгенерированные массивы? Для оффлайн-игр или лут-таблиц. “Мешок” (bag): массив предметов, shuffle и pop. В WoW-подобных — взвешенный bag: редкости дублируют реже. Плюс: оффлайн-работа, минус: статично.

Гибрид: seed от сервера, локальный PRNG. Lineage? Реал-тайм, с античитом на seed. Массивы — для тестов или казуальных игр.

Источники

1. Генерация случайных чисел — Подробное объяснение PRNG, алгоритмов и тестов: https://habr.com/ru/articles/151187/
2. Генераторы случайных чисел — Энтропия, seed и криптографические варианты: https://habr.com/ru/companies/vk/articles/351282/
3. Random в играх — Влияние случайности на баланс и экономику в MMORPG: https://portal.sacralium.game/article/random-v-igrah-kak-sluchainost-vliyaet-na-balans-i-ekonomiku
4. Loot tables и RNG — Механики лута с мешками и взвешенными вероятностями: https://habr.com/ru/articles/354132/

Заключение

Генерация случайных чисел — искусство баланса между скоростью и хаосом: PRNG с солидным seed решает 99% задач, от скриптов до рейдов в WoW. Закономерностей по времени суток нет при правильной энтропии, а в играх реал-тайм RNG с редкими массивами держит адреналин. Хотите копать глубже? Тестируйте сами — запустите MT на миллиардах итераций. Главное: для серьёзного — берите /dev/urandom, для фана — rand() хватит.