Мы запустили Doom на SQL

Коротко о главном: мы переписали движок и рендерер классического Doom на SQL, заставив игру исполняться прямо внутри СУБД. На моей машине игровой процесс выдает эталонные 35 FPS, а графический модуль формирует полноценную карту кадров 320×200 с частотой от 60 Гц и выше. Python здесь отвечает исключительно за тайминги, опрос клавиатуры и вывод получаемой растровой картинки на экран. Многопользовательский режим функционирует в полном объеме.

SQLDoom под управлением AMD Ryzen 7 7840U

Испытать игру можно прямо сейчас: доступен Deathmatch на четыре слота по принципу живой очереди.

SQLDoom на серверах в Евросоюзе

SQLDoom на серверах в США

Перед вами бесплатная shareware-версия первого эпизода. Если все места заняты, вы автоматически перемещаетесь в лист ожидания. Даже находясь в очереди, вы можете отправлять SQL-запросы для мониторинга текущего состояния игрового мира.

SQLDoom

В прошлом году я презентовал проект DOOMQL [Github]. Он выдавал 30 кадров в секунду в текстовом ASCII-режиме, отдаленно напоминающем оригинал, и публика тепло его приняла. Тем не менее многие справедливо отмечали, что из-за использования рейкастинга проект куда ближе к Wolfenstein 3D, чем к Doom. Настоящий же Doom опирается на BSP-деревья, что позволяет сортировать объекты по глубине с минимальными затратами ресурсов и поддерживать текстурирование стен под произвольными углами наряду с разной высотой полов.

Эта идея не давала мне покоя, и я наконец воплотил в жизнь самый настоящий Doom, работающий исключительно на базе SQL.

Основные принципы

Для начала зафиксируем ключевые требования:

1. Визуально игра должна неотличимо походить на классический Doom. Оглядываясь назад, признаю, что DOOMQL выглядел мягко говоря неказисто.

2. Что еще важнее — проект обязан дарить те же ощущения и азарт, что и оригинальная игра.

3. Графический конвейер должен строиться исключительно на SQL. Допустимый результат выполнения SQL-запроса — это таблица или растровое поле, содержащее точные RGB-коды пикселей.

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

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

Архитектура решения

Роль Python сознательно минимизирована (согласно правилу 5). Единственный скрипт задействует библиотеку pygame для перехвата управления, вывода растра и поддержания игрового ритма на уровне 35 тактов в секунду. Вся бизнес-логика, текущее состояние мира и рендерер инкапсулированы внутри базы данных.

                         Python
                 ввод / тайминги / вывод
                    |              ^
                    |              |
         шаг игровой симуляции   запрос кадра
                    |              |
                    v              |
          +----------------+  +----------------+
          |                |  |                |
          | Игровая логика |  |  SQL-рендерер  |
          |     на SQL     |  |                |
          +-------+--------+  +--------+-------+
                  |                    ^
                  |                    |
                  v                    |
             +-----------------------------+
             |                             |
             |  таблицы игрового состояния |
             |                             |
             +-----------------------------+

Эти два потока намеренно разведены: игровая симуляция работает строго на частоте 35 Гц, в то время как рендерер представляет собой чистую функцию над таблицами состояний. Клиент волен запрашивать новые кадры с любой удобной частотой (например, максимально возможной).

Импорт игровых ресурсов

К счастью, формат файлов WAD, применяемый в Doom, изначально обладает высокой степенью реляционной структурированности.

Пары вершин VERTEX объединяются в линии LINEDEF, которые ссылаются на две стороны SIDEDEF. Стороны ограничивают сектор SECTOR, содержащий различные игровые объекты THING — логика предельно прозрачна. Перенос всего содержимого WAD в СУБД оказался на удивление тривиальной задачей и потребовал около тысячи строк на Python. Полная загрузка первого Doom на моем ноутбуке занимает всего порядка 18 секунд.

Ниже приведен пример запроса, отрисовывающего карту E1M1 в ортогональной проекции сверху:

WITH wall AS (
  SELECT round((v1.x + (v2.x - v1.x) * t / 32.0) / 48) AS col, -- 48 единиц на один символьный столбец
         round((v1.y + (v2.y - v1.y) * t / 32.0) / 96) AS row, -- соотношение сторон шрифта 2:1
         l.left_sd_id < 0 AS solid -- признак непроходимости односторонних линий
  FROM linedefs l, generate_series(0, 32) AS t        -- разбиваем каждый отрезок на 32 шага
  JOIN vertexes v1 ON (v1.map_id, v1.id) = (l.map_id, l.v1_id)
  JOIN vertexes v2 ON (v2.map_id, v2.id) = (l.map_id, l.v2_id)
  WHERE l.map_id = 1
)
SELECT string_agg(CASE WHEN (col, row) IN (SELECT col, row FROM wall WHERE solid) THEN '#'
                       WHEN (col, row) IN (SELECT col, row FROM wall)             THEN '.'
                       ELSE ' ' END, '' ORDER BY col)
FROM generate_series(-16, 79) AS col, generate_series(-51, -21) AS row
GROUP BY row ORDER BY row DESC;

Результат вывода:

                                                 #####################
                                                 # ..................#
                                                 # . ......         .#
                                                 # . ...... ######  .#
                                              ######         .. ##  .#
                                          #####..  .         .. ##  ##
                                          #  ####### ...... ######  ##########
                                          # ##   # .                ###..  ..##
  ################                       ## #    ###.........######## #####.  ##
###  ........... #                ########..########.........###         #### .##     ######
#  ..           ##########     ####         ##                 ##        #..... #######    ##
#  .          #####  ... ##  ###   #.....#..##    ........      ##########..... ....##.#### ##
#  .     ###.###  ......  ###  .   .        ##  ...      ...             . ......     .#  ##  ##
#  .     ##..  .  ......  ##   .   .        ##  .           .            . ..........  ##  ## ##
#  .     ###.######  ...  ######   #.....#..##  ...        ..            #.    ... ..   # ## ##
#  .           ############    #            ..    ..........             #.......... ...# #  #
###.........     #             #####     #####                           ##..... ... ##.###  #
  ################                 #######   ####.........##.##........####### .#######  ### #
                                                 ###########.#################  #  ####  # # ##
                                                           #.#      ####......  #  # .   ### ##
                                                           #.#################  #  ###########
                                                           ####. .####       #..#
                                                              #####     ######..######
                                                                        #   .    ..  #
                                                                        #   ##...##  #
                                                                        #   ##   ##  #
                                                                        ######..######
                                                                             ####
                                                                             #####
                                                                             #.. #
                                                                             #####

Игровой цикл

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

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

• Считывание и обработка пользовательского ввода (перемещение, обзоры, стрельба).

• Передвижение и атаки противников.

• Подбор различных бонусов и предметов.

• Вылет ракеты из гранатомета и ее полет вперед.

• Расчет радиуса поражения от взрыва снаряда.

• Отрисовка спрайтов врагов.

• Воспроизведение анимаций, покачивания оружия при ходьбе и элементов интерфейса HUD.

Времени на обработку отведено крайне мало: оригинальный цикл функционировал на частоте 35 Гц, выделяя на один такт 1000 мс / 35 = 28,6 мс. Поскольку кадр выводился ровно раз за такт, кадровая частота также ограничивалась отметкой в 35 FPS.

В SQLDoom логика симуляции по-прежнему работает на 35 Гц (для корректной работы всех оригинальных констант), однако процедура отрисовки отделена от нее. Клиент запрашивает кадры в любой момент времени, а между тактами мы производим интерполяцию координат камеры. Таким образом, у нас есть два целевых показателя:

• Вычисление игрового такта каждые 28,6 мс (иначе нарушится общая отзывчивость управления)

• Обеспечение рендеринга на уровне не менее 35 FPS (меньшие значения допустимы, но движение потеряет плавность)

Последовательность тактовых операций

Игровой такт имеет сугубо процедурную природу. Каждый цикл подразумевает выполнение строгого порядка действий. В арсенале CedarDB имеется скриптовый диалект cedarscript, синтаксически близкий к PL/pgSQL, который позволяет заранее составить план выполнения задач для каждого такта.

Ниже представлен фрагмент управляющей функции:

doom_cs_clock(map, p);
let mut plan = doom_cs_plan(map, p);    -- возвращает битовую маску необходимых подсистем

let use_queued = doom_tic_use(map, p, plan);
if (plan & 2) <> 0 OR use_queued { active = doom_cs_activate_specials(map); }
if (plan & 4) <> 0 OR active <> 0 { doom_cs_doors(map, p); }

doom_tic_move(map, p);                  -- полный расчет перемещений или поворота
doom_cs_death(map, p);                  -- обработка гибели персонажей

plan = doom_cs_plan(map, p);            -- перерасчет мира после сдвигов
plan = doom_tic_secrets(map, p, plan);  -- проверка секретов, проходимых линий и подбора предметов
plan = doom_tic_weapon(map, p, plan);   -- состояние арсенала, рейкастинг попаданий, расчет урона
...
if sound_due { doom_cs_sound(map, p); } -- да, звуковое сопровождение тоже задействовано
doom_cs_monsters(map, p);               -- постоянно
doom_cs_sector_fx(map, p);              -- постоянно
doom_cs_thing_physics(map);             -- постоянно

Упомянутый ранее драйвер на Python каждые 1/35 секунды вызывает процедуру SELECT doom_run_game_tic(...).

Каждая вызываемая функция запускает пачку SQL-операторов. Ниже показан фрагмент конечного автомата, отвечающего за искусственный интеллект монстров.

-- Усеченный фрагмент из sql/runtime/functions/26_cs_monsters.sql.
WITH RECURSIVE
  monsters AS ( [...] ),   -- статус жизни, тип и координаты противников
  los      AS ( [...] ),   -- видимость, угол обзора, дистанция с обходом стен
  decision AS ( [...] ),   -- по одной записи на актера: текущий статус и видимость цели
  transitions AS (
    SELECT d.*,
      CASE
        WHEN NOT d.alive AND d.state NOT IN ('die', 'dead', 'xdeath') THEN
          CASE WHEN d.health < -d.max_health AND d.xdeath_frame IS NOT NULL
               THEN 'xdeath'::actor_state ELSE 'die'::actor_state END -- ЖЕСТОКИЙ РАЗРЫВ НА КУСКИ!
        WHEN d.state="stand" THEN
          CASE WHEN d.visible AND d.in_view_cone AND d.dist <= sight_range
               THEN 'see'::actor_state ELSE 'stand'::actor_state END
        WHEN d.state_tics > 1 THEN d.state          -- продолжаем текущую анимацию
        WHEN d.state="see" THEN
          CASE WHEN d.visible AND d.dist <= d.attack_range
                    AND d.attack_cooldown <= 0
               THEN 'missile'::actor_state ELSE 'see'::actor_state END
        [...]                -- die, xdeath, missile, pain, barrel: еще 5 состояний
        ELSE d.state
      END AS next_state
    FROM decision d
  )
UPDATE monster_ai ai
SET state = n.next_state, state_tics = n.next_tics, seq_index = n.next_seq,
    fired_this_tick = n.advances AND n.lands_on_attack_frame
FROM next_values n
WHERE ai.map_id = n.map_id AND ai.thing_id = n.thing_id;

Как видите, этот код напрямую реализует механику из показанного ранее клипа: если враг получает критический урон (CASE WHEN d.health < -d.max_health AND d.xdeath_frame IS NOT NULL), он зрелищно взрывается на фрагменты (THEN 'xdeath'::actor_state).

Производительность тактового процессора

Ниже представлена диаграмма времени выполнения для самого тяжелого игрового такта:

По правде говоря, это самый ресурсоемкий кадр, который мне удалось зафиксировать. Тест проводился на уровне E4M1 в момент, когда 46 активных противников одновременно пытаются атаковать игрока через открывающийся дверной проем. Обработка занимает 10,45 мс, что составляет около 37% от отведенного лимита времени.

Типичный же такт с шестью активными монстрами в среднем отнимает 2,15 мс, или примерно 8% от бюджета. Запас прочности огромный!

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

Более того, реляционный подход заменяет привычные парадигмы: вместо ручного перебора монстров в цикле мы пишем лаконичный конструктор UPDATE ... WHERE condition, позволяя СУБД самостоятельно и автоматически распараллеливать вычисления.

Стоит отметить, что здесь мне наконец стали интуитивно понятны принципы паттерна Entity Component System (ECS). Любая сущность (игрок, монстр, предмет) обладает набором компонентов (координаты, спрайт, характеристики), а изолированные системы (ИИ, физика движения, расчет урона) определяют правила их взаимодействия. ECS во многом завязан на локальность данных и последовательный перебор сущностей с нужными свойствами. Но ведь реляционные базы данных занимаются именно этим десятилетиями! Любой компонент становится отдельной таблицей, а каждая система превращается в операцию update или insert, объединяющую интересующие нас таблицы по ключу сущности.

Рендеринг графики

Каждый отдельный кадр генерируется масштабным SQL-представлением (view), принимающим на вход геометрию уровня, текущее состояние мира и координаты камеры, а на выходе возвращающим готовый буфер. Структура конвейера выглядит следующим образом:

WITH RECURSIVE
  render_context AS (SELECT $1 AS map_id, $2 AS player_thing_id, $3 AS difficulty),
  pos            AS (SELECT $4 AS x, $5 AS y, $6 AS z, $7 AS angle),
  visible_children AS ( ... ),    -- обход дерева BSP, отсечение скрытых сегментов
  clipped, projected, on_screen,  -- проекция геометрии в экранное пространство
  wall_parts, columns, fragments, -- детализация вплоть до пикселей стен
  panel_clips, plane_spans, ...,  -- отсечение полов и потолков через оконные функции, visplane
  thing_pixels, sprite_fragments, -- спрайтовые изображения
  fragment_union, resolved,       -- сбор всех пикселей и выбор ближайших
  view_colored, ui_colored,       -- наложение палитры COLORMAP и панели статуса
  framebuffer AS ( ... )          -- формирование матрицы 64000 строк (x, y, rgb)
SELECT string_agg(rgb, ''::bytea ORDER BY y, x) AS frame_rgb
FROM framebuffer;                  -- блок в 192000 байт в виде одной строки

Реализация насчитывает около 1,3 тысячи строк SQL (без учета комментариев), распределенных по 89 обобщенным табличным выражениям (CTE) — конструкция получилась весьма внушительной!

Несмотря на кажущееся безумие затеи, этот конвейер концептуально близок к оригиналу Doom. У SQL обнаружилось неожиданное преимущество: в исходном коде linux_doom графический модуль занимает порядка 3,3 тысяч строк без комментариев. Иными словами, решение на SQL оказалось примерно в 2,5 раза компактнее. Насколько оправданным был такой подход — вопрос отдельный, к которому мы еще вернемся.

Для начала разберем самые любопытные этапы конвейера:

Слева показано отсечение геометрии по алгоритму BSP, справа — визуализация прорисовки стен и плоских поверхностей (visplane).

Обход дерева BSP

Поскольку в 1993 году аппаратное ускорение с Z-буфером отсутствовало как класс, для корректного наложения текстур Doom был обязан выстраивать строгий порядок отрисовки. Задача решалась изящным способом: мир рисовался от ближних объектов к дальним с одновременным отслеживанием уже занятых пикселей (если стена закрыла участок, монстра за ней рисовать не нужно). Звучит просто, но обеспечить эффективную сортировку всего уровня по глубине — та еще задача.

Doom выполняет упорядочивание с помощью предрассчитанных BSP-деревьев, зашитых в файл doom.wad. Каждый узел дерева представляет собой разделительную линию, рассекающую карту на две полуплоскости. Секторы уровня делятся на множество выпуклых подсекторов по обе стороны от этих линий, формируя древовидную структуру со следующими свойствами:

1. каждый подсектор является листовым узлом;

2. любой подсектор строго выпукл (находясь внутри него, невозможно увидеть стену изнутри);

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

Рекурсивный обход такого BSP-дерева дает порядок подсекторов от передних к задним. Это задает последовательность рендеринга: перекрытые близкими объектами области можно смело пропускать.

Вот как это выглядит на практике:

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

В центральной части видна оптимизация SQLDoom: для ускорения работы мы заранее, на этапе загрузки, вычисляем все возможные пути в BSP-дереве. Для каждой точки пространства каждый шаг содержит направление: передняя часть (0) или задняя (1). Запаковав это решение в тип bigint и отсортировав лексикографически (order by), мы получаем безошибочный порядок вывода спереди назад.

SELECT ssector_id, ROW_NUMBER() OVER (ORDER BY sort_key) AS bsp_seq
FROM (
  SELECT st.ssector_id,
         -- сзади = бит 1 (40 - глубина), спереди = 0.
         SUM(CASE WHEN st.side = fs.front_side THEN 0::bigint
                  ELSE (1::bigint << (40 - st.depth)) END) AS sort_key,
         BOOL_AND(vc.keep) AS visible   -- были ли отсечены родительские ограничивающие рамки?
  FROM node_path_steps st -- материализованное представление путей от корня до подсектора
  JOIN nodes n ON ...
  CROSS JOIN LATERAL (SELECT ... AS front_side) fs -- определяем наше положение относительно линии
  JOIN visible_children vc ON ...
  GROUP BY st.ssector_id
) s WHERE s.visible;

Одна конструкция sum() ... order by заменяет весь рекурсивный спуск! 40 бит с запасом покрывают размеры любой карты: самое глубокое дерево (на уровне E4M8) имеет глубину всего 32 уровня. Если карта не превосходит ванильный Doom в 256 раз, никаких проблем не возникнет!

Если присмотреться, обход BSP параллельно решает задачу отсечения видимости: каждый узел в файле .wad определяет ограничивающий прямоугольник (bounding box) для всех своих дочерних элементов. Доказав, что пирамида видимости полностью помещается внутри этого прямоугольника, мы избавляемся от необходимости обсчитывать поддерево — за это отвечает флаг visible_children.keep. Таким образом, инструкция bool_and(vc.keep) отсекает те подсекторы, чьи предки не прошли проверку.

Все последующие стадии конвейера просто выполняют соединение (join) относительно bsp_seq, гарантируя обработку только видимых зон в строгой последовательности.

Стены и Visplane

Doom идет на хитрость: проект кажется трехмерным, но по сути является 2.5D-игрой. Мир представляет собой плоскую основу с вертикальными стенами и горизонтальными потолками/полами. Это радикально упрощает рендеринг по сравнению с честным 3D-движком:

1. Отрисовываются все стены (от ближних к дальним, как описано выше).

2. Незакрашенные участки заполняются полами или потолками.

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

Стены

Любая стена охватывает непрерывный диапазон столбцов экрана, причем каждый столбец содержит вертикальный отрезок пикселей. Мы можем рисовать стены последовательно, спереди назад, разворачивая координаты через функции generate_series():

columns AS ( -- генерируем строку для каждого экранного столбца в пределах ширины стены
  SELECT w.*, x AS col_x, ...
  FROM wall_parts_tex w
  CROSS JOIN LATERAL generate_series(
    GREATEST(0, FLOOR(w.screen_x1)::int),
    LEAST(screen_w - 1, CEIL(w.screen_x2)::int)) AS x
),
fragments AS ( -- формируем строку под каждый пиксель стены в текущем столбце
  SELECT c.col_x AS x, y, c.depth_x AS depth, c.u_i, c.v_i
  FROM clamped_spans c
  CROSS JOIN LATERAL generate_series(c.y_start, c.y_end) AS y
)

В оригинальном исходном коде Doom за это отвечают два цикла: R_RenderSegLoop для прохода по столбцам и R_DrawColumn для отрисовки вертикальных линий.

В среднем этап отрисовки стен отнимает около 1,7 мс.

Visplane

Разобравшись со стенами, перейдем к самому увлекательному — полам и потолкам, именуемым в терминологии Doom словом visplane.

Алгоритм оригинального Doom перекладывается на SQL с трудом из-за своей императивной природы. В движке задействованы два массива, ceilingclip и floorclip, хранящие по одному значению на каждый столбец экрана. Они фиксируют свободные вертикальные диапазоны, ожидающие заливки полами или потолками. При отрисовке каждой новой стены границы массивов сдвигаются до полной зачистки экрана. Причем критически важен порядок обновления данных. Гениальное решение! По сути, это простейший алгоритм заливки, создающий иллюзию полноценного трехмерного пространства с минимальными накладными расходами (на языке C).

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

Базовыми элементами итерации выступают панели — фрагменты стен, проецируемые на конкретные столбцы экрана. Одни панели несут графику (сплошная стена solid, верхняя часть над проемом upper, нижняя часть под окном lower), другие служат для корректировки геометрии остальных элементов (например, проходя под балконом, игрок должен видеть перекрытие сверху, которое где-то должно заканчиваться).

Для каждого столбца экрана (col_x) мы формируем упорядоченный список панелей от ближних к дальним. Состояние обрезок формируется на основе предыдущих строк. Ничего не напоминает? Время задействовать оконные функции!

Текстовое описание дается с трудом, поэтому лучше оцените процесс визуально:

Ниже приведена сокращенная версия SQL-запроса:

panel_clips AS (
  -- 1. вычисляем границы после наложения ближних панелей
  SELECT p.*,
    COALESCE(MAX(CASE WHEN part IN ('solid','upper','upper_flush')
                      THEN y_bot::int + 1 END) OVER w, 0)            AS cc_before,
    COALESCE(MIN(CASE WHEN part IN ('solid','lower','lower_down')
                      THEN y_top::int - 1 END) OVER w, screen_h - 1) AS fc_before
  FROM panel_seq p
  WINDOW w AS (PARTITION BY col_x ORDER BY depth_x, bsp_seq, part, seg_id
               ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)
),
plane_spans_raw AS (
  -- 2. все незанятое пространство сверху — это потолок над стеной...
  SELECT col_x, fsec AS sector_id, f_ceil AS plane_z, 'ceil' AS plane,
         cc_before         AS y0,   -- от точки окончания ближайшей стены
         f_ceil_y::int - 1 AS y1    -- до уровня потолка текущей панели
  FROM panel_clips
  WHERE part IN ('solid','upper','upper_open','upper_flush')
    AND f_ceil_y::int - 1 >= cc_before          -- если свободного места нет, пропускаем
  UNION ALL
  -- ...а снизу — соответствующий пол
  SELECT col_x, fsec, f_floor, 'floor',
         f_floor_y::int AS y0,      -- от уровня пола панели
         fc_before      AS y1       -- до точки начала ближайшей стены
  FROM panel_clips
  WHERE ...
)

Сначала мы определяем для каждой панели свободные вертикальные интервалы экрана. Занятые области учитываются на основе всех более близких к камере панелей (за это отвечает конструкция ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING в пункте 1). Затем мы отрисовываем пиксели от границы предыдущей панели до начала следующей (пункт 2). Процедура выполняется симметрично для полов и потолков.

Довольно варварский метод адаптации процедурного алгоритма под работу с множествами. К счастью, оконные функции выручают...

Рендеринг полов, потолков и неба в среднем занимает около 3 мс.

Небольшое признание

К сожалению, я вас немного обманул: расчет стен, поверхностей visplane и спрайтов пока ничего не нарисовал. На выходе мы получили лишь множество кандидатов вида (x, y, depth, colour), причем в одной экранной точке могло скопиться несколько пикселей с разной глубиной. Поскольку мы отказались от оригинальной арифметики фиксированной точки Doom, стены, полы и небо могут пересекаться. Добавим сюда необходимость вывода спрайтов, способных частично перекрываться стенами. В оригинальном Doom применялась масса трюков, исключавших подобные коллизии без тяжелого Z-буфера. Я безуспешно пытался воспроизвести эти ухищрения на SQL и в итоге сдался, прибегнув к «грубой силе»: мы генерируем все пиксели подряд, а затем выбираем победителей.

((LEAST(depth, 131071.0) * 4096)::bigint << 34) -- глубина, приведенная к фиксированной точке 17.12
| ((2 - surface_priority) << 32)                -- приоритет: стена > спрайт > visplane
| (LEAST(source_priority, 3) << 30)
| ((stable_id + 32768) << 14)                   -- стабильность при разрешении конфликтов
| (light_index << 8) | palette_index            -- полезные данные палитры
AS winner_key
...
SELECT pix, MIN(winner_key) FROM ranked_fragments GROUP BY pix

Здесь используется тот же трюк с упаковкой данных в bigint и поиском минимального значения, что и для BSP-деревьев: старшие биты отданы под глубину, поэтому для выбора ближайшего объекта достаточно взять min(). Полезная нагрузка (цвет пикселя) зашита прямо в ключ, изнуряющие операции JOIN больше не требуются! Решение выглядит громоздким, но поскольку операция выполняется для каждого пикселя кадра (а разрешением 320x200 это 64 000 точек), код должен быть предельно оптимизирован.

Даже с учетом ухищрений этот этап остается самым прожорливым: на него уходит в среднем 8,2 мс — больше трети кадрового бюджета! Именно поэтому Джон Кармак в свое время отказался от подобных лобовых атак. Но нам повезло: мощности современных процессоров позволяют проворачивать такое даже внутри СУБД, стабильно удерживая 35 FPS.

Производительность рендеринга

Ниже приведена диаграмма затрат графического конвейера в сравнении с целевыми показателями оригинального Doom.

На моем ноутбуке (Ryzen 7 PRO 7840U) частота кадров держится около 60 FPS, проседая до базовых 35 FPS лишь в наиболее динамичных сценках.

Главными потребителями ресурсов выступают:

• отрисовка visplane (где мы вынуждены имитировать процедурный итеративный алгоритм);

• сортировка по глубине (от которой классический движок успешно избавлен);

• попиксельные операции (обращения к палитрам цветов и сборка кадрового буфера).

В чем база данных оказалась действительно хороша

Рендеринг шутера внутри СУБД — затея, мягко говоря, сомнительная. Но некоторые аспекты подошли для этого идеально!

Все есть данные

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

Дробовик главного героя описывается всего одной строкой:

doom=# SELECT name, ammo_type, ammo_per_shot, pellet_count,
doom-#        dmg_dice_count, dmg_dice_mult, max_range
doom-#   FROM weapon_defs WHERE name="shotgun";
  name   | ammo_type | ammo_per_shot | pellet_count | dmg_dice_count | dmg_dice_mult | max_range
---------+-----------+---------------+--------------+----------------+---------------+-----------
 shotgun | shells    |             1 |            7 |              3 |             5 |      2048
(1 строка)

Семь дробинок в выстреле, каждая наносит урон броском 3d5.

Даже анимации хранятся в виде данных! Вот полный конечный автомат перезарядки дробовика:

doom=# SELECT state, seq_index AS seq, frame, tics,
doom-#        is_attack_frame AS shoots, refire_check AS refire
doom-#   FROM weapon_frames WHERE weapon_id = 3 ORDER BY state, seq_index;
 state | seq | frame | tics | shoots | refire
-------+-----+-------+------+--------+--------
 ready |   0 | A     |    1 | f      | f
 fire  |   0 | A     |    3 | f      | f
 fire  |   1 | A     |    7 | t      | f
 fire  |   2 | B     |    5 | f      | f
 fire  |   3 | C     |    5 | f      | f
 fire  |   4 | D     |    4 | f      | f
 fire  |   5 | C     |    5 | f      | f
 fire  |   6 | B     |    5 | f      | f
 fire  |   7 | A     |    3 | f      | t
 fire  |   8 | A     |    7 | f      | f
 flash |   0 | A     |    4 | f      | f
 flash |   1 | B     |    3 | f      | f
(12 строк)

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

Разумеется, все это можно было упаковать в JSON-файлы, но в таком случае:

1. не проводилась бы строгая валидация типов при изменениях;

2. требовался бы перезапуск для применения правок.

Многопользовательский режим почти «бесплатно»

Пройдя через все муки портирования Doom на SQL, мы наконец получаем главную награду от использования базы данных — готовый мультиплеер без дополнительных затрат! Мы автоматически получили функции, на самостоятельную реализацию которых разработчики классических игр тратят уйму времени:

• Надежную аутентификацию.

• Контроль конкурентного доступа.

• Разграничение прав.

• Согласованные снимки (snapshot) состояния мира.

• Готовый бинарный сетевой протокол.

Сторонний питоновский демон referee координирует общий 35-герцевый таймер и переключает карты. Удаленные клиенты передают лишь управляющие сигналы.

Больше всего меня восхищает атомарность: расчет каждого такта обрамляется в простые инструкции begin transaction и commit. Каждый участник сессии (deathmatch в Doom поддерживает до четырех игроков) гарантированно получает консистентную картину: либо мир до начала транзакции такта, либо сразу после ее завершения. Никаких промежуточных обновлений, физических багов или рассинхронов в позициях летящих ракет.

Второй приятный бонус — контроль доступа. Хотя sqldoom оперирует 110 таблицами и сотней функций, роли четырех игроков могут взаимодействовать с системой исключительно через строго ограниченное API. Все прочие доступы просто заблокированы на уровне ролей!

Яркий пример — функция приема ввода input:

CREATE OR REPLACE FUNCTION api_input(
  p_fwd real, p_strafe real, p_run boolean, p_turn real,
  p_fire boolean, p_weapon integer, p_use boolean) RETURNS integer
LANGUAGE cedarscript SECURITY DEFINER AS $doom$
INSERT INTO mp_inputs
SELECT mp.map_id, mp.player_thing_id,
       LEAST(1.0, GREATEST(-1.0, COALESCE(p_fwd, 0)))::real,
       LEAST(1.0, GREATEST(-1.0, COALESCE(p_strafe, 0)))::real,
       [...]
FROM mp_players mp WHERE mp.role_name = session_user::text;
return 1;
$doom$;

Несмотря на то, что сама функция обладает правами на запись в таблицы (security definer), игроку разрешено лишь вызывать ее. Набор доступных команд ограничен: направление движения (нажатия w/s), стрейф (a/d), бег, мышиный поворот, стрельба, выбор оружия и активация предметов/дверей (пробел). Мы можем даже фильтровать передаваемые клиентом значения, защищаясь от читов. Производительность мультиплеера приятно удивляет: три процессорных ядра на клиента обеспечивают стабильные 35 FPS, при этом симуляция по-прежнему расходует лишь малую часть доступного времени. Выделение отдельного ядра под тактовый процессор позволяет 16-ядерной машине легко справляться с режимом deathmatch -altdeath (с возрождением предметов и сохранением оружия после смерти).

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

Бонус: компиляция SQL-запросов

Может показаться, что написанная на C++ база данных, интерпретирующая SQL, безнадежно медленна и не способна тягаться с чистым C? Вероятно, так оно и есть, но мне было интересно измерить реальный масштаб отставания.

CedarDB — это компилирующая СУБД: сложные запросы после многоступенчатой оптимизации транслируются в промежуточное представление LLVM IR, а затем компилируются в машинный код. Мне стало любопытно: насколько сгенерированный машинный код отличается от бинарника linux_doom, скомпилированного с языка C?

В верхней части показана логика расчета перемещений с учетом инерции. Слева — оригинал на C, справа — реализация на SQLDoom. Прямого поэлементного сравнения провести не выйдет из-за разницы в архитектуре, но код на C транслируется в 48 инструкций, в то время как SQLDoom генерирует 117. При этом 42 инструкции из этого числа уходят на повторную запись результатов в таблицы (выделены зеленым), чего оригинал на C делать не должен. Ситуация действительно выглядит хуже, но не катастрофически, учитывая глубину абстракций между SQL и кремнием процессора. На мой взгляд, для SQL-запроса, пропущенного через оптимизатор и компилятор LLVM, разрыв оказался на удивление небольшим.

Джон Кармак — безусловный гений

Сравните SQLDoom с его предшественником DOOMQL, созданным по мотивам Wolfenstein 3D:

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

Тем не менее концептуально более подходящий инструмент не всегда дает лучший результат. Архитектура SQLDoom на основе BSP-деревьев работает значительно быстрее, а качество картинки на порядок выше. И всё это благодаря тому, что Джон Кармак сумел выжать максимум из процессора 486 за счет гениальных математических трюков.

Честно говоря, сама CedarDB за это время тоже эволюционировала. Когда я собирал DOOMQL, движок работал заметно медленнее, а подсистемы ролевого доступа еще не существовало.

Инструкция по запуску

Исходный код проекта выложен на Github: github.com/cedardb/sqldoom.

Для запуска вам понадобятся три компонента:

1. CedarDB Community Edition;

2. Python с установленными пакетами psycopg2 и pygame;

3. Оригинальный файл IWAD от Doom (его я предоставить не могу, но бесплатная shareware-версия doom1.wad легко устанавливается через apt install doom-wad-shareware для прохождения первого эпизода; также подойдут файлы от полной коммерческой версии игры).

Следуя инструкциям из файла README, вы сможете поднять собственный экземпляр SQLDoom за считанные секунды!

А если возиться с установкой не хочется, добро пожаловать на публичные серверы:

SQLDoom в Европе

SQLDoom в США

 

Источник