📊 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. Шансы на природу —
равные, но можно изменить через синхронизацию.

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

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

Да, я только понял, что забыл комменты привязать XD В следующих постах будет)

🚨 Ошибка недели: почему твой weighted random врёт

Классическая ловушка — веса заданы через float и суммируются с погрешностью:

float[] weights = { 0.1f, 0.3f, 0.6f }; // кажется, сумма = 1.0
// На самом деле: 0.99999994f из-за float-арифметики

Если ты делишь на сумму для нормализации — погрешность накапливается. Последний элемент может никогда не выпасть или выпадать чуть реже.

Два способа починить:

1. Используй int-веса — целые числа не теряют точность:

int[] weights = { 60, 30, 10 }; // вместо 0.6f, 0.3f, 0.1f

2. Последний элемент — всегда fallback, а не результат сравнения:

for (int i = 0; i < weights.Length; i++)
    if (roll < cumulative[i]) return i;
return weights.Length - 1; // если погрешность съела край — возвращаем последний

Маленькая деталь — но именно такие баги живут в проде годами и порой приводят к непредсказуемым последствиям.

#мат_геймдев #ОшибкаНедели #рандом

📋 Итог блока «Рандом» — что мы разобрали и где это использовать

За прошлую неделю — три концепции, которые покрывают основные задачи с дропом предметов в геймдеве:

Weighted Random
Простой и читаемый. Выбор по умолчанию для лутбоксов, таблиц дропа, спавна мобов.

Alias Method
O(1) после предподготовки. Когда вызовов тысячи в секунду.

Binary Search + кеш
Компромисс. Быстрее обычного, проще Alias.


На следующей неделе открываем новую тему — Физика столкновений. Поехали 👇

#мат_геймдев #ДайджестМесяца #рандом

👾 Физика столкновений: зачем разбираться, если движок всё делает сам?

Коллайдеры Unity или Godot — это удобно. Ставишь Box Collider, игра работает.
Но рано или поздно случается одно из двух:

• Персонаж проваливается сквозь пол на высокой скорости
• Хитбоксы не совпадают с визуалом и игроки злятся
• Нужна кастомная физика — платформер кастомной физикой
top-down с трением, пинбол-механика


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

Тогда понимание математики за коллайдерами — не академизм, а рабочий инструмент.

На этой неделе разбираем:
— AABB: самый быстрый прямоугольный коллайдер
— Circle: идеален для снарядов и мячей
— Вектор отражения: отскок без магии

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

📊 AABB — прямоугольник против прямоугольника без тригонометрии

AABB (Axis-Aligned Bounding Box) — прямоугольник, стороны которого
параллельны осям координат. Никакого поворота.

Проверка столкновения двух AABB — четыре сравнения чисел:

struct AABB
{
    public float minX, maxX, minY, maxY;
}

bool Overlaps(AABB a, AABB b)
{
    return a.maxX > b.minX &&  // a не левее b
           a.minX < b.maxX &&  // a не правее b
           a.maxY > b.minY &&  // a не ниже b
           a.minY < b.maxY;    // a не выше b
}

Никакого корня квадратного, никаких синусов. Четыре сравнения.
Это причина, по которой большинство игровых движков используют AABB
для первичной проверки (broad phase) даже у сложных объектов.

Минус: не работает если объект повёрнут. Для поворота — OBB или SAT.
Но для большинства платформеров и top-down игр AABB хватает с головой.

#мат_геймдев #МатРазбор #физика #коллайдеры

🤔 Загадка: почему быстрый персонаж проваливается сквозь пол?

Коллайдеры настроены правильно. На низкой скорости всё работает.
Но разогнать персонажа — и он прошивает платформу насквозь.

Пауза — подумай секунду.

...

Ответ: Tunneling (туннелирование).

Физика в играх дискретная: каждый кадр объект перемещается на velocity * deltaTime.
Если объект за один кадр перемещается дальше, чем толщина коллайдера —
движок просто не замечает пересечения. Объект был над полом, стал под ним.
Столкновения не было.

Три решения:
1. Continuous collision detection (CCD) — движок проверяет весь путь, не точку.
Дорого по производительности.
2. Ограничить максимальную скорость так, чтобы за кадр объект не мог
пролететь сквозь коллайдер.
3. Raycast в направлении движения перед шагом — рукопашная CCD.

Знал о туннелировании раньше? 👇

#мат_геймдев #физика #коллайдеры #ОшибкаНедели

📊 Circle-коллайдер: почему он лучше AABB для снарядов

AABB — быстрый, но у него слабое место: он прямоугольный.
Пуля, мяч, персонаж в top-down — у них нет углов. AABB даёт ложные
столкновения в углах, которых визуально нет.

Circle решает это элегантно. Проверка столкновения двух окружностей —
одно вычитание и одно сравнение:

bool CirclesOverlap(Vector2 posA, float rA, Vector2 posB, float rB)
{
    float dx = posA.x - posB.x;
    float dy = posA.y - posB.y;
    float distSq = dx * dx + dy * dy;       // квадрат расстояния
    float radiusSum = rA + rB;
    return distSq < radiusSum * radiusSum;   // без корня — быстрее
}

Никакой тригонометрии. Корень не нужен — сравниваем квадраты.

Когда выбирать Circle:
• снаряды (пули, фаерболы) — форма симметрична
• мячи, монеты, бонусы — очевидно
• персонажи в top-down — нет чёткой «передней» стороны

Когда выбирать AABB:
• платформы, стены, тайлы — прямоугольные по природе
• хитбоксы, которые должны «прижиматься» к форме спрайта

На практике движки используют их вместе: AABB — быстрая первичная
проверка (broad phase), Circle или Polygon — точная (narrow phase).

#мат_геймдев #МатРазбор #физика #коллайдеры

📊 Вектор отражения: как математика делает отскок

Мяч летит в стену. Как посчитать направление после отскока?

Интуиция подсказывает: «отразить угол». Но угол — это арктангенс,
градусы, неудобно. Есть формула, которая работает через векторы:

R = V - 2 * (V · N) * N

Где:
V — вектор направления до удара
N — нормаль поверхности (перпендикуляр к стене, единичный вектор)
R — вектор направления после отскока

Vector2 Reflect(Vector2 velocity, Vector2 normal)
{
    // normal должен быть нормализован
    float dot = Vector2.Dot(velocity, normal);
    return velocity - 2f * dot * normal;
}

// Примеры нормалей:
// Пол (горизонтальная поверхность) → normal = Vector2.up    (0, 1)
// Стена справа                     → normal = Vector2.left  (-1, 0)
// Наклонная платформа 45°          → normal = new Vector2(-0.707f, 0.707f)

// Использование:
ballVelocity = Reflect(ballVelocity, wallNormal);

В Unity это уже встроено:

ballVelocity = Vector2.Reflect(ballVelocity, wallNormal);

Но понимать формулу важно — потому что Reflect работает для любого угла.
Не только для горизонтальных/вертикальных стен, но и для наклонных
поверхностей, движущихся платформ, рикошетов.

Откуда формула? V · N — это «насколько вектор V направлен вдоль N».
2 * (V · N) * N — это та часть V, которую нужно «отзеркалить».
Вычитаем её из V дважды — получаем отражение.

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

Отражение векторов - Интерактив
https://wreath-violet-94758009.figma.site/

Я пока думаю в каком формате делать всякие интерактивные штуки чтобы было проще воспринимать формулы и код. Гифки там или интерактивные сайты. Для последнего надо бюджет на тачку и домен для этого дела выделить, а пока не до того) Экспериментально из любопытства собрал в ИИ фигмы интерактив объясняющий пост выше.

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

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

🎲 Откуда берётся «случайность» в компьютере?

Спойлер: её нет. Компьютер генерирует числа по формуле — детерминированно,
шаг за шагом. Такая последовательность называется псевдослучайной (PRNG).

Простейший PRNG — линейный конгруэнтный генератор (LCG):

next = (a * current + c) % m

Три магических константы a, c, m — и каждый вызов выдаёт «новое» число.

Пример на пальцах (a=1664525, c=1013904223, m=2^32):

uint state = 42; // начальное значение (сид)

uint NextRandom()
{
    state = 1664525u * state + 1013904223u;
    return state;
}

Вызови три раза — получишь три разных числа. Вызови снова с state=42 — те же три.

Почему это важно для геймдева:
→ Ты контролируешь «случайность» через начальное значение (seed)
→ Один и тот же seed = один и тот же мир / один и тот же дроп
→ Это основа воспроизводимых миров, реплеев и читов через save-scumming

Unity использует System.Random под капотом — тот же принцип, чуть сложнее.
Godot — свой Mersenne Twister. Но идея одна: формула + стартовое число.

Существуют ГСЧ, основанные на сборе энтропии — они «более случайные», и главная задача таких генераторов — быть непредсказуемыми. Применяются они там, где взлом или предсказуемость недопустимы: в криптографии, защите данных, онлайн-сервисах. Это область весьма сложных идей и алгоритмов: получить по-настоящему случайное, равновероятно распределённое число от 0 до 1 — задача совсем не тривиальная.

Вообще важно понимать природу случайности — это абстрактное понятие, придуманное человеком. Я когда-то задумывался: бросить монетку 50 на 50 — спорное утверждение. Ведь по сути невозможно поставить чистый эксперимент, который бы это достоверно доказал. Так что под случайностью мы скорее понимаем непредсказуемость. И псевдослучайность по примеру выше работает как настоящая случайность ровно до тех пор, пока ты не знаешь, как она устроена.

Если тема интересна — расскажу про ТГСЧ и КГПСЧ: генераторы, которые используются в защите данных и криптографии. Ну и хорошими постами делись с друзьями — «нам нужно больше золота подписчиков».

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

🌱 Seed-рандом: один номер — весь мир

Minecraft. Ты вводишь число при создании мира и получаешь конкретный ландшафт.
Через год вводишь то же число — тот же ландшафт. Это seed.

Seed — это просто начальное значение для PRNG. Пока генератор тот же,
последовательность всегда идентична.

Практический паттерн: отдельный генератор для каждой системы

public class SeededRandom
{
    private System.Random rng;
    public int Seed { get; private set; }

    public SeededRandom(int seed)
    {
        Seed = seed;
        rng = new System.Random(seed);
    }

    public int Next(int min, int max) => rng.Next(min, max);
    public float NextFloat()          => (float)rng.NextDouble();
}

// Каждый регион карты — свой генератор:
var dungeonRng  = new SeededRandom(worldSeed ^ 0xDEAD);
var lootRng     = new SeededRandom(worldSeed ^ 0xBEEF);
var enemyRng    = new SeededRandom(worldSeed ^ 0xCAFE);

XOR с разными константами гарантирует, что генераторы идут по разным дорожкам,
но оба воспроизводимы при известном worldSeed.

Три применения:
→ Процедурные карты — один seed = один мир
→ Реплеи — записываешь только ввод игрока + seed, а не весь стейт
→ Отладка — нашёл баг? Скажи seed разработчику, он воспроизведёт

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

🏰 Процедурная генерация: рандом с правилами

«Процедурная генерация» — не просто случайные числа. Это рандом,
ограниченный правилами так, чтобы результат был играбелен.

Простейший пример — комнатный dungeon:

Шаг 1. Создай сетку N×M, заполни стенами (1).
Шаг 2. Попробуй разместить K случайных прямоугольников-комнат.
Если прямоугольник не пересекается с уже размещёнными — добавь.
Шаг 3. Соедини центры соседних комнат коридорами (L-образный тоннель).
Шаг 4. Поставь старт в первую комнату, выход — в последнюю.

void GenerateDungeon(int seed)
{
    var rng = new SeededRandom(seed);
    var rooms = new List<RectInt>();

    for (int i = 0; i < MAX_ROOMS; i++)
    {
        int w = rng.Next(MIN_SIZE, MAX_SIZE);
        int h = rng.Next(MIN_SIZE, MAX_SIZE);
        int x = rng.Next(1, width  - w - 1);
        int y = rng.Next(1, height - h - 1);
        var room = new RectInt(x, y, w, h);

        if (!rooms.Any(r => r.Overlaps(room)))
        {
            CarveRoom(room);
            if (rooms.Count > 0)
                CarveCorridors(rooms.Last(), room, rng);
            rooms.Add(room);
        }
    }
}

Секрет «не сломанного» уровня: правила ограничивают, рандом заполняет.
Именно это делает Spelunky, Enter the Gungeon, Dead Cells — каждый запуск свой,
но всегда проходимый.

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

🗺️ Два других способа генерировать уровни

Комнатный dungeon — самый простой метод.
Вот ещё два, которые дают другой визуальный стиль.

BSP (Binary Space Partitioning)
Делит пространство пополам рекурсивно, как оригами.
Каждая «половинка» становится комнатой. Переходы между ними — двери.
Результат: более прямоугольные, «архитектурные» уровни.
Используют: Nethack, классические roguelike.

Корень → [левая половина] [правая половина]
         ↓                   ↓
         [комн.] [комн.]   [комн.] [комн.]

Cellular Automata (клеточные автоматы)
Заполни сетку случайными стенами/полом (50/50).
Потом повтори правило N раз:
«Если у клетки ≥ 5 соседей-стен — она стена, иначе — пол»
Результат: органичные пещеры, плавные очертания.
Используют: Dwarf Fortress, Don't Starve для биомов.

// Один шаг клеточного автомата
for (int x = 1; x < w-1; x++)
for (int y = 1; y < h-1; y++)
{
    int walls = CountWallNeighbors(x, y);
    nextGrid[x,y] = walls >= 5 ? 1 : 0;
}

Выбор метода зависит от стиля игры:
→ Dungeon / RPG → комнаты или BSP
→ Survival / Open world → cellular automata

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