Dev Math

Перлин пофиксил свой шум в 2001-м. А потом запатентовал фикс

Три поста я рассказывал вам про шум Перлина. Чтож, у него два изъяна.

Первый: его узор тайком выстраивается по осям. Шум считается по сетке-клеточкам, и бугры на нём тянутся
по горизонтали и вертикали, будто прилипли к тетрадному листу. На горах незаметно, а на ровной воде или в анимации глаз уже ловит эту «решётку».

Второй: он дорожает с каждым измерением. 2D-шум — плоская картинка (карта высот). 3D — объём: так в Minecraft режут пещеры. 4D — объём, который ещё и движется во времени (дым, бегущие облака); четвёртая ось — время. А чтобы взять значение, шум перебирает все углы клетки — 2ⁿ штук: 4, 8, 16. Каждое измерение удваивает счёт.

И знаете, кто это починил? Сам Перлин. В 2001-м он выкатил
Simplex-noise, и фикс почти издевательски прост: резать пространство не на квадраты, а на треугольники (в 3D — тетраэдры). Углов у них не 2ⁿ,
а n+1: 3, 4, 5 вместо 4, 8, 16. И «решётка» по осям заодно пропадает.

А что забавно: этот фикс Перлин запатентовал (US 6 867 776). И индустрия годами использовала обходной шум — OpenSimplex (Курт Спенсер, 2014), лишь бы не судиться. Патент истёк только в январе 2022-го — но OpenSimplex уже прижился.

Для рельефа классики хватает с головой. А в 3D, дыме и облаках — цена Перлина кусается.

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

Тизер-трейлер "Приключения Дейва"

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

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

Одна октава шума — скучный холм. Горы начинаются со сложения

Шум Перлина из прошлого поста сам по себе — пологие холмы. Ни скал,
ни хребтов, ни мелкой шероховатости. А в природе деталь живёт на
каждом масштабе — это фрактал. Так что шум складывают сам с собой на
разных частотах:

float sum = 0.0, amp = 0.5, freq = 1.0;
for (int i = 0; i < 6; i++) {
  sum  += amp * noise(p * freq);
  freq *= 2.0;   // частота ×2 (lacunarity)
  amp  *= 0.5;   // вклад ×0.5 (gain)
}
// sum — это fBm, фрактальный шум

Шесть строк — и «капля» становится правдоподобным хребтом. А подать
шум на вход самому шуму, fbm(p + fbm(p)) — гребни завихряются, и из
той же функции выходят облака, мрамор, лава. Этот приём, domain
warping, — фирменная магия Иниго Килеза (если не слышали — сооснователь
Shadertoy и автор iquilezles.org, «библии» процедурной графики).

Собственно, вся процедурная природа — базовый шум плюс две надстройки:
сложить октавы и исказить координаты. Облака в Horizon Zero Dawn,
рельеф Minecraft, мрамор в текстурах — всё отсюда. Только не берите
мало октав (выйдут «пузыри») и не сэмплите через random на пиксель
(мерцающая каша).

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

Шум Перлина — это не случайные числа. Это случайные стрелки

Наивная идея «шума»: накидать
в узлы сетки случайные значения
и интерполировать между ними.
Это value noise — и он сразу выдаёт себя: сквозь картинку проступает сетка, всё распадается на квадраты.

Перлин сделал хитрее. В узле лежит не число, а случайное направление — градиент, стрелка.
Значение в точке — это скалярные произведения этих стрелок на векторы «от угла к точке», плавно смешанные специальной кривой:

float n00 = dot(g00, p - c00);   // стрелка · смещение
float n10 = dot(g10, p - c10);   // ...для всех 4 углов клетки
float n01 = dot(g01, p - c01);
float n11 = dot(g11, p - c11);
vec2  f = fade(fract(p));        // гладкая кривая, НЕ линейная
float n = mix(mix(n00,n10,f.x), mix(n01,n11,f.x), f.y);

В узлах значение строго ноль — оттого ни «пятен» на решётке,
ни швов.

А главное: стрелки не бросаются заново, а считаются хешем от целых координат и сида. Тот же узел при том же сиде — та же стрелка. Всегда. Собственно, поэтому один seed в Minecraft рисует одинаковый мир у всех.

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

Горы, облака и мрамор в играх никто не рисовал — это одна функция

Откройте Minecraft и полетайте над миром. Горы, пещеры, береговые линии — этого рельефа нет ни в одном файле. Его никто не рисовал и не сканировал. Это значения функции: подаёте ей координаты точки — получаете высоту.

Казалось бы, чтобы получить такую «природную» случайность, достаточно взять random на каждую точку. Ну попробуйте — получите белый шум, ту самую телевизионную «снежинку». Для ландшафта это мусор: каждая точка живёт сама по себе, ни холмов, ни долин, один хаос. Фокус,
собственно, не в случайности, а в ГЛАДКОЙ случайности — у соседних точек значения близкие. Вот из этого и получается логичный рельеф.

Имя у фокуса есть: шум Перлина. Кен Перлин придумал его ещё в 1982-м. Он бесился от «пластмассового» вида графики, над которой работал для «Трона», и захотел управляемую случайность (позже за неё дали
технический «Оскар»). Сегодня на ней стоит половина видимой природы в
играх: рельеф и пещеры Minecraft (тот же seed — тот же мир у всех), облака в Horizon Zero Dawn, мрамор и огонь в текстурах.

На неделе разберём, как функция от (x, y) превращается в горный хребет и почему один и тот же seed в Minecraft всегда даёт один и тот
же мир. 🔥

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

Математика невезения: как игры подкручивают случайность, чтобы она ощущалась честной
https://dev-math.ru/articles/lootboxes/

Всю неделю мы разбирали рандом по кусочкам — сегодня забираем всю кухню разом. Внутри вывод констант, пять интерактивов прямо в браузере и цифры, после которых надпись «шанс 1%» читается иначе. Жду 🔥 и репостов друзьям 😆

Игроки читают «1% дропа» как «1 из 100», а random в игре считают честным броском — оба утверждения неверны, и на этом зазоре держатся и фрустрация, и часть монетизации. В статье случайность разобрана как три слоя.

Первый — генератор: LCG в одну строку, детерминизм seed и история pack.png с перебором 2⁴⁸, спектральный тест Кнута и провал RANDU.

Второй — искажение распределения под восприятие: PRD в Dota с численным выводом константы C, pity-системы Genshin и Hearthstone, true hit Fire Emblem, aim assist XCOM и shuffle bag Тетриса.

Третий — экономика дропрейта: геометрическое распределение, 385 против 267 кейсов до ножа CS, кривая 1−(1−p)^N и регулирование лутбоксов от Китая 2017-го до отменённого штрафа EA в Нидерландах. Разработчик получает карту выбора инструмента — голый PRNG, PRD, pity или shuffle bag — и честный список цен, которыми оплачивается каждое сглаживание дисперсии.

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

Шанс 50/50 выбить нож в CS стоит 660 $

Шанс ножа в кейсе — 0,26%. Эту цифру Valve не публиковала: сообщество годами восстанавливало её по статистике анбоксингов. В 2017-м Министерство культуры Китая обязало раскрывать вероятности лутбоксов, и таблицу выложил Perfect World — издатель, через которого Valve работает в Китае.

Чтож, посчитаем. Памяти у кейсов нет, попытки независимы: шанс хотя бы одного ножа за N кейсов — 1−(1−0,0026)^N. Сотня кейсов — должно же хватить? Конечно же нет: 23%. Монетка 50/50 набегает только к 267-му кейсу — те самые 660 $ ключами. Уверенные 99% — 1769 кейсов, около 4 400 $.

Ну и моё любимое: остаться без ножа после двух тысяч кейсов вдвое вероятнее, чем выбить его из первого же. Не верите — посчитайте. Пустой кейс — это 99,74%. Возведите в степень 2000: остаётся 0,55%. А нож с первой попытки — те самые 0,26%. Шанс «всё ещё пусто» тает вдвое каждые 266 кейсов и нуля не достигает никогда: из 100 000 человек, открывших по 2000 кейсов, около 550 останутся ни с чем — хотя «в среднем» нож выпадает на 385-м.

И вот что я в этой истории так же люблю: та же Valve в Dota подкручивает криты в вашу пользу, лишь бы серия промахов не испортила вам вечер. В кейсах серия неудач продаёт ключи, поэтому кейс номер 2000 ничем не отличается от первого. Даже Genshin даёт гарантию на 90-й крутке. Тут — ни на какой.

Шансы при этом честные, жульничать тут и не нужно.

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

По иконке текстурпаков фанаты вычислили seed мира Minecraft через десять лет после скриншота

pack.png видел каждый фанат майнкрафта: холм, озеро, водопад. Откуда кадр — было неизвестно, пока в 2020-м ютубер SalC1 не спросил об этом вслух. Дальше сообщество устроило расследование.

По облакам и ориентации текстур блоков восстановили ракурс, заодно вычислили способ съёмки: Print Screen и кроп до 512×512. Ключевой факт: рельеф зависит только от нижних 48 бит сида — пространство перебора 2⁴⁸, 281 триллион вариантов. Фильтром стало перемешивание песка с землёй в кадре: сгенерировал кусок мира — сравнил. Подняли распределённый счёт на BOINC, 3700 добровольцев, три дня — seed найден: 3257840388504953787. В этот мир можно зайти и встать в точку, откуда сделан кадр.

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

В статье — что у таких генераторов внутри.

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

«Ну сейчас-то повезёт» — это ошибка игрока. А в Dota — фича.

Чтож. Начнём неделю лутбоксов и дропрейта.

Предмет с «25% крита» на первом ударе критует примерно в 8,5% случаев. Цифра в тултипе не врёт — врёт интуиция о том, как она считается.

В Dota крит — не честная монетка, а система с памятью (pseudo-random distribution). То самое «ну сейчас-то повезёт» здесь буквально зашито в формулу: каждый удар без крита поднимает шанс следующего. Старт ~8,5%, дальше выше, к двенадцатому удару крит гарантирован. В среднем по дистанции выходят те самые 25%.

Зачем так? Честные 25% дают жирный хвост невезения: не критануть восемь раз подряд — это 10% случаев, и встречается оно сплошь и рядом. Каждый такой стрик игрок читает как «игра жульничает». PRD режет именно хвост: дольше без крита — ближе крит. Но за это вы слабее в начале серии — короткие неудачные полосы как раз учащаются. По сути, вы не стали критовать чаще, вы перестали попадать в катастрофические серии. Это обмен дисперсии на предсказуемость, который продаётся как «честность».

В статье — вся кухня: как «случайность» умещается в одну строку кода, почему «1% дропа» это совсем не «1 из 100», и где эта математика правит уже не восприятие, а ваш кошелёк 🙂

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

Дейв Математик #1. Физика прыжков.

Я решил попробовать сделать комикс. Посмотрим как зайдет. Встречайте Дейв Математик! Олдскульный разработчик игр, который в процессе дебага попадает в свои игровые миры и решает в них проблемы с помощью математики.

Ставьте огоньки, если формат зайдет, поделаю разных комиксов раз в неделю или под вдохновение.

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

P.S. И накидайте бустов https://t.me/easy_dev_math?boost чтобы можно было публиковать больше стори на канале :)

#матразбор #комикс

Матчмейкинг по-простому: Сигнал и шум
https://dev-math.ru/articles/matchmaking/

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

Главная мысль — на все полвека одна. Истинный скилл это скрытый сигнал, который нельзя увидеть напрямую. Один матч — шумная однобитная выборка из него. А рейтинг — это фильтр, который оценивает и сам сигнал, и собственную неуверенность в нём. Вся эволюция ELO → Glicko → TrueSkill ровно про это: как сделать фильтр умнее. ELO — фиксированное доверие к одному матчу (тот самый K) и логистическая сигмоида, откуда берётся «400 очков = ×10 шансов». Glicko добавляет второе число RD — адаптивный K, который сам понимает, про кого мы знаем мало. TrueSkill описывает скилл целым гауссовым колоколом N(μ, σ) и раздаёт его по команде через factor graph. В финале — кто это крутит в проде: Chess.com и Lichess на Glicko, Rocket League, Halo на TrueSkill.

Не забываем делиться статьей с друзьями, если она понравится — это помогает развитию канала. Больше подписчиков богам подписчиков. Ну и ставим огоньки естественно. Автор работает за классы :) Я стараюсь в одиночку на пару с клодом делать качественные материалы и хочется чтобы их увидело как можно больше людей.

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

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

Одного числа мало. Рейтингу нужна погрешность

В среду мы оставили ELO с фиксированным K — фильтром, который не знает, когда сам себе не доверяет. Новичок и ветеран с рейтингом 1500 для него одинаковы, хотя первое — это «без понятия», а второе — «проверено сотней матчей».

Лечится одним движением: добавьте к рейтингу второе число — насколько система в нём уверена. Это и есть Glicko (Марк Гликман, 1995): рядом с рейтингом живёт RD, разброс оценки. И вот тут сигнал/шум возвращается красиво — RD это, по сути, адаптивный K. Большой RD (новичок или вернулись после года) → рейтинг идёт крупными шагами, жадно ловит сигнал; маленький (тысяча партий за плечами) → шаги мелкие, шум давится. K больше не подбирают руками, он вытекает из уверенности. И сам RD падает, когда вы играете, и растёт за время простоя — старые данные протухают.

TrueSkill (Microsoft Research, 2006, под Halo на Xbox Live) доводит идею до предела: скилл — не точка, а нормальное распределение N(μ, σ), где σ — та же неуверенность, что RD. Матч смещает и сужает колокол. И — чего ELO не умел в принципе — перформанс команды складывается из распределений игроков, так что через factor graph система раздаёт +/− по всей пятёрке после одного матча 5v5.

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

В статье — полный разбор: апдейт TrueSkill через factor graph на одном примере, Glicko-2 с псевдокодом и интерактив, где вы сами крутите рейтинги и σ и смотрите, кого алгоритм считает честной парой.

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

Рейтинг — это не скилл, а оценка скилла

Ваш истинный скилл — это число, которого никто никогда не видел. Ни вы, ни сервер. Измерить напрямую нельзя — только догадываться по результатам матчей.

А один матч — это плохие данные. Выиграли, потому что сильнее? Или соперник тильтанул, лагнул, один раз зевнул в CS? В одной игре сигнал (ваш скилл) намертво смешан с шумом (везение). Это всего один бит информации о вещественном числе — всерьёз оценивать по нему нечего.

И тут немного надо понимать логику сигнал-шум. Вы сыграли 1000 матчей. У вас есть ваш скилл (сигнал), а есть удача (шум) в любой игре. Тут уже сигнал будет виден ярче, так как всегда чем больше выборка, тем меньше влияние шума на сигнал. Но кроме этого шум мы умеем математически фильтровать, в попытках найти истинное значение сигнала.

Собственно, поэтому ELO не «считает» скилл, а фильтрует его из шума:

E_a = 1 / (1 + 10 ** ((R_b - R_a) / 400))  # модель предсказывает исход
R_a = R_a + K * (S_a - E_a)                # факт минус прогноз → поправка

Первая строка — прогноз модели. Вторая — поправка: та же механика, что у экспоненциального сглаживания, новая оценка = старая плюс доля ошибки прогноза S_a − E_a. K — размер этой доли, по сути learning rate: насколько доверять одному матчу.

И тут весь фокус фильтра. Большой K хватается за каждый результат: два равных игрока, каждый матч — монетка, но при K=40 рейтинг скачет на ±20 за партию, хотя скилл не двигался. Это шум, просочившийся в число. Маленький K усредняет много игр — гладко, но реальный рост догоняет медленно. Поэтому FIDE душит шум топам, опуская K до 10: у Карлсена скилл давно известен, дёргать рейтинг из-за одного зевка незачем.

Загвоздка в том, что K фиксированный. Умный фильтр сам бы понимал, когда он не уверен — и доверял данным, а когда уверен — глушил шум. А вот об этом мы и поговорим в статье.

🔥 — если поняли «скилл = сигнал, отфильтрованный из шума». Ну и не забываем делиться с друзьями, это помогает развитию канала.

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

Скрытое число

В голосовании за тему на втором месте шло ELO и MMR, так что это неделя будет про них. Прямо сейчас у вас есть рейтинг. Даже если вы его ни разу не видели и не сыграли ни одной ранкед-игры — система всё равно держит про вас число.

Заходите вечером в CS или Dota, жмёте «Найти игру» — и через минуту перед вами девять других людей. Откуда сервер знает, что подходят именно эти девять?

Под капотом — математика, которую придумали для шахмат в 1960-х. Та самая, по которой считают рейтинг Магнусу Карлсену: FIDE приняла её в 1970-м, отсюда слово ELO (в честь Арпада Эло, который и придумал эту систему). А дальше она расползлась по всему соревновательному геймдеву — Halo, Rocket League, Lichess, LoL. Движки рейтинга у всех разные, идея одна: у игрока есть скрытое число (MMR), алгоритм сводит близких и пересчитывает всех после матча.

И вот тут начинается интересное. Шахматист играет 1v1 годами. А матчмейкер в шутере должен за секунды собрать из миллионов человек онлайн партию 5v5 с исходом близким к 50/50 — да ещё с поправкой на регион, пинг и штрафы за поведение. По сути это уже не сортировка по рейтингу, а вероятностная модель.

На неделе разберём её целиком: формула ELO в две строчки, почему её перестало хватать, и как Glicko с TrueSkill раздают рейтинг команде из пяти человек после одного матча.

🔥 — если хочется узнать, откуда берётся ваш MMR или написать свою систему рейтинга игроков.

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