HN 日本語サマリー

← 一覧へ戻る
プログラミング

オリジナルのDoomをSQLに移植しました

We ported the original Doom to SQL (cedardb.com)

290 pointsby Vaslo44 コメント

要約

この記事では、1993年発売のオリジナルのDoomのゲームロジックとレンダラーをSQLに移植し、データベース内で実行したプロジェクトについて解説しています。ゲームループはオリジナルの35 FPSで動作し、レンダラーは最大60 Hzで完全な320x200のフレームバッファを生成します。Pythonはタイミング、キーボード入力、ビットマップ表示のみを担当し、マルチプレイヤーも機能します。

全文翻訳

オリジナルのDoomをSQLに移植しました

dev 2026年9月22日 • 25分

オリジナルのDoomのゲームロジックとレンダラーを、両方ともSQLクエリとして実装しました。さらに、デスマッチも動作します。

要約: 1993年発売のオリジナルDoomのゲームロジックとレンダラーをSQLに移植し、データベース内で実行しました。ゲームループはオリジナルの35 FPSで動作し、レンダラーは私のラップトップ上で最大60 Hzで完全な320x200フレームバッファを生成します。Pythonはタイミングの管理、キーボード入力の読み取り、そして返されたビットマップの表示のみを担当します。マルチプレイヤーも動作します。

[動画: お使いのブラウザは動画タグをサポートしていません。]

SQLDoomの動作中の様子 (AMD Ryzen 7 7840U)

今すぐプレイできます デスマッチ、4人スロット、先着順です。

🇪🇺 EUサーバー上のSQLDoom

🇺🇸 USサーバー上のSQLDoom

これは最初のエピソードのシェアウェア版です。すべてのシートが埋まっている場合は、キューに入ります。キューがいっぱいの場合でも、待っている間にSQL経由でライブゲームの状態を調べることができます。

SQLDoom

昨年、私はDOOMQL [Github] を公開しました。それは約30 FPSでDoomに似たASCIIアートをレンダリングし、多くの人に好評でした。しかし、一部の人々からは、レイキャスティングアプローチを使用しているため、DoomよりもWolfenstein 3Dに近いと指摘されました。一方、DoomはBSPツリーを使用しており、これにより正しい深度順序付けが容易になり、テクスチャ、任意の壁角度、および異なる床の高さを実現できます。

私はこのままにしておくことができず、いくつかの試行錯誤(ご想像の通り、再び育児休暇中)を経て、ついにSQLだけで完全に動作する本物のDoomを発表できることを嬉しく思います。

[画像: これらは1993年のバイナリとSQLクエリのどちらかです。どちらがどちらか分かりますか?]

これらは1993年のバイナリとSQLクエリのどちらかです。どちらがどちらか分かりますか?

ルール

まず、達成したいことのいくつかの基本ルールを確立しましょう。

  1. 本物のDoomのように見えること。DOOMQLの視覚的忠実度は、今となってはかなり残念です。
  2. しかし、さらに重要なのは、本物のDoomのように感じられること。オリジナルのゲームは純粋な楽しさです。
  3. レンダリングは純粋にSQLベースであること。許容される唯一のSQL出力は、各ピクセルの正確なRGB値をエンコードしたテーブルまたはビットマップです。
  4. ゲームループも純粋にSQLベースであること。ただし、DB内でユーザー定義関数を使用することは許容されます。
  5. 入力の解析、ゲームティックの駆動、出力ビットマップのレンダリングのみを担当する場合、他のプログラミング言語でクライアントを作成することは許可されます。

アーキテクチャ

Pythonは意図的に単純(ルール5)です。単一のスクリプトが pygame を使用して入力を駆動し、出力ビットマップを描画し、毎秒35回ゲームティックをトリガーします。ゲームロジック、ゲーム状態、レンダラーはデータベース内に存在します。

                         Python
                 input / timing / display
                    |              ^
                    |              |
          run game tic        request frame
                    |              |
                    v              |
          +----------------+  +----------------+ 
          |                |  |                |
          | SQL game logic |  |  SQL renderer  |
          |                |  |                |
          +-------+--------+  +--------+-------+
                  |                    ^
                  |                    |
                  v                    |
             +-----------------------------+
             |                             |
             |       game state tables     |
             |                             |
             +-----------------------------+

2つのパスは意図的に分離されています。ゲームロジックは固定の35 Hzループで実行され、レンダラーはゲーム状態テーブルの純粋な関数であり、クライアントはいつでも(つまり、可能な限り速く、頻繁に)新しいフレームを要求できます。

ゲームデータのロード

都合の良いことに、Doomの.wadファイル形式は実際には非常にリレーショナルです。

2つの VERTEXES が LINEDEF で接続され、LINEDEF には2つの SIDEDEF があります。SIDEDEF は SECTOR を境界とし、SECTOR には THINGS を含めることができます。WAD全体をデータベースに変換するのは驚くほど簡単で、約1000行のPythonで完了しました。Doom 1全体をインポートするには、私のラップトップで約18秒かかります。

例えば、E1M1を鳥瞰図でレンダリングするクエリは次のようになります。

WITH wall AS (
  SELECT round((v1.x + (v2.x - v1.x) * t / 32.0) / 48) AS col, -- 48 units per column
         round((v1.y + (v2.y - v1.y) * t / 32.0) / 96) AS row, -- chars are 2:1
         l.left_sd_id < 0 AS solid -- one-sided lines are pass-through
  FROM linedefs l, generate_series(0, 32) AS t        -- walk each line in 32 steps
  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(私が楽しんでいる様子)の実行例です。

[画像: ロケットランチャーで兵士3人をバラバラにする]

ロケットランチャーで兵士3人をバラバラにする

この短いクリップだけでも、多くのことが起こっているのがわかります。

  • プレイヤーの入力をポーリングして処理する必要がある(歩行、旋回、射撃)
  • 敵が歩き、攻撃する
  • アイテムが拾われる
  • ロケットランチャーが発射され、弾丸が移動する
  • ロケットの爆発には爆風半径がある
  • 敵のスプライトをレンダリングする必要がある
  • アニメーション、ビューボビング、HUD

そして、これらすべてを処理する時間はあまりありません。オリジナルのDoomは固定の35 Hzクロックで動作していたため、1ティックの予算は 1000 ms × 35 Hz = 28.6 ms です。また、1ティックあたり正確に1フレームを描画していたため、35 FPSに制限されていました。

SQLDoomはゲームロジックを35 Hzに保ち(そのため、すべてのオリジナルの定数は引き続き機能します)、描画を分離します。クライアントは好きな時にフレームをクエリ(Get it?)でき、ティック間でカメラ位置を補間します。したがって、注意すべき2つの予算があります。

  • 28.6 msごとにティックを実行する(そうでなければ完全に間違った感じになる)
  • 毎秒少なくとも35フレームをレンダリングする(それ以下でも許容できるが、スムーズには感じられない)
ティックシーケンス

ゲームティックは本質的に手続き的です。ティックごとに実行する必要がある一連のタスクがあります。CedarDBには cedarscript というスクリプト言語があり、これはPL/pgSQLに似ており、ティックごとに何を行うかを事前に計画できます。

ティック関数の小さなセクションを以下に示します。

doom_cs_clock(map, p);
let mut plan = doom_cs_plan(map, p);    -- returns a bitmask of functions to trigger

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);                  -- full movement, or just turning
doom_cs_death(map, p);                  -- process deaths

plan = doom_cs_plan(map, p);            -- the world moved; re-plan
plan = doom_tic_secrets(map, p, plan);  -- secrets, walkover lines, pickups
plan = doom_tic_weapon(map, p, plan);   -- weapon state, hitscan, damage
...
if sound_due { doom_cs_sound(map, p); } -- yes, we also play sounds
doom_cs_monsters(map, p);               -- always
doom_cs_sector_fx(map, p);              -- always
doom_cs_thing_physics(map);             -- always

上記のPythonドライバーは、1/35 秒ごとに SELECT doom_run_game_tic(...) を呼び出します。

呼び出された各関数は、SQLステートメントのバッチを実行します。以下は、モンスターAIの状態機械の一部です。

-- Abridged from sql/runtime/functions/26_cs_monsters.sql.
WITH RECURSIVE
  monsters AS ( [...] ),   -- who is alive, what kind, where
  los      AS ( [...] ),   -- visible, in_view_cone, dist: recursive, walks walls
  decision AS ( [...] ),   -- one row per actor: its state and what it can see
  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 -- GORY EXPLOSION!
        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          -- animation still running
        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 more
        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%を消費します。

6体のモンスターがいるより典型的なティックは、平均で2.15ミリ秒、つまりバジェットの約8%です。かなりの余裕があります!

正直なところ、かなり複雑なゲームロジックをSQLで表現するのがいかに簡単かに驚きました。ゲームロジックはわずか約5900行のSQLです。これは多く聞こえるかもしれませんが、オリジナルのCソースコード(約9000行)よりも間違いなく少ないです!

また、考え方を強制されます。例えば、敵を1体ずつ反復処理する代わりに、単純な UPDATE ... WHERE condition を記述するだけで、データベースがそれをどのように最適に適用するかを(並列で自動的に)判断します。

それが、エンティティコンポーネントシステム(ECS) パターンを私に理解させてくれた理由でもあります。ここでは、各 entity(プレイヤー、モンスター、アイテムなど)は複数の components(位置、スプライト、ステータスなど)を持ち、system(モンスターAI、プレイヤー移動、ダメージ計算)は特定のコンポーネントセットを持つエンティティが互いにどのように相互作用するかを決定します。ECSはデータ局所性と、特定のコンポーネントセットを持つエンティティをどのように反復処理するかについて多くを語ります。SQLでは、データ集約型処理に非常に慣れています!各コンポーネントはテーブルになり、各システムは関心のあるテーブルをエンティティを結合キーとして結合する update または insert になります!

レンダリング

各フレームは、レベルジオメトリとゲーム状態、およびプレイヤー位置を入力として読み取り、完全なフレームバッファを返す巨大なビューです。レンダリングパイプライン全体の概要を以下に示します。

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 ( ... ),    -- walk the BSP, culling invisible segments
  clipped, projected, on_screen,  -- project segments to screen space
  wall_parts, columns, fragments, -- one row per wall pixel
  panel_clips, plane_spans, ...,  -- ceiling/floorclip as window functions, visplanes
  thing_pixels, sprite_fragments, -- sprites
  fragment_union, resolved,       -- every candidate pixel, resolve for the nearest
  view_colored, ui_colored,       -- COLORMAP, status bar
  framebuffer AS ( ... )          -- 64,000 rows of (x, y, rgb)
SELECT string_agg(rgb, ''::bytea ORDER BY y, x) AS frame_rgb
FROM framebuffer;                  -- 192,000 bytes, one row

実装は約1300行のSQL(コメントを除く)で、89個のCTEに分散されているため、SQLクエリとしてはかなり複雑です!

[画像: 単一のレンダリングフレームの全89 CTE]

単一のレンダリングフレームの全89 CTE

しかし、完全な狂気のように見えますが、このパイプラインは実際にはDoomが行っていることにかなり近いです。SQLには1つの利点さえあります。linux_doom ソース は、レンダリングエンジンに約3300行(コメントを除く)を使用しています。SQLDoomの約2.5倍の行数です。そもそも良いアイデアだったかどうかは別の問題であり、後でそれについて話しましょう。

まず、レンダリングパイプラインの最も興味深い部分を見てみましょう。

[画像: レンダリングステージごとのフレームの視覚化]

レンダリングステージごとのフレームの視覚化

左半分はBSPベースのカリングを示し、右半分は壁レンダリングとビズプレーンを視覚化します。

BSPトラバーサル

1993年当時、ハードウェアアクセラレーション付きのZバッファリングを備えたGPUを持っていた人は誰もいなかったため、Doomは正しい順序で描画することによってオクルージョンを正しく処理する必要がありました。Doomが行う方法は非常に巧妙です。前面から背面へ描画し、すでに描画したピクセルを追跡します(つまり、壁ピクセルをすでに描画した場合、その背後にあるモンスターを描画する必要はありません)。しかし、それは言うは易く行うは難しです。レベル内のすべてを深度順に並べる効率的な方法が必要です。

Doomはこの順序付けを、doom.wad ファイルに焼き付けられた事前計算されたBSPツリーを使用して取得します。ツリーの各ノードはマップを2つに分割する線です。マップのセクターは多くのサブセクターに分割され、それらはこれらの線の両側に配置され、ツリーに挿入されます。これにより、次のプロパティが得られます。

  1. 各サブセクターはリーフである。
  2. 各サブセクターは凸である(つまり、どこからでも任意の壁が見える)。
  3. 各ツリーノードで、カメラ側にあるサブツリー全体は、反対側にあるサブツリーよりも前面にあることが保証される。

したがって、BSPツリーを再帰的にトラバースすることで、すべてのサブセクターの前面から背面への順序が得られます。これにより、直接レンダリング順序が得られます。画面領域がより近いもので覆われたら、その背後にあるオブジェクトはスキップできます。

これがどのように動作するかを以下に示します(フルスクリーンで表示する必要があるかもしれません):[動画: お使いのブラウザは動画タグをサポートしていません。]

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,
         -- back = 1 at bit (40 - depth), front = 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   -- was any parent bbox culled?
  FROM node_path_steps st -- materialized view, every root-to-ssector path
  JOIN nodes n ON ...
  CROSS JOIN LATERAL (SELECT ... AS front_side) fs -- on which side are we?
  JOIN visible_children vc ON ...
  GROUP BY st.ssector_id
) s WHERE s.visible;

1つの sum() ... order by が、再帰的な下降全体を置き換えます!40ビットは、どのようなマップにも対応できるはずです。最も深いBSPツリーはE4M8のもので、わずか32レベルです。マップがバニラマップの最大値の256倍より大きくない限り、すべて大丈夫です!

注意深く見ると、BSPトラバーサルがカリングも処理していることがわかります。都合の良いことに、.wad の各ノードは、そのすべての子供のバウンディングボックスも定義しています。私たちのビューフラスタムがそのバウンディングボックスの完全に外側にあることを証明できれば、そのサブツリーをレンダリングのために考慮する必要はありません。それが visible_children.keep が示すものです。したがって、bool_and(vc.keep) は、親のいずれかが資格を満たさないすべてのサブセクターをドロップします。

パイプラインのそれ以降のすべては bsp_seq に対して結合されるため、表示可能なサブセクターのみが正しい順序で考慮されます。

壁とビズプレーン

Doomは一種のチートです。3Dのように見えますが、実際には2.5Dゲームです。基本的に、垂直な壁と天井が常に地面と平行である平坦な表面です。これにより、実際の3Dエンジンよりもレンダリングがはるかに容易になります。

  1. すべての壁を描画する(前面から背面へ、前述の通り)。
  2. まだ描画されていないものはすべて、床または天井です。それを描画します。
  3. スプライト(モンスター、樽、アイテム)は、常にあなたの方を向く平坦な画像です(段ボールの切り抜きを想像してください)。したがって、複雑な変換は必要ありません(壁と重なる場合を除く)。
壁

壁は一連の連続した画面列を占め、各列内ではピクセルの連続した範囲です。したがって、壁を前面から背面へ1つずつ、行と列を generate_series() で展開して描画できます。

columns AS ( -- emit a row per screen column the wall w covers
  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 ( -- one row per pixel the wall covers in this column
  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は2つのループを使用します。画面列を取得するための R_RenderSegLoop と、ピクセルを描画するための R_DrawColumn です。

壁のレンダリングは平均で1.7 msかかります。

ビズプレーン

壁の処理が終わったところで、楽しい部分について話しましょう。床と天井、Doomがビズプレーンと呼ぶものです。

残念ながら、Doomのレンダリングアルゴリズムは、非常に命令的であるため、SQLにはそれほどうまく翻訳されません。Doomは ceilingclip と floorclip という2つの配列を保持しており、各画面列に1つのエントリがあります。これらは、まだ床または天井になっておらず、描画されていない各列の帯をマークします。新しい壁が描画されるたびに、それらは変更され、すべてのピクセルが埋まるまで続きます。Doomはそれらを変更するだけでなく、正しい順序で変更することが非常に重要です。これは巧妙です!最終的には単なる塗りつぶしアルゴリズムですが、すべてが3Dに見えます(もちろん、C言語では)。

SQLDoomは、SQLにはループや変更可能な状態の概念がないため、この問題に異なるアプローチを取る必要があります。したがって、ループの代わりに、ソートと集計を使用してそれらのソートされた実行を処理します。これは貧弱なループの代替手段です。

ここで反復処理するものはパネルと呼ばれます。画面の1つの列に表示される壁の一部です。一部のパネルは何かを描画します:ソリッドな壁(solid)、ドアの上部(upper)、または窓やパラペットの下部(lower)。一部のパネルは、他のパネルのレンダリング方法に影響を与えるだけです。バルコニーの下のドアから出ると、頭上に何かがあり、それはどこかで終わる必要があります。

したがって、各画面列(col_x)について、近くから遠くへのパネルの順序リストがあります。パネル前のクリップ状態は、前の行によって完全に定義されます。ウィンドウ関数が匂いますか?

これはテキストで説明するのが非常に難しいため、代わりにビデオを見てみましょう![動画: お使いのブラウザは動画タグをサポートしていません。]

ビズプレーンの位置決定(ウィンドウ関数を使用)

以下は、(省略された)SQLクエリです。

panel_clips AS (
  -- 1. the band as the NEARER panels left it
  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. whatever the band leaves uncovered is a ceiling above the wall...
  SELECT col_x, fsec AS sector_id, f_ceil AS plane_z, 'ceil' AS plane,
         cc_before         AS y0,   -- from where nearer walls stopped
         f_ceil_y::int - 1 AS y1    -- down to this panel's own ceiling
  FROM panel_clips
  WHERE part IN ('solid','upper','upper_open','upper_flush')
    AND f_ceil_y::int - 1 >= cc_before          -- nothing left open: skip
  UNION ALL
  -- ...and a floor below it
  SELECT col_x, fsec, f_floor, 'floor',
         f_floor_y::int AS y0,      -- from this panel's own floor
         fc_before      AS y1       -- down to where nearer walls stopped
  FROM panel_clips
  WHERE ...
)

まず、シーン内のピクセルを描画する可能性のある各パネルについて、どのくらいの列がまだ割り当てられていないかを計算します。そして、すでに割り当てられている可能性のあるピクセルは、すべてより近いパネルからのものです(これは (1) の ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING 項です)。*次に、前のパネルの終わりから次のパネルの始まりまで、いくつかのピクセルを描画します(2)。これは天井と床の両方に対して行います。

命令型アルゴリズムをセットベースとして偽装するかなりハッキーな方法ですよね?ウィンドウ関数があってよかった…

床、天井、空のレンダリングは通常約3 msかかります。

醜い部分

残念ながら、私はあなたに嘘をつかなければなりませんでした。壁、ビズプレーン、スプライトの解像度はまだ何も描画していません。それらは単に (x, y, depth, colour) の形式の候補を生成するだけで、同じ位置に複数のピクセルがある可能性があります。Doomの固定小数点演算を実装していないため、異なる壁、床、空が重なる可能性があります。また、スプライトをレンダリングする必要があり、それらは壁によって部分的に隠される可能性があります。Doomは、これが発生しないように、Zバッファリングを回避するために非常に綿密に振り付けられたダンスを行っています。私はSQLでその振り付けを再現しようとして失敗したので、あきらめて総当たり法を使用しました。すべてを生成してから勝者を選びます。

((LEAST(depth, 131071.0) * 4096)::bigint << 34) -- depth, clamped to 17.12 fixed-point
| ((2 - surface_priority) << 32)                -- wall > sprite > plane
| (LEAST(source_priority, 3) << 30)
| ((stable_id + 32768) << 14)                   -- stable tiebreak
| (light_index << 8) | palette_index            -- the payload
AS winner_key
...
SELECT pix, MIN(winner_key) FROM ranked_fragments GROUP BY pix

BSPツリーと同じトリックで、すべてを bigint にパックし、最小値を選択します。最上位ビットは深度なので、最小値を選択するだけで勝者を見つけることができます。ペイロード(つまり、ピクセルの色)もキーの一部であるため、再度結合する必要さえありません!これは少しハッキーに見えますが、これはピクセルごとの作業(Doomの1フレームは 320*200=64000 ピクセル)なので、あまり多くの作業をしないように注意する必要があります。

この最適化を使用しても、これは依然としてフレームの最も高価な部分です。平均で8.2ミリ秒、フレーム全体の3分の1以上です!そして、まさにジョン・カーマックがそれを避けた理由です。しかし、幸いなことに、現在ではSQLでこれでも35 FPSのターゲットを達成できるマシンがあります。未来は今、老人よ!

レンダリングパフォーマンス

Doomの35 FPSフレームターゲットと比較したパイプラインのウォーターフォールビューを以下に示します。[画像: AMD Ryzen 7 7840U 上のレンダリングパイプライン]

AMD Ryzen 7 7840U 上のレンダリングパイプライン

私のラップトップ(Ryzen 7 PRO 7840U)では、通常約60 FPSですが、非常に負荷の高いシーンでは35 FPSまで低下します。

パイプラインの最も高価な部分は(驚くことではありませんが):

  • ビズプレーンのレンダリング(反復アルゴリズムをエミュレートする必要がある場所)
  • 深度解決(オリジナルの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 row)

各ペレットは 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 rows)

テーブルに格納されているアイテムのプロパティは、すべてを非常に簡単にモッドできるようにします。私が十分なダメージを与えられていないことに不満を感じ、ショットガンを一度に500発のペレットを発射するようにモッドした次のクリップを見てください。

[画像: ショットガンのモッド]

チート…ショットガンのモッド

もちろん、JSONなどのファイルにすべてを保存することもできましたが、それは意味します。

  1. 制約は変更時に検証されない。
  2. 変更を有効にするには再読み込みが必要になる。
マルチプレイヤーはほぼ無料で手に入る

さて、このすべての手間をかけてDoomをSQLに移植しましたが、データベースの最大の強みをまだ活用していません。つまり、マルチプレイヤーサーバーが無料で手に入ることです!聞いてください、従来のゲーム開発者が自分で構築しなければならない多くのものを無料で手に入れることができます。

  • 認証
  • 並行処理制御
  • アクセス制御
  • ゲーム状態の一貫したスナップショット
  • バイナリワイヤプロトコル

別のPython referee スクリプトが共有の35 Hzクロックを駆動し、マップをローテーションします。プレイヤーのオンラインクライアントが入力を供給します。

しかし、私が最も気に入っている部分はアトミック性です。ゲームティックを実行するたびに、begin transaction と言って、最後に commit するだけです。各プレイヤー(Doomデスマッチは最大4人までサポート)は、ティックトランザクションが開始される前の世界の様子か、完全にコミットされた後の世界の様子かの、一貫したビューを取得します。部分的に適用された更新、物理バグ、またはロケットが実際に当たったかどうかについての意見の相違はありません。

驚くほどエレガントだった2番目の部分は、アクセス制御でした。sqldoom自体は約110のテーブルと100を超える関数を持っていますが、4人のプレイヤーロールは、いくつかの明確に定義された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 キーを押したか?)、実行中か?、マウスによる旋回か?、発砲ボタンを押しているか?、どの武器が選択されているか?、そしてボタンを押したりドアを開けようとしているか?(スペースバー)です。プレイヤーの入力値さえ信頼する必要はありません。関数は入力値を許可された値にクランプします。

マルチプレイヤーのパフォーマンスも驚くほど良好です。クライアントあたり3コアで安定した35 FPSを達成し、ゲームティックは依然として予算を大幅に下回っています。ティックドライバーに追加のコアを1つ追加すると、16コアのマシンはオリジナルの -altdeath Doomデスマッチを実行するのに十分です。

公開インスタンスはエピソード1のマップをローテーションしており、10分ごとに新しいマップが登場します。4つのスロットすべてが埋まっている場合でも、SQLコンソールからライブマッチをクエリできます。プレイ、またはライブマッチをクエリ →

ボーナス:SQLのコンパイル

C++で書かれたデータベースがSQLを解釈するのは、信じられないほど非効率的で、Cに匹敵できないはずですよね?おそらくそうではありませんが、それがどれほど離れているかを評価したかったのです。

CedarDBはコンパイルデータベースシステムです。すべての複雑なクエリは(複数のステップを経て)LLVM IRに変換され、マシンコードにコンパイルされます。そこで、自分自身に質問しました。生成されたマシンコードは、オリジナルのコンパイル済みlinux_doom Cコードとどのように異なりますか?

[画像: コンパイルされたlinux_doomとSQLDoomの比較]

コンパイルされたlinux_doomとSQLDoomの比較

上の半分はオブジェクトの移動ロジックとそれが運動量にどのように影響されるかを示しています。左側はオリジナルのDoomソースコード、右側はSQLDoomの実装を示しています。ロジックが少し異なる場所に分散しているため、比較は直接的ではありませんが、Cコードは48命令にコンパイルされ、SQLDoomは117命令かかります。これらの追加命令のうち42は、テーブルに結果を格納するためのものです(緑色の線)。C言語はもちろんそれを行う必要はありません。したがって、劣っていますが、間違いなくそれほど劣っているわけではありません。通常、SQLとCPUの間には多くの抽象化レイヤーがあります。SQLから始まり、クエリオプティマイザーを通過してからLLVMに到達したものを考えると、ギャップは驚くほど小さいと感じました。

ジョン・カーマックは天才だった。

つまり、SQLDoomをWolfenstein 3Dのような前身であるDOOMQLと比較してください。[画像: DOOMQL vs SQLDoom]

DOOMQL vs SQLDoom

どちらも同じエンジンと制約を使用しています。SQLを入力、ビットマップを出力とします。そして、誤解しないでください。DOOMQLのプリミティブなレイキャスティングアプローチは素晴らしいです。SQLで定式化しやすく、ステップ間の依存関係も少なく、SQLのセットベース処理に非常に適しています。

しかし、最適なフィットが常に最良の結果をもたらすとは限らないことが判明しました。SQLDoomのBSPツリーアプローチははるかに高速であり、視覚的忠実度も同時に高いです。すべてジョン・カーマックが、少しの煙と鏡で486からどれだけ引き出せるかを真剣に考えたからです。

そして、正直なところ、CedarDBも追いつきました。DOOMQLを構築したとき、エンジンはかなり遅く、まだロールベースのアクセスシステムがありませんでした。

自分で実行する方法

GitHubのgithub.com/cedardb/sqldoom にあります。

3つのものが必要です。

  1. CedarDB Community Edition
  2. psycopg2 と pygame を使用するPython
  3. そして、私が提供できないDoom IWAD。シェアウェアのdoom1.wadは自由に再配布可能(apt install doom-wad-shareware)であり、エピソード1をプレイするには十分です。小売版のWADは、所有していれば動作します。

その後はREADMEに従うだけで、すぐに独自のSQLDoomを実行できます!

あるいは、それがすべて面倒に聞こえる場合は、公開インスタンスで試合に参加してください。

続きを読む

CedarDBブログでさらに読む

すべて表示