[Перевод] Мы портировали Doom на SQL
TL;DR: Мы портировали игровую логику и рендерер первого Doom на SQL и запустили его внутри базы данных. На моём ноутбуке игровой цикл исполняется на исходных 35 FPS, а рендерер генерирует полный буфер кадров 320x200 с частотой от 60 Гц и выше. Python только обрабатывает тайминги, считывает клавиатуру и отображает получаемую им битовую карту. Многопользовательский режим тоже работает.
SQLDoom на AMD Ryzen 7 7840U
Можете сыграть прямо сейчас: Deathmatch, четыре слота, обслуживание в порядке очереди.
Это shareware-версия первого эпизода. Если все места заняты, вы попадаете в очередь. Если очередь заполнена, то в процессе ожидания вы всё равно можете запрашивать состояние игры через SQL.
SQLDoom
В прошлом году я опубликовал DOOMQL [Github]. Он рендерил с частотой 30 FPS ASCII-графику, приблизительно напоминающую Doom, и людям очень понравился этот проект. Но многие говорили, что он гораздо ближе к Wolfenstein 3D, чем к Doom, потому что в нём используется рейкастинг. В Doom же используются BSP-деревья, благодаря чему корректное упорядочивание по глубине становится настолько малозатратным, что обеспечивает возможность использования текстур, стен под произвольными углами и разной высоты полов.
Меня не оставляла в покое эта мысль, поэтому я наконец-то реализовал настоящий Doom, работающий целиком на SQL.
Правила
Давайте для начала определимся с базовыми правилами:
Игра должна выглядеть, как реальный Doom. Оглядываясь назад, я понимаю, что визуально DOOMQL был довольно уродливым.
Что ещё важнее — он должен ощущаться, как реальный Doom, передавая всю увлекательность оригинала.
Рендеринг должен быть основан исключительно на SQL. Единственный приемлемый вывод SQL — это таблица или битовая карта, в которой закодированы конкретные RGB-значения каждого пикселя.
Игровой цикл тоже должен быть целиком основан на SQL, однако допускается использовать внутри базы данных пользовательские функции.
Допускается писать клиент на другом языке программирования, если он будет заниматься только парсингом ввода, управлением тактами игры и рендерингом битовой карты.
Архитектура
Python намеренно сделан скучным (правило 5). Единственный скрипт использует pygame для обработки ввода, отрисовки выходной битовой карты и выполнение тактов игры 35 раз в секунду. Игровая логика, игровое состояние и рендерер находятся внутри базы данных.
Python
ввод / тайминги / отображение
| ^
| |
исполнение такта игры запрос кадра
| |
v |
+----------------+ +----------------+
| | | |
| Игровая логика | | SQL-рендерер |
| на SQL | | |
+-------+--------+ +--------+-------+
| ^
| |
v |
+-----------------------------+
| |
| таблицы игрового состояния |
| |
+-----------------------------+
Два пути намеренно сделаны раздельными: игровая логика исполняется в цикле с фиксированной частотой 35 Гц, а рендерер — это чистая функция таблиц игрового состояния; клиент может запрашивать новый кадр с любой частотой (например, максимально часто).
Загрузка данных игры
Удобно, что файловый формат .wad игры Doom изначально имеет высокую степень реляционности.
Две вершины VERTEX соединяются LINEDEF, имеющим два SIDEDEF. SIDEDEF ограничивает SECTOR, имеющий внутри различные THING; в общем, смысл понятен. Перенос всего WAD в базу данных оказался на удивление простым процессом: для этого понадобилось всего около тысячи строк на Python. Для импорта всего Doom 1 на моём ноутбуке достаточно примерно 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, а не только рендерить смутно похожие на него кадры. Разумеется, серьёзную роль в этом играет графика, но в Doom ещё и потрясающий геймплей. Посмотрите на следующую сцену, где реализовано правило 2:
Как видите, здесь происходит многое. В этом коротком клипе мы видим:
Опрос и обработку ввода пользователя (движение, повороты, стрельба).
Движение и атаки врагов.
Подбор предметов.
Из ракетницы вылетает и движется вперёд ракета.
У взрыва ракеты есть радиус поражения.
Рендерятся спрайты врагов.
Есть анимации, покачивание при ходьбе и HUD.
На обработку всего этого у нас не так много времени: Doom работал с фиксированной частотой 35 Гц, поэтому такт игры имеет бюджет времени 1000 мс × 35 Гц = 28,6 мс. Кроме того, кадр отрисовывался ровно раз за такт, поэтому частота кадров тоже была ограничена 35 FPS.
В SQLDoom игровая логика тоже исполняется с частотой 35 Гц (чтобы работали все константы из оригинала игры), однако отрисовка вынесена отдельно. Клиент может запрашивать кадр, когда ему захочется, а между тактами мы интерполируем позицию камеры. Так что нам нужно учитывать два бюджета:
Выполнение такта игры каждые 28,6 мс (в противном случае игра будет ощущаться не так)
Рендеринг не менее 35 кадров в секунду (приемлемо и меньше, но движение не будет казаться плавным)
Последовательность такта
Такты игры процедурны по своей сути. При выполнении каждого такта у нас есть последовательность необходимых действий. В 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 ( [...] ), -- видимый, in_view_cone, dist: recursive, walks walls
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).
Производительность управления тактами
Вот waterfall-график рендеринга игрового такта:
На самом деле, это самый медленный такт, который мне удалось найти. Это уровень E4M1 с 46 активными монстрами, которые пытаются напасть на меня через открывающуюся дверь. Для его рендеринга нужно 10,45 мс, то есть ~37% от бюджета такта.
Более типичный такт с 6 активными монстрами в среднем занимает 2,15 мс, или примерно 8% от бюджета. У нас есть большой запас!
Честно говоря, меня удивило, с какой лёгкостью можно выразить довольно сложную игровую логику на SQL. Вся игровая логика уместилась всего в ~5,9 тысячи строк SQL. Хоть и кажется, что это много, на самом деле, это намного меньше исходного кода C, выполняющего ту же логику в примерно 9 тысячах строк!
Кроме того, язык заставляет думать иначе: вместо итераций, например, перебора монстров одного за другим, мы пишем простой UPDATE ... WHERE condition, чтобы сама база данных разобралась, как лучше его применить, параллельно и автоматически!
Должен также сказать, что здесь, наконец, мне стал понятен паттерн Entity Component System (ECS). Каждая entity (игрок, монстр, объект, …) имеет несколько component (позиция, спрайт, статистика, …), а одна system (ИИ монстров, перемещение игрока, расчёт урона) определяет, как entity с конкретным набором свойств взаимодействуют друг с другом. ECS во многом основан на локальности данных и способе итерации по entity, имеющих конкретный набор компонентов. А в SQL мы уже привыкли к интенсивной обработке данных! Каждый компонент становится таблицей, а каждая система превращается в update или insert, выполняющий join интересующих его таблиц с entity в качестве ключа join!
Рендеринг
Каждый кадр — это просто огромное представление (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, -- проецирование сегментов в экранное пространство space
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, то есть она довольно сложна для SQL-запроса!
Но несмотря на то, что это выглядит, как полное безумие, такой конвейер довольно близок к тому, что делал Doom. У SQL даже есть одно преимущество: в исходниках linux_doom движок рендеринга занимает примерно 3,3 тысячи строк (не считая комментариев). То есть примерно в 2,5 раза больше, чем в SQLDoom. Было ли это вообще хорошей идеей — другой вопрос, который мы рассмотрим ниже.
Для начала изучим самые интересные части конвейера рендеринга:
Слева показано усечение на основании bsp, справа — визуализация рендеринга стен и visplane.
Обход BSP
Так как в 1993 году ни у кого не было GPU с аппаратным ускорением Z-буферизации, для правильной реализации перекрытий Doom должен был выполнять отрисовку в нужном порядке. Он делает это довольно изобретательным образом: выполняет отрисовку спереди назад и отслеживает, какие пиксели уже были отрисованы (то есть, если я уже отрисовал пиксель стены, мне не нужно рисовать монстра за ней). Но это проще сказать, чем сделать: нам нужен эффективный способ упорядочивания всего на уровне по глубине.
Doom выполняет это упорядочивание при помощи заранее вычисленных BSP-деревьев, сохранённых в файле doom.wad. Каждый узел дерева — это отрезок, разделяющий карту на две части. Таким образом, секторы карты разбиваются на множество подсекторов, находящихся по одну или другую сторону от этих отрезков; они вставляются в дерево, благодаря чему мы получаем следующие свойства:
каждый подсектор — это лист и
каждый подсектор выпуклый (то есть, мы не можем увидеть стену, находясь внутри неё)
в каждом узле дерева всё поддерево, находящееся на стороне камеры, гарантированно будет перед поддеревом на другой стороне.
Таким образом, рекурсивно обходя 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 -- был ли усечён какой-нибудь из родительских bbox?
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 бит должно быть достаточно для обработки любой карты игры: самое глубокое BSP-дерево (в E4M8) имеет всего 32 уровня. Если карта не в 256 раз больше самой крупной карты «ванильного» Doom, то всё будет в порядке!
Если приглядеться, то можно понять, что наш обход bsp также выполняет усечение: каждый узел в .wad также определяет ограничивающий прямоугольник всех его дочерних элементов. Если мы можем доказать, что пирамида видимости полностью находится внутри этого ограничивающего прямоугольника, то нам не придётся определять поддерево для рендеринга — это и обозначает visible_children.keep. Поэтому bool_and(vc.keep) отсекает все подсекторы, чей предок не отвечает требованиям.
Для всего последующего в конвейере просто выполняется join относительно bsp_seq, поэтому учитываются только видимые подсекторы и только в правильном порядке.
Стены и Visplane
Doom немного жульничает: он выглядит трёхмерным, но на самом деле это 2,5D-игра. По сути, это плоская поверхность с идеально вертикальными стенами и потолками, всегда параллельными поверхности земли. Это сильно упрощает рендеринг по сравнению с реальным 3D-движком:
Отрисовываем все стены (спереди назад, как говорилось выше).
Всё, что пока не было отрисовано — это или пол, или потолок. Отрисовываем их.
Спрайты (монстры, бочки, предметы) — это плоские изображения, всегда смотрящие в камеру (подобно картонным фигурам), поэтому никаких сложных преобразований не требуется (если только они не накладываются на стену, но об этом мы поговорим ниже).
Стены
Стена занимает множество соседних столбцов экрана, и в каждом столбце находится непрерывный интервал пикселей. Поэтому мы просто можем одну за другой и спереди назад отрисовывать стены, разворачивая строки и столбцы при помощи 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, потому что высокоимперативен: Doom имеет два массива, ceilingclip и floorclip, хранящие по одной записи на столбец экрана. В них записываются полосы, всё ещё свободные в каждом столбце (то есть которые должны стать полом или потолком и пока ещё не отрисованные). При отрисовке новой стены они изменяются, пока не будет заполнен каждый пиксель. Doom не просто изменяет их: очень важно делать это в правильном порядке. Гениально! В конечном итоге, это просто алгоритм заливки, но благодаря ему почти без затрат (по крайней мере, на 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Это тот же трюк, что и с BSP-деревом, когда мы упаковывали всё в bigint, а затем выбирали min: самые старшие биты — это глубина, поэтому для нахождения победителя достаточно выбрать min. А поскольку полезная нагрузка (то есть цвет пикселя) — это часть ключа, нам даже не нужно заново выполнять join! Решение кажется грязноватым, но поскольку эта работа выполняется попиксельно (а один кадр Doom содержит 320*200=64000 пикселей), нам нужно быть аккуратными, чтобы не выполнять слишком много работы.
Даже с такой оптимизацией это остаётся самой затратной частью кадра: в среднем 8,2 мс, больше трети всего бюджета кадра! И именно поэтому Джон Карман не стал применять такое решение. Но нам повезло: теперь у нас есть машины, способные выполнять это даже на SQL и всё равно успевать обеспечивать 35 FPS.
Производительность рендеринга
Вот waterfall-график конвейера в сравнении с целевым 35 FPS Doom.
На моём ноутбуке (Ryzen 7 PRO 7840U) обычно получается около 60 FPS, но в очень напряжённых сценах частота кадров падает до 35 FPS.
Самые затратные части конвейера:
рендеринг visplane (где мы вынуждены имитировать итеративный алгоритм),
сортировка по глубине (которой оригинальный Doom успешно полностью избегает),
и всё, что происходит для каждого пикселя (например, поиск по таблице цветов и упаковка буфера кадров)
Где использование базы данных оказывается хорошей идеей
Рендеринг Doom в базе данных — очевидно плохая идея. Но есть некоторые части, которые хорошо для этого подходят!
Всё — это данные
Изначально я не представлял, какое удовольствие испытаю от преобразования свойств элементов в реляционный датасет. Во-первых, это сильно упрощает проверку того, что же содержится в игре, во-вторых, свойства становится очень легко менять.
Дробовик игрока — это всего лишь строка:
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, но при этом
ограничения не проверялись бы во время внесения изменений и
нам приходилось бы перезагружаться, чтобы изменения вступили в силу.
Multiplayer почти не потребовал дополнительных затрат
Мы претерпели все эти мучения по портированию Doom на SQL, но пока так и не воспользовались самым большим преимуществом базы данных: можно без затрат получить multiplayer-сервер! Мы бесплатно получили кучу возможностей, которые разработчикам традиционных игр приходится создавать самостоятельно:
Аутентификация.
Контроль конкурентности.
Контроль доступа.
Согласованные снэпшоты состояния игры.
Двоичный сетевой протокол.
Отдельный скрипт referee на Python управляет общим таймером на 35 Гц и выполняет ротацию карт. Клиенты игроков онлайн передают ввод.
Больше всего мне нравится атомарность: при выполнении такта игры можно просто сказать begin transaction и выполнить commit в конце. Каждый игрок (deathmatch Doom поддерживает до четырёх игроков) всё равно получит согласованное представление: или то, как выглядел мир до начала транзакции такта, или после его полного завершения. Никаких частично применённых обновлений, физических багов или рассогласований относительно того, куда же на самом деле попала ракета.
Во-вторых, удивительно изящным стал контроль доступа. Хотя сам sqldoom содержит примерно 110 таблиц и чуть более 100 функций, роли четырёх игроков могут взаимодействовать с ним только через небольшое количество чётко определённых функций 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?), бежит ли он?, поворачивает при помощи мыши?, нажата ли кнопка выстрела?, какое оружие выбрано?, пытается ли он нажать на кнопку/открыть дверь (spacebar)? Мы даже можем не доверять значениям ввода игрока: функция ограничивает ввод допустимыми значениями.
Скорость многопользовательского режима тоже на удивление хороша: 3 ядра на одного клиента обеспечивают стабильные 35 FPS, а расчёт игрового такта всё равно остаётся сильно быстрее бюджета. Если добавить дополнительное ядро под управление тактом, то 16-ядерная машина справится с режимом deathmatch -altdeath (предметы распавнятся, оружие остаётся).
Публичный инстанс выполняет ротацию карт Episode 1; смена карты происходит каждые 10 минут. Если все четыре слота заняты, то всё равно можно выполнять запросы к текущему матчу через консоль SQL.
Бонус: компиляция SQL
Наверно, написанная на C++ база данных, интерпретирующая SQL, безумно неэффективна и не сможет приблизиться к C? Скорее всего, так и есть, но мне хотелось проверить, насколько велик разрыв.
CedarDB — это компилируемая система баз данных: каждый сложный запрос (путём многоэтапного процесса) опускается до LLVM IR, а затем компилируется в машинный код. Я задался вопросом: насколько сгенерированный машинный код отличается от скомпилированного кода linux_doom на C?
В верхней части показана логика движения объектов и влияние на него момента. Слева находится исходный код оригинального Doom, справа — реализация SQLDoom. Сравнение не полностью идентичное, потому что логика распределена немного по-разному, но код на C компилируется в 48 команд, а SQLDoom — в 117. Из этих дополнительных команд 42 снова сохраняют результат в таблицу (зелёные строки), чего коду на C, очевидно, делать не нужно. То есть ситуация действительно хуже, но на самом деле она не так уж ужасна, учитывая те слои абстракции, которые находятся между SQL и CPU. Мне кажется, для SQL, пропущенного через оптимизатор запросов и LLVM, разница оказалась на удивление маленькой.
Джон Кармак — гений.
Сравните SQLDoom с его предшественником DOOMQL в стиле Wolfenstein 3D:
В обоих используется один и тот же движок, те же ограничения: на входе SQL, на выходе битовая карта. И не поймите меня неверно: примитивный рейкастинг DOOMQL великолепен, его гораздо проще сформулировать на SQL, а между этапами не так много зависимостей, поэтому он гораздо лучше подходит для обработки SQL на основе множеств.
Однако оказалось, что самое подходящее не всегда обеспечивает лучшие результаты. Решение SQLDoom на основе BSP-деревьев намного быстрее, а качество графики при этом гораздо выше. Всё это благодаря тому, что Джон Кармак хорошо продумал, как выжать из 486 максимум при помощи разных хитростей и трюков.
И, честно говоря, CedarDB тоже сделала шаг вперёд. Когда я создавал DOOMQL, движок был гораздо медленнее и у нас ещё не существовало системы доступа на основе ролей.
Как запустить проект самостоятельно
Он есть на Github: github.com/cedardb/sqldoom.
Вам понадобится три вещи:
Python с
psycopg2иpygame,IWAD Doom, который я вам дать не могу. Shareware doom1.wad распространяется свободно (
apt install doom-wad-shareware), и его достаточно для игры в episode 1; подойдут и WAD retail-версии, если они у вас есть.
Просто выполните инструкции из README, и за считаные секунды запустите собственный SQLDoom!
А если вам покажется, что возни слишком много, то можете просто присоединиться к матчу на публичном инстансе:
KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.