📊 Weighted Random: как сделать дроп с разным шансом выпадения

Ты делаешь сундук с лутом. Меч должен выпадать в 60% случаев, зелье — в 30%, легендарный топор — в 10%.

Первая мысль — Random.Range(0, 10) и куча if. Работает, но превращается в ад при изменении баланса.

Есть чище. Кладёшь все веса в массив и суммируешь их нарастающим итогом — это кумулятивный вес. Потом кидаешь одно случайное число от 0 до суммы всех весов и смотришь, в какой «отрезок» оно попало.

int[] weights = { 60, 30, 10 }; // меч, зелье, топор
string[] items = { "Меч", "Зелье", "Топор" };

int GetWeightedRandom()
{
    int total = 0;
    foreach (int w in weights) total += w;

    int roll = Random.Range(0, total);
    int cumulative = 0;

    for (int i = 0; i < weights.Length; i++)
    {
        cumulative += weights[i];
        if (roll < cumulative) return i;
    }
    return weights.Length - 1;
}

Хочешь добавить новый предмет — просто добавляешь одно число в массив. Хочешь изменить баланс — меняешь одно число. Никаких if.

Веса не обязаны суммироваться в 100 — это просто удобство. Можно писать { 6, 3, 1 } или { 600, 300, 100 } — результат одинаковый.

#мат_геймдев #БыстрыйМат #рандом #геймдев

⚡ Alias Method: как он устроен внутри

Вчерашний weighted random полезен, но важно понимать что по сложности он — O(n): чем больше предметов, тем дольше выборка.
Есть Alias Method, который даёт O(1) — время выборки не зависит от размера таблицы вообще.
За это платим однократной предподготовкой O(n) при старте и памятью.

Разберем пример. Допустим, три предмета с весами: Меч — 3, Зелье — 1, Топор — 2. Сумма = 6.

Шаг 1. Делим каждый вес на среднее (6 ÷ 3 = 2) — нормализованные высоты:

Меч   → 1.5
Зелье → 0.5
Топор → 1.0

Шаг 2. Рисуем три столбика — каждый ровно высотой 1.0:

|      |      |      |
|  1.0 |  1.0 |  1.0 |
 Слот0  Слот1  Слот2

Шаг 3. Расставляем предметы. Меч (1.5) не влезает в один слот.
Зелье (0.5) занимает полслота — свободное место отдаём Мечу:

| М    | М    |      |
| М    | З    | Т    |
 Слот0  Слот1  Слот2

Слот 0 → полностью Меч
Слот 1 → снизу Зелье (50%), сверху Меч (50%)
Слот 2 → полностью Топор

Шаг 4. Сохраняем для каждого слота: кто основной, кто запасной и граница.
Это и есть таблица алиасов.

───────────────────────────────────

Выборка — всегда два шага:

Слот:     0       1       2
Основной: Меч     Зелье   Топор
Запасной: —       Меч     —
Граница:  1.0     0.5     1.0

Шаг 1. Бросаем кубик — выбираем случайный слот.
i = Random.Range(0, 3) → выпало 1

Шаг 2. Бросаем монетку — сравниваем с границей слота.
r = Random.value → выпало 0.3
0.3 < 0.5 (граница слота 1) → берём основного → Зелье ✅

Тот же слот 1, но r = 0.7:
0.7 > 0.5 → берём запасного → Меч ✅

Слот 0 и 2: граница = 1.0 → любое число меньше 1.0 → всегда основной.

Вот почему O(1): не важно сколько предметов — всегда один Random.Range,
один Random.value, одно сравнение.

───────────────────────────────────

Теперь код. Строим таблицу алиасов один раз, потом только Sample():

public class AliasTable
{
    private int[]   _alias; // «запасной» предмет для каждого слота
    private float[] _prob;  // граница: ниже — основной, выше — запасной

    // Вызывается один раз — O(n)
    public AliasTable(int[] weights)
    {
        int n = weights.Length;
        _alias = new int[n];
        _prob  = new float[n];

        // Нормализуем веса: каждый вес → высота столбика (среднее = 1.0)
        float sum = 0;
        foreach (var w in weights) sum += w;
        float[] p = new float[n];
        for (int i = 0; i < n; i++) p[i] = weights[i] * n / sum;

        // Делим предметы на «маленькие» (< 1.0) и «большие» (>= 1.0)
        var small = new Queue<int>();
        var large = new Queue<int>();
        for (int i = 0; i < n; i++)
            if (p[i] < 1f) small.Enqueue(i);
            else           large.Enqueue(i);

        // Заполняем слоты: маленький берёт «запасного» из большого
        while (small.Count > 0 && large.Count > 0)
        {
            int s = small.Dequeue();
            int l = large.Dequeue();

            _prob[s]  = p[s]; // граница слота = высота маленького
            _alias[s] = l;    // запасной — большой предмет

            // У большого забрали часть — уменьшаем его высоту
            p[l] = (p[l] + p[s]) - 1f;
            if (p[l] < 1f) small.Enqueue(l);
            else           large.Enqueue(l);
        }
        // Оставшиеся «большие» заполняют слот целиком
        foreach (int i in large) _prob[i] = 1f;
        foreach (int i in small) _prob[i] = 1f; // float-погрешность
    }

    // Вызывается каждый раз — O(1)
    public int Sample()
    {
        int   i = Random.Range(0, _prob.Length); // кубик: выбираем слот
        float r = Random.value;                  // монетка: основной или запасной?
        return r < _prob[i] ? i : _alias[i];
    }
}

Использование:

// Один раз при старте
int[] weights = { 3, 1, 2 }; // Меч, Зелье, Топор
string[] items = { "Меч", "Зелье", "Топор" };
var table = new AliasTable(weights);

// Каждый раз при дропе
string dropped = items[table.Sample()];

Когда использовать: 50000+ предметов.
Для обычного лутбокса на 5–10 предметов — вчерашний метод проще.

#мат_геймдев #МатРазбор #рандом #оптимизация

⚡ Много предметов в луте? Замени цикл на бинарный поиск

Линейный поиск — O(n). На 10 000+ предметов уже заметно тормозит. Бинарный — O(log n), и на больших таблицах разница становится огромной.

Один раз считаем в Start():

int[] cumulative = new int[weights.Length];
cumulative[0] = weights[0];
for (int i = 1; i < weights.Length; i++)
    cumulative[i] = cumulative[i - 1] + weights[i];

При каждом дропе — только поиск:

int roll = Random.Range(0, cumulative[^1] + 1);
int idx = System.Array.BinarySearch(cumulative, roll);
if (idx < 0) idx = ~idx;

~ — оператор побитового НЕ. BinarySearch возвращает отрицательное число, если точного совпадения нет — это ~insertionPoint, где insertionPoint — индекс, куда вставилось бы значение. ~idx обращает это обратно и даёт первый элемент, который больше нашего броска. Именно он нам и нужен.

На 5 предметах разницы нет. На 10 000 — ощутимо.

Главное правило: кэшируй массив при старте, не пересчитывай каждый раз.

#мат_геймдев #БыстрыйМат #рандом #оптимизация

🎮 Weighted Random в играх, которые ты знаешь

Эта механика везде — просто под разными названиями:

🃏 Gacha-игры (Genshin Impact, Honkai)
Ставки в 0.6% на 5★ — это weighted random с очень маленьким весом редкого предмета.
Плюс «pity system» — счётчик, который повышает вес при неудаче.

⚔️ Diablo / Path of Exile
Аффиксы предметов тянутся из пула с разными весами. Редкий аффикс просто
имеет вес 1 против 1000 у обычного.

🌍 Minecraft
Структуры биомов, дроп мобов, содержимое сундуков — всё таблицы весов.
В коде это буквально называется loot tables.

🎰 Pokémon
Скрытые способности (Hidden Ability) — 1 шанс из 150. Шансы на природу —
равные, но можно изменить через синхронизацию.

Суть одна — ты уже знаешь как это работает под капотом.

#мат_геймдев #геймдизайн #рандом #МатРазбор