Недавно я набрёл на шедевр Патрика — клон DOOM, основанный на DuckDB-WASM и работающий в браузере. Прочитав о нём, я решил довести эту великолепную идею до логического завершения: написать многопользовательский DOOM-подобный шутер целиком на SQL. При этом всю тяжёлую работу хотел сделать через базу данных CedarDB. Отлучившись с работы в месячный отпуск по уходу за ребёнком (бессонных ночей хватало), я попытался сделать именно это.
Вот вам тизер DOOMQL:
Ладно, демка вышла на славу, а теперь давайте подробно обсудим этот проект. Вас ждёт экскурс в архитектуру игры, далее я расскажу о конвейере рендеринга в SQL, об игровом цикле, а также позабавлю вас интересной метаигрой: как обмануть SQL, выдавая ему только такие команды, которые можно выполнить через базу данных.
Зачем вообще это делать?
Поиграть в DOOM на основе DuckDB прямо в браузере, бесспорно, интересно, но кое-что в этом проекте не давало мне покоя. Во-первых, казалось, что если написать все звенья рендерингового конвейера на JavaScript, это будет какое-то жульничество. Такой подход хорошо применим к проекту DuckDB-Doom, где всё помещается на единственной HTML-странице, но я хотел всё написать именно на SQL. Кроме того, игра DuckDB-Doom немного лагает, поскольку здесь нам доступна частота всего 8 кадров в секунду, а область просмотра совсем маленькая. Мне захотелось проверить, удастся ли ускорить этот процесс, если переключаться на CedarDB. Кроме того, я собирался сделать настоящие спрайты с элементом прозрачности, эти спрайты должны правдоподобно двигаться в 3D-пространстве. А самое важное — создать многопользовательскую игру должно быть не только возможно, но и легко, верно? Меня как настоящего нерда очаровало эмпирическое сходство между сервером базы данных и традиционным игровым сервером. Основное назначение базы данных — синхронизировать состояние, разделяемое между множеством клиентов. Благодаря изоляции транзакций, каждый из игроков имеет непротиворечивое п��едставление об игровом мире, независимо от того, что делают другие клиенты. Почему бы на это не положиться? Хотелось бы мне вам соврать, что мне всё это удалось — и всё благодаря тому, как хороша из себя база данных CedarDB. Но, честно говоря, мой внутренний технарь просто хотел выкрутить все регуляторы до отказа и проверить, что в итоге откажет.
Обзор архитектуры
В общем виде:
Состояние хранится в таблицах (карта, игроки, мобы, входные данные, конфиги, спрайты, …).
Рендеринг осуществляется через стек представлений SQL, реализующих рейкастинг и проецирование спрайтов.
Игровой цикл заключён в миниатюрном шелл-скрипте, выполняющем SQL-файл ~ 30 раз в секунду.
Клиент написан примерно в 150 строках Python: он обращается за вводом и запрашивает из базы данных 3D-представление для вашей игры.
Можно играть, видеть других игроков и даже жульничать (отправляя необработанный SQL).
Состояние игры, или давайте всё сохраним в базе данных
Располагая базой данных, естественно, попробуем сохранить в ней всю конфигурацию игры, состояние и статические данные:
Конфигурация:
CREATE TABLE config(
player_move_speed NUMERIC DEFAULT 0.3,
player_turn_speed NUMERIC DEFAULT 0.2,
ammo_max INT DEFAULT 10,
ammo_refill_interval_seconds INT DEFAULT 2
);Карта:
CREATE TABLE map(x INT, y INT, tile CHAR);Игроки и входные данные:
CREATE TABLE players (
id INT REFERENCES mobs(id),
score INT DEFAULT 0,
hp INT DEFAULT 100,
ammo INT DEFAULT 10,
last_ammo_refill int default EXTRACT(EPOCH FROM (now()))::INT
);
CREATE TABLE inputs(
player_id INT PRIMARY KEY REFERENCES players(id),
action CHAR(1), -- 'w', 'a', 's', 'd', 'x' чтобы стрелять
timestamp TIMESTAMP DEFAULT NOW()
);Поскольку здесь всё – данные, не составляет труда написать мод матча и запустить его:
-- Меняем настройку
update config set ammo_max = 20;
-- Добавляем игрока
insert into players values (...);
-- Движемся вперёд
update input set action = 'w' where player_id = <your_id>;
-- Жульничаем (пожалуйста, здесь будьте умнее)
update players set hp = 100000 where player_id = <your_id>;
-- Баним читеров (которые сглупили)
delete from players where hp > 100;Рендеринг: когда VIEW превращается в 3D-представление
Если присмотреться, оказывается, что в 3D (точнее: 2,5D)-представлении DOOM мы просто просматриваем состояние, наложенное на 2D (т.е., карту уровня и всех присутствующих на ней игроков или врагов). Что ж, у нас в SQL есть сущности VIEWS. Они представляют собой просто снимки состояний, записанных в таблицах, и двумерны, как и сами таблицы. Что нам мешает буквально выстроить 3D-«представление» нашей 2D-карты, воспользовавшись для этого простым алгоритмом рейкастинга?
Конвейер таков:
Отправляем набор лучей из глазницы каждого игрока и проверяем, какие участки карты (тайлы) ему видны.
Проверяем, какие стены видны игроку, отображаем их в правильную высоту и так, чтобы (в зависимости от расстояния) они казались более-менее твёрдыми.
Проецируем мобов в пространство, попадающее в камеру игрока.
В зависимости от глубины выбираем уровни детализации спрайтов.
Расширяем спрайты до пикселей, отмасштабированных в соответствии с экранным пространством.
Заслоняем участки обзора в зависимости от того, где находятся стены и другие спрайты.
Собираем ряды кадрового буфера при помощи
string_agg.Выстраиваем миникарту, повторно используя расчёт видимых тайлов, выполненный выше.
Сочетаем 3D-представление с миникартой и видом из шлема (HP/пули/игроки), собираем всё это в общую игровую сцену.
Давайте подробно разберём этапы 2, 7 и 8.
Рейкастинг
Рекурсивная логика пошаговой трассировки лучей (ray marching) реализована по образцу, предложенному Патриком в его посте о DuckDB DOOM. Ниже — упрощённая выдержка, адаптированная для многопользовательского режима:
CREATE OR REPLACE VIEW visible_tiles AS
WITH RECURSIVE raytrace AS (
-- Начинаем с глазницы игрока...
SELECT r.player_id, r.col, 1 AS step_count,
r.player_x + COS(r.angle)*s.step AS fx,
r.player_y + SIN(r.angle)*s.step AS fy,
r.angle, 0 AS dist
FROM rays r, settings s -- лучи выстроены на предыдущем этапе
UNION ALL
-- ... выполняем рекурсивную трассировку вдоль лучей, по 1 «шагу» за раз ...
SELECT rt.player_id, rt.col, rt.step_count + 1,
rt.fx + COS(rt.angle)*s.step,
rt.fy + SIN(rt.angle)*s.step,
rt.angle,
step_count * s.step * COS(rt.angle - m.dir) AS dist
FROM raytrace rt, settings s, players p, mobs m
WHERE rt.step_count < s.max_steps -- ... останавливаемся после того, как достигнем максимального расстояния, предусмотренного для рендеринга
AND rt.player_id = p.id
AND m.id = p.id
AND NOT EXISTS ( -- или если врежемся в стену
SELECT 1 FROM map m
WHERE m.x = CAST(rt.fx AS INT) AND m.y = CAST(rt.fy AS INT)
AND m.tile = '#') -- стена
)
-- Далее для каждого игрока определяем:
-- a) с какими тайлами произошло столкновение
-- b) насколько далеко эти тайлы расположены
-- c) столбец на экране, соответствующий каждому из тайлов
SELECT player_id, tile, CAST(fx AS INT) AS tile_x, CAST(fy AS INT) AS tile_y, col, MIN(dist) AS dist
FROM raytrace rt, map m
WHERE m.x = CAST(rt.fx AS INT) AND m.y = CAST(rt.fy AS INT) -- С одним и тем же тайлом можно столкнуться многократно, поэтому берём самое близкое попадание
GROUP BY player_id, tile_x, tile_y, tile, col; А это был всего лишь первый этап работы конвейера. Если хотите подробнее изучить дальнейшие, то посмотрите код.
Окончательная сборка кадра
Выполнив всю тяжёлую работу, видим, что сухой остаток удивительно прост:
SELECT player_id, y, string_agg(ch, '' ORDER BY x) AS row
FROM framebuffer
GROUP BY player_id, y; Так мы склеиваем символьные пиксели в ряды.
Вид из шлема + миникарта
Проделав такой же трюк, выстраиваем вид из шлема и миникарту. Вот индикатор здоровья:
'HP: [' ||
repeat('█', LEAST(20, ROUND(20 * GREATEST(0, LEAST(p.hp,100))::numeric / 100)::int)) ||
repeat(' ', GREATEST(0, 20 - ROUND(20 * GREATEST(0, LEAST(p.hp,100))::numeric / 100)::int)) ||
'] ' || GREATEST(0, p.hp)Добавляем линейку с боеприпасами функцией repeat('•', p.ammo) — и получаем вид из шлема, написанный на чистом SQL:
1: Lukas (L) score: 1 HP: [█████████ ] 50 AMMO: ••••••••••
2: Foobar (F) score: 0 HP: [████████████████████] 100 AMMO: •••••••• Можно повторно использовать написанное ранее представление visible_tiles, построив на его основе миникарту с конусом обзора:
select * from minimap where player_id = 1 order by y;
player_id | y | row
-----------+----+------------------------------------------------------------------
1 | 0 | ################################################################
1 | 1 | ################################################################
1 | 2 | ##....... ##### #############################
1 | 3 | ##.....F. ##### ##### ###
1 | 4 | ##....... ##### ##### ###
1 | 5 | ## ..... ##### ##### ###
1 | 6 | ## ... ###
1 | 7 | ## .L ###
1 | 8 | ## ##### ##### ###
1 | 9 | ## ##### ##### ###
1 | 10 | ## ############# ########## ###
1 | 11 | ########## ################ ########## ###
1 | 12 | ########## ################ ########## ###
1 | 13 | ########## ################ ###################### ##########
1 | 14 | #### ####### ###################### ##########
1 | 15 | #### ####### ###################### ##########
1 | 16 | #### ##### ##### ###
1 | 17 | #### ##### ##### ###
1 | 18 | #### ##### ##### ###
1 | 19 | #### ##### ##### ###
1 | 20 | #### ##### ##### ###
1 | 21 | #### ##### ###
1 | 22 | #### ###
1 | 23 | #### ##### ###
1 | 24 | #### ##### ##### ###
1 | 25 | #### ##### ##### ###
1 | 26 | #### ##### ##### ###
1 | 27 | #### ##### ##### ###
1 | 28 | #### ##### ##### ###
1 | 29 | ################################################################
1 | 30 | ################################################################
1 | 31 | ################################################################Удивительно элегантный игровой цикл
Игровой цикл в нашем случае — это просто шелл-скрипт, адресующий базе данных запросы на сыром SQL:
# Игровой цикл: примерно 30 тактов в секунду
while true; do
psql -qtAX -U "$DB_USER" -d "$DB_NAME" -h "$DB_HOST" -p "$DB_PORT" -f gameloop.sql
sleep 0.03
doneВнутри gameloop.sql такие действия, как полёт пули, столкновения, фраги и перерождения выполняются каждое за одну транзакцию, благодаря чему состояние остаётся согласованным даже, если какое-то событие вклинится между тактами.
Вот часть, в которой обрабатывается взаимодействие с пулями:
-- Обрабатываем все пули
BEGIN TRANSACTION;
-- Продвигаем пули вперёд
UPDATE mobs
SET x = x + cos(dir) * 0.5, y = y + sin(dir) * 0.5
WHERE kind = 'bullet';
-- Удаляем пули, вылетевшие за границы
DELETE FROM mobs
WHERE (x < 0
OR x >= (select max(x) from map)
OR y < 0
OR y >= (select max(y) from map))
AND kind = 'bullet';
-- Удаляем пули, попавшие в стены
DELETE FROM mobs b
WHERE EXISTS
(SELECT 1
FROM map m
WHERE m.x = CAST(b.x AS INT)
AND m.y = CAST(b.y AS INT)
AND m.tile = '#')
AND kind = 'bullet';
-- Если игрока ранит пуля, он теряет 50 очков здоровья
UPDATE players p SET hp = hp - 50
FROM collisions c
WHERE p.id = c.player_id;
-- Если у пользователя 0 или меньше очков здоровья, то убивший его игрок получает очко
UPDATE players p SET score = score + 1
FROM collisions c
WHERE p.id = c.bullet_owner
AND EXISTS (SELECT 1 FROM players p2 WHERE p2.id = c.player_id AND p2.hp <= 0);
-- Удаляем пули, попавшие в игроков
DELETE FROM mobs m
USING collisions c
WHERE m.id = c.bullet_id;
-- Перерождаем игроков, чей уровень здоровья составил 0 или меньше
UPDATE mobs m
SET x = r.x, y = r.y, dir = 0
FROM players p
CROSS JOIN (
SELECT x, y
FROM map
WHERE tile = 'R'
ORDER BY random()
LIMIT 1
) AS r
WHERE m.id = p.id
AND p.hp <= 0;
-- После перерождения восстанавливаем игроку уровень здоровья до 100 и боезапас до 10
UPDATE players p SET
hp = 100,
ammo = 10
FROM mobs m
WHERE p.id = m.id
AND p.hp <= 0;
COMMIT;На моей машине игровой цикл выполняется примерно за 1 мс, так что тактовую частоту определённо можно было бы улучшить. Может быть, так удалось бы привлечь снобов из «Контры», которые кривятся на всё, что ниже 128 Гц. Для этого с моей стороны потребова��ся бы небольшой рефакторинг, так как я привязал скорость движений к игровому циклу — при проектировании игр за такое больно бьют по рукам!
Думаю, надо быть безумцем, чтобы даже помыслить о движке для рейкастинга на чистом SQL в нормальной игре. Поэтому я готов отстаивать именно такой игровой цикл на основе транзакций, какой получился у меня. Думаю, в реальном игровом движке он получился бы гораздо более лаконичным и менее хрупким.
Реализуем многопользовательский режим за два запроса
Описать задачу игрового клиента не составляет труда:
1. Рендеринг
SELECT full_row FROM screen WHERE player_id = <your_id> ORDER BY y2. Отправка ввода
INSERT INTO inputs(player_id, action)
VALUES (<your_id>, <pressed_key>)
ON CONFLICT(player_id)
DO UPDATE SET action = EXCLUDED.actionИгровой цикл периодически проверяет таблицу ввода и в соответствии с ней перемещает всех игроков — разумеется, в рамках транзакции, поэтому никаких гонок условий у нас не возникает.
Вот и всё (да, ещё потребуется один раз «создать игрока» при первом подключении). Примерно в 150 строках клиентского кода на Python мы в основном обрабатываем весь ввод с клавиатуры, а также уменьшаем мерцание терминала. На клиенте предусмотрен режим наблюдателя. Для этого нужно всего лишь поменять <player_id> при вызове рендера.
Производительность
При размере экрана 128 на 64 пикселей однопользовательское представление у меня на машине отображается примерно за 33 мс, и этого достаточно для щадящих ~30 кадров в секунду, по сравнению с 8 кадрами в секунду у DOOM на DuckDB при всего 32 x 16 пикселях. На самом деле, я весьма горжусь такой производительностью и очень доволен, что здесь задействована CedarDB. Думаю, ни одна другая база данных не смогла бы с ней потягаться. Если найдёте такую – дайте знать!
Возможно, вас беспокоит, что отображение представлений сразу для всех игроков и фильтрация постфактум приводят к расточительной трате ресурсов. В CedarDB есть оптимизатор запросов, проталкивающий предикат where player_id = <...> сквозь границы представлений и тем самым освобождающий вас от лишней работы. Можете легко в этом убедиться, выполнив:
select * from screen order by y; -- отображение обоих пользователей
-- Время: 57,907 мс (меньше, чем 33 мс умноженные на 2, где 33 мс затрачивается в однопользовательском режиме )Метаигра с жульничеством
Поскольку клиенты отправляют сырой код SQL в режиме суперпользователей (здесь я не утруждаю себя реализацией какого-либо контроля доступа на основе ролей или обеспечением безопасности на уровне строк — и это плохой пример, не следуйте ему!), у нас возникает метаигра: попробуем творчески жульничать так, чтобы нас не поймали с поличным.
Почти не стараемся:
update players set score = 0 where id != <your_id>;
update players set hp = 0 where id != <your_id>;Коварство:
update inputs set action = null where player_id != <your_id>;Воруем фраги:
update mobs set owner = <your_id> where kind = 'bullet';Попробовал — не работает:
DELETE FROM mobs m
USING collisions c
WHERE m.id = c.bullet_id AND c.player_id = <your_id>;Последний приём не срабатывает, так как и движение пуль, и проверка столкновений, и перерождение происходят в рамках одной и той же транзакции. Поскольку транзакции атомарны, вы увидите или как все операции применятся одновременно, или ничего не увидите. К тому моменту, как заметите попадание в вас, вы уже будете мертвы. Это свойство очень полезно применительно к базам данных (а совсем не для того, чтобы бороться с читерами).
Чему я научился
Оказывается, можно довести демо Патрика до крайности: реализовать весь конвейер рендеринга на языке SQL. Притом, что этот проект работает, должен признать, что сделать его было… плохой идеей? Летает быстро, но такой код жутко сложно поддерживать и отлаживать.
Меня удивило, насколько естественно оказалось выражать состояние и логику игры на SQL. Мне даже показалось, что я случайно переизобрёл паттерн сущность-компонент-система. Оказалось, что многопользовательский режим «просто работает», поскольку источником истины является база данных, которая сама справляется со всеми непростыми аспектами конкурентности.
Попробуйте сами!
Весь код выложен на Github: репозиторий DOOMQL
Выполните:
docker pull cedardb/cedardb:latest
docker run --rm -p 5432:5432 -e CEDAR_PASSWORD=postgres --detach cedardb/cedardb:latest
# Подождите несколько секунд, пока запустится CedarDB
./server.sh
# во втором окне терминала сильно уменьшите масштаб, чтобы не было никаких сложностей из-за перехода на новую строку
python3 pyclient.py