Недавно я набрёл на шедевр Патрика — клон 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.
Рейкастинг
Рекурсивная логика трассировки лучей реализована по образцу, предложенному Патриком в его посте о 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 мс Метаигра с жульничеством
Поскольку клиенты отправляют сырой код 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
Fell-x27
Абсолютно проклято, но, в контексте Doom это даже лорно.