Тем временем, Apple анонсировали выпуск полной поддержки WebGPU в Safari 26, которая уже в бете

Все Chromium-based браузеры (то есть всё, что не Сафари или Огнелис) уже давно поддерживают на Windows и macOS

Это значит, что ждем только Firefox (работает только в Nightly и не везде) и Chromium на Linux для полной поддержки везде

Новость на самом деле очень важная, потому что Apple тянули с поддержкой WebGL 2 много лет. При этом их браузер второй в мире по популярности после Chrome, то есть они могут легко затормозить развитие технологии, просто не поддерживая ее.

Но тут видимо даже им уже надоел WebGL, раз они так оперативно катят поддержку

Большая поддержка означает большее использование и большие шансы на окончательное принятие стандарта (сейчас он в статусе кандидата, ждут именно использование в браузерах)

А это означает и лучшее развитие упомянутых библиотек-реализаций для этих браузеров, которые можно (и нужно) использовать вне веба для написания графики под десктопы и мобилки

https://webkit.org/blog/16993/news-from-wwdc25-web-technology-coming-this-fall-in-safari-26-beta/

Как же так получилось, кто бы знал...

А мне вот адепты крестов говорили, что никому он не нужен и никто не использует (отдельный мем)

Сорри, но тут я не удержался уж, слишком сочно

Итак, Apple выложили информацию про новый Metal 4, который придет этой осенью с обновлением их операционных систем

Этим релизом они решили почти полностью сломать совместимость с нынешним Metal 3 и прошлыми версиями, ради большей совместимости с концепциями Vulkan и DX12

Теперь из старого API по сути остался только MTLDevice, все остальное изменено. Например, вместо MTLCommandQueue, теперь MTL4CommandQueue

Сделали аллокаторы, таблицы аргументов и прочие сущности, которые раньше только в более сложных API встречались

Главное изменение - теперь все ресурсы требуют ручной синхронизации, никакого автоматического отслеживания, которое было в Metal 3, OpenGL и WebGPU, и спасало от кучи ошибок

Из плюсов - добавили свой аналог DLSS 4, с генерацией кадров, денойзером, апскейлером и тд

И прямо в графическое API добавили поддержку исполнения нейросетей. Там и раньше были Metal Performance Shaders и инструменты отладки для них, но теперь можно прямо посреди процесса отрисовки запускать нейронки через сам Metal напрямую

В итоге, API сделали более дружелюбным к многопотоку и гораздо более похожим на Vulkan и DX12, но ценой кардинального усложнения и несовместимости со старым кодом

Причем Metal 3 уже поддерживал ручное управление ресурсами и прочие оптимизации, но они не были обязательными и не мешали просто использовать API для своих проектов без лишней сложности. А теперь оно становится и более трудным, и обязательным

Понятно, зачем Apple это сделали - они уже давно очень хотят на игровой рынок, и это упростит миграцию игр от крупных студий с Windows, которые и так используют DX12 или, реже, Vulkan

Но для обычных разработчиков, особенно и так пишущих под платформы Apple на Metal, это огромное усложнение и раздувание кода, как мне кажется, будет скорее жирным минусом

С такими новостями WebGPU остается единственным выбором на нативе для одиночек и малых коллективов, когда теперь уже все три нативных API стали слишком переусложнены

По сути, сейчас из простых, но мощных вариантов - только wgpu, dawn, sdl-gpu и blade.

Но у wgpu преимущество, благодаря широкой распространенности и популяризации стандарта, на котором оно основано

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

Как говорится, пост по просьбам трудящихся

Известные мне способы процедурной генерации игровых миров:

1. Просто а-ля майнкрафт, всё из кубов. Тут всё довольно просто, а сама генерация через шумы, например обычный шум Перлина или Вороного. Несколько карт шума с разной детализацией отвечают за ландшафт, биомы и прочее

2. Простой ландшафт в 3д, полностью процедурный, делают через марширующие кубы или тетраэдры. Кубы были открыты первыми и запатентованы, и патент протух только недавно, поэтому долго использовали свободный вариант на тетраэдрах. Например в Deep Rock Galactic изначальная генерация карты делается именно марширующими тетраэдрами

3. Если хочется гибко изменять 3д ландшафт - CSG, Constructive Solid Geometry. Это много про что, но в данном случае про воксельные миры с плавным редактированием ландшафта. Например в том же Deep Rock Galactic копание и прочие изменения пещер и стен уже во время матча сделаны именно так

4. Если хочется наделать самому какие-то ассеты, из которых потом процедурно строить мир - это WFC, Wave Function Collapse. В 3д или 2д, тут не важно. Звучит страшно, но на самом деле довольно простая штука для понимания, можно видео погуглить. По сути руками делаешь ассеты, потом задаешь правила их размещения ("тайлы с лесом только рядом с тайлами лугов" и тд), а дальше оно генерит тебе мир какого хочешь размера. Townscaper как пример игры на этом. Очень мощная вещь, но в продвинутых 3д вариантах бывает сложно реализовать нормально. Возможность генерировать мир из готовых ассетов тут и минус (нужно их иметь), и плюс - можно гибко подстроить арт дизайн и прочие детали, которые процедурно делать замучаешься

5. Бывают всякие кастомные алгоритмы, например как в Shadows of Doubt. Там процедурное вообще всё - здания, этажи, интерьер помещений, содержимое записок и компьютеров, жители, их работы, предыстории, отношения и так далее. На самом деле это несколько отдельных алгоритмов для разных этапов подобной генерации, например стены, окна и комнаты сами по себе генерируются тайлами 15х15. Тут уже только в девлоги конкретной игры погружаться, чтобы раскопать, как всё сделано

6. Cellular Automata, оно же клеточный автомат. Самым известным примером является игра "Жизнь". Однако применим и в процедурной генерации игр, а точнее для генерации карты пещер или данжей, островов и так далее. Обычно генерируется 2д картинка, которая потом уже используется для следующего этапа 3д генерации

7. Довольно эффективным способом генерации случайных закрытых пространств является использование теории графов. Мы не пытаемся сгенерировать сразу же 3д модель мира, вместо этого мы делаем граф, где вершины - комнаты, пещеры, помещения и прочее, а ребра - коридоры и проходы между ними. Тогда мы можем использовать стандартные алгоритмы на графах для оптимизации путей прохождения, обеспечения ограничений (чтобы комната с боссом была не слишком далеко от точки входа, например), и так далее. А дальше, по уже готовому графу, можно переходить к более подробной генерации деталей, визуальных частей и так далее, как и в клеточных автоматах. Такой способ использует Enter the Gungeon, также отдаленно похож аналог на массивах из Diablo 1

8. Для расположения камней в мире, деревьев в лесу и других подобных объектов, которые должны быть случайно раскиданы, но не ближе заданной дистанции друг к другу, можно использовать Poisson-disc Sampling. Результат выглядит гораздо более естественно, чем при использовании простой карты шума

9. Еще один, на этот раз очень простой для реализации алгоритм - Random Walk. Быстро работает, дает гарантированно соединенные между собой области, банально проще клеточных автоматов, шумов Перлина и Вороного, и так далее. Конечно, результат часто не впечатляет, но для простых пещер вполне подойдет

В большинстве игр используются сразу несколько алгоритмов. Например в Lost Flame используют и шум Перлина, и клеточные автоматы, и обычной выбор типа тайла по псевдослучайному генератору. А в Nuclear Throne используют клеточные автоматы, Poisson-disc Sampling и Random Walk

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

Разбавлю поток информации про графику и геймдев немного

Пару раз спрашивали, что такое формальная верификация алгоритма, и зачем она используется.

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

Это позволяет математически доказать, что алгоритм валиден, не может находиться в некорректном состоянии ни при каких условиях, и так далее

То есть, проверяется только отсутствие ошибок в самой идее, в спецификации. Их отсутствие в последующей реализации кодом уже никто не гарантирует

Есть много языков для такого, перечислю несколько знакомых мне:

1. Rocq, он же раньше назывался Coq. Более старый и широкомасштабный. Построен больше на описании теорем и их доказательстве

2. TLA+, создан Лэмпортом и больше похож на бред математика, однако обладает собственной IDE на базе Eclipse под названием TLA Toolbox, а также отдельным набором инструментов проверки спецификаций. Больше используется для описания систем и процессов, чем теорем, хотя оно тоже возможно

3. Pluscal. По сути то же самое для TLA+, чем Typescript является для Javascript. То есть надстройка, которая превращается в своего более урезанного и проблемного собрата после сборки. В отличие от остальных, уже отдаленно напоминает языки программирования. Так как превращается в TLA+, то использует все те же инструменты и ту же IDE

Я больше знаком с TLA+/Pluscal, поскольку их используют для верификации распределенных алгоритмов, планировщиков задач и так далее

Например, Amazon в своих AWS с помощью TLA+ нашли баг, затрагивающий их сервисы S3 и DynamoDB, который требовал 35 шагов для воспроизведения и не был обнаружен ни тестами, ни двумя код ревью

По сути, процесс верификации на TLA+/Pluscal выглядит так:

1. Мы описываем на выбранном языке нашу систему, делаем спецификацию. Алгоритм работы, поведение, степень параллельности и тд

2. Задаем список ограничений, выполнение которых будем отслеживать. Отсутствие дедлоков, недоступность не более двух узлов, пересечения кворумов, приоритеты процессов - все, что угодно. Тут же задаем теоремы, доказательство которых нас интересует

3. Запускаем автоматическую верификацию нашей спецификации на каких-то исходных данных. Инструмент проверяет, что наши ограничения выполняются для любого возможного состояния системы в любой момент времени, что теоремы доказаны, и так далее. Если что-то не так - мы увидим, в каком состоянии оказалась система в момент нарушения какого-то ограничения, что даст нам возможность скорректировать баги в нашей спецификации

На Rocq я ничего не верифицировал, но со стороны там процесс другой и больше строится на пошаговом дедуктивном доказательстве теорем

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

Тем временем, Mozilla готовится к включению WebGPU в релизе FIrefox 141 на Windows

Остальные платформы подъедут позже, но для Windows пулл реквест с включением уже на ревью и ожидается в следующем выпуске браузера

С такими темпами адаптации, можно сказать, что через пару-тройку лет должно быть доступно уже повсеместно

Накидаю небольшую памятку по вероятностным структурам данных

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

Самый наверно известный представитель - Фильтр Блума (Bloom Filter). Позволяет очень быстро проверить принадлежность элемента ко множеству, при этом может давать ложноположительные срабатывания, но никогда не ложноотрицательные. Используется много где, например в базах данных для быстрой проверки, входит ли первичный ключ в сегмент или файл данных на диске без поиска по нему. Если фильтр сказал, что ключа там нет - его там гарантированно нет, что позволяет существенно оптимизировать время поиска (например в СУБД на базе LSM, где каждая SSTable хранится в отдельном файле). Также полезно для реализации кешей, блеклистов и прочих случаев, когда нам нужно быстро исключить возможность принадлежности элемента ко множеству. Ключевым свойством является полная независимость сложности поиска элемента от количества элементов в фильтре. Вдобавок, всего 10 бит на одно хранимое значение снижают вероятность ложноположительного обращения до 1%

Также есть развитие идей фильтра Блума в виде Cuckoo Filter и Quotient Filter, которые уже поддерживают удаление элементов, но более сложны в реализации и потребляют больше памяти.

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

Далее идет HyperLogLog, занятная штука, позволяющая найти количество уникальных элементов во множестве, но имеющая незначительную вероятность ошибки (около 1% в типичных применениях). Всего 1.5 кбайт памяти достаточно для анализа более чем 10^9 элементов. Используется для подсчета уникальных посетителей систем, аналитики и работы с большими данными

Также есть T-Digest, который может быстро найти распределение элементов по перцентилям, однако тоже имеет некую погрешность. Часто используется в A/B тестах, иногда в машинном обучении и других сферах

Еще можно добавить Lossy Counting, позволяющий найти N самых частых элементов во множестве с минимальными затратами памяти за счет удаления самых редких элементов в процессе работы. Чаще всего встречается в разного рода аналитике

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

Например, Google Chrome использует фильтры Блума для быстрого распознавания вредоносных URL, а Medium для своей рекомендательной системы, отсеивая уже просмотренные посты. В то время как HyperLogLog напрямую доступен в Redis через команды pfadd и pfcount для подсчета количества уникальных событий

Эти структуры данных явно не относятся к тем, что часто нужны на практике, но знание об их существовании может выручить в том редком случае, когда они все же пригодятся

Последнее время стараюсь если и прокрастинировать, то все равно делать что-то полезное

Например, вместо диссертации пишу многострадальный гайд по графике на wgpu

Все равно ощущение, что займет это годы, но так хоть какой-то прогресс будет

А если летом защищусь и решу вопрос с призывом, то еще больше времени появится

Дописал вторую главу туториала, вроде бы

Постоянно нахожу, что еще можно дописать или отредактировать, но пока вроде всё устраивает

Вышло 3954 слова без учета блоков кода или 4627 с ними (диаграммы тоже считаются за блоки кода, поскольку они в формате Mermaid)

Надеюсь, что следующие главы будут поменьше, но как будто ощущение, что нет)

Такими темпами, может быть закончу базовый раздел в этом десятилетии)

откопал старое сообщение про типы рендера, решил сюда закинуть для истории

1. Forward render, когда все просто рисуется напрямую (если вы "просто рендерите", то, скорее всего, у вас именно он).

Конечно, в современных движках уже используются модифицированные алгоритмы (Tiled Forward, Clustered Forward, Forward+ и тд), но общий принцип плюс-минус один.

Из плюсов:

- легко работать с прозрачностью

- поддерживает msaa

- имеет низкие требования к пропускной способности видеопамяти

Из минусов:

- плохо масштабируется с увеличением количества источников света в сцене. В целом больше зависит от сложности сцены, чем от размеров экрана.

- все современные продвинутые реализации требуют компьют шейдеров.

- методы постобработки все равно иногда требуют данные, которых нет в форварде, и приходится мучаться с z препассами и прочим, по сути вводя куски деферред подхода для части данных (например гораздо тяжелее SSAO и SSR реализовать, чем в деферреде).

- плохо переживает мелкие треугольники на экране

2. Deferred render, когда всё рисуется в два этапа - сначала заполняем специальный g-буфер данными, потом на базе него уже рисуем саму сцену. Именно этот способ чаще всего используется в современных игровых движках, из-за простоты и преимуществ

Из плюсов:

- про него очень много информации

- работает даже на очень древнем железе

- масштабируемость зависит больше от размера экрана, а не сложности сцены.

- легче переживает мелкие треугольники на экране.

- постобработке нужны данные из g-буфера, а тут они уже и так есть, то есть легче всякие красивости наводить, включая PBR.

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

из минусов:

- msaa не работает, сглаживание тут в принципе тяжело сделать нормально.

- прозрачность тоже очень тяжело реализовать, настолько, что часто делают отдельный форвард проход для прозрачных объектов.

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

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

например, Doom 2016 сделан на гибридном рендере. У них сначала маленький пре-пасс для заполнения куска g-буфера, а потом используют его + данные рендера прошлого кадра для рендера текущего, из-за чего отражения отстают на один кадр от самой сцены

4. Новый подход через буфер видимости.

Он чем-то похож на деферред, но вместо рендера текстур в g-буфер, там заполняется числовой буфер с идентификаторами объектов и их треугольников, что позволяет их очень эффективно упаковать, например, в u32. Вообще про это есть доклад от Интела, но уже есть и реализации в разных самописных движках, например цикл из 4 статей про реализацию на DirectX 12 (не самую оптимальную кстати). И в целом есть еще разные варианты этого алгоритма, от разных авторов в разных статьях/докладах

из плюсов:

- работает даже быстрее деферреда, и очень хорошо масштабируется.

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

- очень нетребователен к пропускной способности видеопамяти, если реализовывать "чистый" буфер видимости, а не использовать его для заполнения g буфера и последующего деферреда

из минусов:

- гораздо сложнее реализовать, чем все предыдущие подходы. Тут и куча производных, и барицентрические координаты, и еще всякое алгоритмическое, графы, и прочее

Тот самый доклад Интела про Visiblity Buffer

и упомянутая серия статей про реализацию на DirectX 12

она не совсем оптимальна, потому что, как и в Unreal Engine, автор использует visibility buffer только для наполнения g буфера, который потом идет в обычный деферред пайплайн. А это, по сути, обнуляет половину преимуществ visibility buffer по сравнению с использованием только его вместо деферреда, таких как низкая зависимость от пропускной способности видеопамяти

http://filmicworlds.com/blog/visibility-buffer-rendering-with-material-graphs/

в целом, Nanite из Unreal Engine является мутацией подхода c Visibility Buffer, но он не очень эффективен.

Потому что при использовании visibility buffer нам вообще не нужен g-буфер, мы можем напрямую работать с идентификаторами в компьютах и очень сильно всё ускорить.

А Nanite использует буфер видимости исключительно чтобы ускорить заполнение g-буфера, который потом используется уже у них в обычном деферред пайплайне.

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

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

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