ソースコードQuake III

[翻訳者注：この記事の最初の部分の翻訳はすでにHabréにありますが、その著者は何らかの理由で作業を完了しませんでした。]

レンダラーQuake III

Quake IIIレンダラーは、Quake IIハードウェアアクセラレータレンダラーの進化的開発でした。古典的な部分は「バイナリ分割」/「潜在的に見えるセット」のアーキテクチャ上に構築されていますが、次の2つの重要な側面が追加されています。

• OpenGL 1.X固定パイプラインの上に構築されたシェーダーシステム これは1999年にとって大きな成果でした。 これは、今日どこにでもある頂点シェーダー、幾何学シェーダー、およびフラグメントシェーダーの時代に革新のための大きなスペースを提供しました。
  
• マルチコアアーキテクチャのサポート：OpenGLクライアントサーバーモデルは一部のメソッドをブロックし、スレッドシステムはこの問題を部分的に解決します。

建築

renderer.lib完全に含まれており、 quake3.exeと静的にリンクされていquake3.exe ：



全体的なアーキテクチャはQuake Classicを繰り返します。BSP/ PVS /ライティングマップの有名な組み合わせを使用します。

• 前処理：
  
  1. ゲームデザイナーはQRadiant .mapを使用して作成し、保存します。
  2. q3bsp.exeは、バイナリスペースパーティション（BSP）でマップを切り取ります。 これについては、Quake1レンダラーのレビューで書きました。
  3. ポータルシステムはBSPから生成されます 。これについては、 Doom3 Dmapツールに関する記事で説明しました。
  4. q3vis.exeはポータルシステムを使用し、各シートのPVS（潜在的に表示されるセット）を生成します。 前の記事で説明したように、各PVSは圧縮され、bspファイルに保存されます。
  5. ポータルシステムがクリアされます。
  6. q3light.exeは、マップ上の各ポリゴンのライティングを計算し、その結果をq3light.exeマップのテクスチャとしてbspファイルに保存します。
  7. この時点で、事前に計算されたすべてのデータ（PVSとライトマップ）は.bspファイルに保存されます。
• リードタイム：
  
  1. エンジンはマップとbspをロードします。
  2. 視覚化が必要な場合：
  3. エンジンは現在のシートのPVSを解凍し、 実際に見えるものを決定します。
  4. マルチポリゴンを使用して、ポリゴンごとに、照明マップと色を組み合わせます。

エンジンを変更して、どちらか一方のみを表示すると、マルチテクスチャリングと照明マップの段階がはっきりとわかります。

レベルデザイナー/アーティストが描いたテクスチャ：



q3light.exeによって生成された照明マップ：



実行時にマルチテクスチャリングを使用して接続した場合の最終結果：



レンダリングアーキテクチャは、1999年のゲーム開発者会議でBrian Hookによってレビューされました。 残念ながら、 GDC Vaultのビデオは利用できなくなりました！ [ただし、 YouTubeにあります。]

シェーダー

シェーダーシステムはOpenGL 1.X固定パイプラインの上に構築されているため、非常に高価です。 開発者は頂点の変更をプログラムできますが、テクスチャパスも追加できます。 これについては、Quake 3 Shaderバイブルシェーダーバイブルで詳しく説明しています。

マルチコアレンダラーとSMP（対称型マルチプロセッシング）

多くの人は、Quake III Arenaがcvariable r_smpを使用したSMPサポート付きでリリースされたことを知りません。 フロントエンドとバックエンドは、標準のProducer-Consumerスキームを介して情報を交換します。 r_smpの値が1の場合、ペイントされたサーフェスは、RAMにあるダブルバッファーに交互に保存されます。 フロントエンド（この例ではメインスレッドと呼ばれます ）はバッファーの1つに交互に書き込みますが、バックエンドはもう一方（この例ではレンダラースレッドと呼ばれます）から読み取ります。

例は、すべてがどのように機能するかを示しています。

t0-t1：

• メインスレッドが描画するものを決定し、サーフェスをsurfacebuffer1に書き込みます。
• レンダラースレッドのデータがないため、ブロックされます。
• GPUスレッドも何もしません。

t1-t2：プロセスはどこでも開始します：

• メインスレッドは、次のフレームで何を表示するかを決定します。 サーフェスをsurfacebuffer2に書き込みます。これは、ダブルバッファリングの典型的な例です。
• 一方、RendererスレッドはOpenGL呼び出しを行い、GPUスレッドがすべてを安全な場所にコピーするのを辛抱強く待ちます。
• GPUスレッドは、レンダラースレッドが指す場所から表面を読み取ります。

t2では次のことに注意してください。

• レンダラースレッドはまだデータをGPUに転送しています：SurfaceBuffer1が使用されます。
• メインスレッドはSurfaceBuffer2への書き込みを終了しましたが、SurfaceBuffer1への書き込みを開始できません：ロックされています

このケース（レンダラースレッドがメインスレッドをブロックする場合）は、Quake IIIのプレイ中に非常に頻繁に発生します。
OpenGL APIメソッドの1つをブロックする制限を示します。



t2の後：

• レンダラースレッドがSurfaceBuffer1（t3）で終了するとすぐに、SurfaceBuffer2からサーフェスのアップロードを開始します。
• ロックが解除されると（t3）、メインスレッドは次のフレームで動作を開始し、SurfaceBuffer1に書き込みます。
• この構成では、GPUはほとんどアイドル状態になりません。

注：同期は、 winglimp.cの Windowsイベントオブジェクトを介して実行されます （下部にSMPアクセラレーションがあります）。

ネットワークモデル

Quake3ネットワークモデルは、間違いなくエンジンの最もエレガントな部分です。 低レベルでは、Quake IIIは依然として、Quake Worldで初めて登場したNetChannelモジュールとのデータ交換を抽象化します 。 理解する最も重要なこと：

変化の速いリズムの環境では、最初の転送中に受信されなかった情報は、それが陳腐化するため、再送信する価値はありません。

したがって、結果として、エンジンはUDP / IPを使用します。「信頼性のある送信」により許容できない遅延が発生するため、コードにはTCP / IPトレースがありません。 ネットワークスタックは、相互に排他的な2つのレイヤーで強化されています。

• 事前送信キーを使用した暗号化。
• 事前に計算されたハフマンキーを使用した圧縮。

しかし、最も素晴らしい設計はサーバー側にあり、エレガントなシステムが各UDPデータグラムのサイズを最小化し、UDPの信頼性を補います。スナップショット履歴は、メモリイントロスペクションを使用してデルタ寄木を生成します。

建築

ネットワークモデルのクライアント側は非常に単純です。クライアントは、フレームごとにサーバーにコマンドを送信し、ゲームステータスの更新を受信します。 サーバー側は、UDPパケットの損失を考慮してゲームの一般的な状態を各クライアントに送信する必要があるため、もう少し複雑です。 このメカニズムには、3つの主要な要素が含まれます。

• マスターGamestateは、物事の一般的な真の状態です。 顧客はチームをNetchannelに送ります。 これらはevent_tに変換され、サーバーが受信するとゲームの状態を変更します。
• サーバーは、クライアントごとに、ネットワークを介して送信されたゲームの最新の32個の状態を循環配列に保存します。これらはスナップショットと呼ばれます。 配列は、Quake World Networkの記事（ エレガントなソリューション ）で説明した有名なバイナリマスクトリックを使用してループします。
• サーバーには「空の」状態もあり、各フィールドの値は0です。「以前の状態」のないデルタスナップショットに使用されます。

サーバーは、クライアントに更新を送信することを決定すると、3つの要素すべてを使用してメッセージを生成し、NetChannelを介して送信します。

興味深い事実：各プレーヤーのこのような数のゲーム状態を保存すると、大量のメモリを消費します。私の測定によると、4人のプレーヤーで8 MBです。

スナップショットシステム

スナップショットシステムを理解するために、次の条件の例を示します。

• サーバーはクライアントClient1に更新を送信します。
• サーバーは、4つのフィールドを持つ状態をClient2クライアントに渡そうとしています（位置[X]、位置[Y]、位置[Z]の3つの整数値、およびヘルスの1つの整数値）。
• 通信はUDP / IPを介して行われます。これらのメッセージはインターネット上で失われることがよくあります。

フレーム1サーバー：

サーバーは各クライアントからいくつかの更新を受け取りました。 それらは、ゲームの一般的な状態（緑）に影響を与えました。 Client1に状態を渡すときです。



メッセージを生成するために、ネットワークモジュールは常に次のことを行います。

1. ゲームの一般的な状態をクライアントの履歴の次のスロットにコピーします。
2. 別のスナップショットと比較します。

それが次の画像に見られるものです。

1. ゲームの一般的な状態（Master gamestate）は、インデックス0でClient1の履歴にコピーされます：現在は「Snapshot1」と呼ばれています。
2. これは最初の更新であるため、Client1の履歴には正しいスナップショットが存在するため、エンジンはすべてのフィールドがリセットされる空のスナップショット「ダミースナップショット」を使用します。 各フィールドはNetChannelに送信されるため、これにより完全な更新が行われます。

ここで最も重要なことは、クライアントの履歴に正しいスナップショットが含まれていない場合、エンジンが空のスナップショットを取得してデルタメッセージを生成することを理解することです。 これにより、132ビットでクライアントに完全な更新が送信されます（各フィールドの前にはビットトークン ）： [1 A_on32bits 1 B_on32bits 1 B_on32bits 1 C_on32bits] 。

フレーム2サーバー：
次に、少し先に進んでみましょう。サーバーの2番目のフレームです。 ご覧のように、各クライアントはコマンドを送信し、それらすべてがゲームの一般的な状態に影響を与えました。マスターgamestate：Client2はY軸に沿って移動したため、pos [1]はE（青）に等しくなります。 Client1もコマンドを送信しましたが、さらに重要なことに、以前の更新の受信を確認したため、Snapshot1は確認済み（「ACK」）としてマークされました。



同じプロセスが実行されます。

1. ゲームの一般的な状態は、次のクライアント履歴スロットにコピーされます：（インデックス1）：これはSnapshot2です
2. 今回は、クライアントの履歴に正しいスナップショットがあります（snapshot1）。 これら2つのスナップショットを比較する

その結果、部分的な更新のみがネットワーク経由で送信されます（pos [1] = E）。 これがこのデザインの美しさです。プロセスは常に同じです。



注：各フィールドの前にはビットマーカー （1 =変更、0 =変更なし）があるため、上記の例の部分的な更新には36ビットが使用されます： [0 1 32bitsNewValue 0 0] 。

フレーム3サーバー：
システムが失われたパッケージをどのように処理するかを見るためにさらに一歩進んでみましょう。 フレーム3になりました。クライアントは引き続きコマンドをサーバーに送信します。
Client2は損害を受け、ヘルスは現在Hです。しかし、Client1は最新の更新を確認しませんでした。 UDPサーバーが失われた可能性があり、クライアントACKが失われた可能性がありますが、その結果、使用できません。



それにもかかわらず、プロセスは同じままです。

1. ゲームの一般的な状態をクライアント履歴の次のスロットにコピーします：（インデックス2）：これはSnapshot3です
2. 最後の有効な確認済みスナップショット（snapshot1）を比較します。

その結果、メッセージは部分的に送信し、古い変更と新しい変更の組み合わせを含みます：（pos [1] = Eおよびhealth = H）。 snapshot1は古すぎて使用できない場合があることに注意してください。 この場合、エンジンは再び「空のスナップショット」を使用するため、完全な更新が行われます。

システムの美しさと優雅さは、そのシンプルさにあります。 自動的に1つのアルゴリズム：

• 部分的または完全な更新を生成します。
• 受信されなかったOLD情報とNEW情報を1つのメッセージで再送信します。

イントロスペクションCメモリ

Quake3が内観のスナップショットを比較する方法を疑問に思うかもしれません...結局のところ、Cはそうではありません。

答えは次のとおりですnetField_t各フィールドの場所は、配列とスマートプリプロセスディレクティブを使用して事前に作成されます。

  typedef struct { char *name; int offset; int bits; } netField_t; //        ... #define NETF(x) #x,(int)&((entityState_t*)0)->x netField_t entityStateFields[] = { { NETF(pos.trTime), 32 }, { NETF(pos.trBase[0]), 0 }, { NETF(pos.trBase[1]), 0 }, ... } 

この部分の完全なコードは、 MSG_WriteDeltaEntityます。 Quake3は、何を比較しているのかさえ知りません。entityStateFieldsのインデックス、オフセット、サイズを盲目的に使用し、ネットワークを介して差分を送信します。

予備的な断片化

コードを詳しく調べると、UDPデータグラムの最大サイズが65507バイトであるにもかかわらず、NetChannelモジュールがメッセージを1400バイトのブロック（ Netchan_Transmit ）にカットすることがわかります。 そのため、ほとんどのネットワークでは最大パケットサイズ（MTU）が1500バイトであるため、インターネット経由で送信するときに、エンジンがルーターによるパケットの破損を回避します。 ルータのフラグメンテーションを取り除くことは非常に重要です：

• ネットワークに入ると、ルーターはパケットを断片化するまでブロックする必要があります。
• ネットワークを離れるとき、データグラムのすべての部分を待ってから多くの時間をかけて収集する必要があるため、問題はさらに深刻です。

信頼性が高く信頼性のない送信を伴うメッセージ

スナップショットシステムは、ネットワーク上で失われたUDPデータグラムを補正しますが、一部のメッセージとコマンドは必ず配信する必要があります（たとえば、プレーヤーがゲームを離れるとき、またはサーバーがクライアントに新しいレベルをロードする必要があるとき）。

このバインディングは、NetChannelモジュールによって抽象化されています。これについては、以前の投稿の1つで書きました 。

推奨読書

開発者の1人であるブライアンフックは、ネットワークモデルに関する短い記事を書きました 。

遅れのない著者ニール「ヘイスト」トロントもそれを説明しました 。

仮想マシン

以前のエンジンが仮想ゲームプレイのみを仮想マシンに与えた場合、idtech3はそれを非常に重要なタスクに任せます。 とりわけ：

• 可視化はクライアント仮想マシンで実行されます。
• 遅延補正メカニズムは、クライアントVMに完全に実装されています。

さらに、その設計ははるかに複雑です。Quake1仮想マシンの保護/移植性とネイティブQuake2 DLLの高性能を組み合わせています。 これは、バイトコードをオンザフライでx86コマンドにコンパイルすることにより実現されます。

興味深い事実：仮想マシンはもともと単純なバイトコードインタープリターであるはずでしたが、パフォーマンスは非常に低かったです。 したがって、開発チームはランタイムx86コンパイラーを作成しました。 1999年8月16日付の.planファイルによると、このタスクは1日で完了しました。

建築

Quake III仮想マシンはQVMと呼ばれます。 その3つの部分は常にロードされています。

• クライアント側：2つの仮想マシンがロードされます。 ゲームの状態に応じて、メッセージはそれらの1つに送信されます。
  
  • cgame ：バトルフェーズでメッセージを受信します。 不可視のグラフィックスのクリッピング、予測、およびrenderer.lib制御のみを実行しrenderer.lib 。
  • q3_ui ：メニューモードでメッセージを受信します。 システムコールを使用してメニューをレンダリングします。
  
  
• サーバー側：
  
  • game ：常にメッセージを受信し、ゲームロジックを実行し、AI操作にbot.libを使用します。

QVM内部

QVMの使用について説明する前に、バイトコードの生成方法を確認しましょう。 いつものように、私はイラストと簡単な付随テキストを使用して説明することを好みます：



quake3.exeとそのバイトコードインタープリターはVisual Studioを使用して生成されますが、VMバイトコードはまったく異なるアプローチを使用します。

1. 各.cファイル（翻訳モジュール）は、LCCを使用して個別にコンパイルされます。
2. LCCは、出力がPE（Windows Portable Executable）ではなく、スタックされたマシンのテキストアセンブリである中間表現であるため、特別なパラメーターと共に使用されます。 作成される各ファイルは、 textの一部、 data 、および文字のエクスポートとインポートを含むbssで構成されます。
3. q3asm.exeと呼ばれる特別なidソフトウェアツールは、すべてのアセンブリテキストファイルを受け取り、それらをまとめて.qvmファイルに収集します。 さらに、すべての情報をテキストからバイナリに変換します（ネイティブの変換ファイルを使用できない場合のために、速度を上げるため）。 q3asm.exeは、システムによって呼び出されるメソッドも認識します。
4. バイナリバイトコードをダウンロードした後、 quake3.exeそれをx86コマンドに変換します（必須ではありません）。

内部LCC

以下は、仮想マシンで実行する必要がある関数から始まる特定の例です。

  extern int variableA; int variableB; int variableC=0; int fooFunction(char* string){ return variableA + strlen(string); } 

変換module.c lcc.exeれているmodule.c lcc.exe 、Windows PEオブジェクトの生成を回避し、中間表現に出力するために、特別なフラグで呼び出されます。 これは、上記のC関数に対応する.obj LCC出力ファイルです。

  data export variableC align 4 LABELV variableC byte 4 0 export fooFunction code proc fooFunction 4 4 ADDRFP4 0 INDIRP4 ARGP4 ADDRLP4 0 ADDRGP4 strlen CALLI4 ASGNI4 ARGP4 variableA INDIRI4 ADDRLP4 0 INDIRI4 ADDI4 RETI4 LABELV $1 endproc fooFunction 4 4 import strlen bss export variableB align 4 LABELV variableB skip 4 import variableA 

いくつかのメモ：

• バイトコードは部分（ text 、 data 、およびbss ）に分割されtext ： bss （初期化されていない変数）、 data （初期化された変数）、およびcode （通常textと呼ばれtext ）
• 関数は、 proc 、 endprocサンドイッチを使用して定義されます。
• LCCの中間表現はスタックされたマシンです。すべての操作はスタック上で実行され、CPUレジスタに関する仮定は行われません。
• LCCフレーズの最後に、変数/関数をインポート/エクスポートするファイルのグループがあります。
• 各アナウンスメントは、操作のタイプ（ ARGP4 、 ADDRGP4 、 CALLI4など）でCALLI4ます。 各パラメーターと結果はスタックにプッシュされます。
• インポートとエクスポートはここにあるため、アセンブラは翻訳モジュールを「リンク」できます。 import strlenが使用されることに注意してください。q3asm.exeもVMインタープリターも標準Cライブラリにアクセスしないため、 strlenはシステムコールと見なされ、仮想マシンによって実行されます。

このようなテキストファイルは、VMモジュールの各.cファイルに対して生成されます。

Q3asm.exeの内部

q3asm.exeは、LCC q3asm.exeテキストファイルを受信し、それらを.qvmファイルに収集します。



ここで次のことがわかります。

• q3asmは、テキストファイルの各インポート/エクスポート文字を理解します。
• 一部のメソッドは、システムコールのテキストファイルで事前定義されています。 クライアントVMおよびサーバーVMの syscallを確認できます 。 システムコールシンボルには、インタープリターが認識できるように、負の整数値の形式の属性があります。
• q3asmは、スペースと速度を確保するためにプレゼンテーションをテキストからバイナリに変更しますが、ここでは最適化は行われません。
• 組み立てられる最初のメソッドは、入力メッセージマネージャであるため、 vmMainである必要があります。 さらに、バイトコードの0x2Dテキストセグメントに0x2Dれている必要があります。

QVM：仕組み

繰り返しますが、スケジューリングを実行する一意のエントリポイントと一意の出口ポイントを示す画像：



いくつかの詳細：

メッセージ（Quake3-> VM）は、次のように仮想マシンに送信されます。

• Quake3のどの部分でもVM_Call( vm_t *vm, int callnum, ... )を呼び出すことができます。
• VMCallは、最大11個のパラメーターを受け取り、各4ビット値を0x00から0x26のVMバイトコード（ vm_t *vm ）に書き込みます。
• VMCallは、メッセージ識別子をVMCall書き込みます。
• インタープリターは、0x2D（ q3asm.exeがq3asm.exe書き込んだvmMain ）のオペコードの解釈を開始します。
• vmMain 、対応するバイトコードメソッドにメッセージをディスパッチおよびルーティングするために使用されます。

クライアントVMとサーバーVMによって送信されたメッセージのリストは、各ファイルの最後に表示されます。

システムコール（VM-> Quake3）は次のように行われます。

• インタープリターは1つずつ、VMオペコード（ VM_CallInterpreted ）を実行します。
• CALLI4オペコードを検出すると、intのメソッドのインデックスをチェックします。
• 値が負の場合、呼び出しはシステムです。
• システムコール関数へのポインター（ int (*systemCall)( int *parms ) ）はパラメーターで呼び出されます。
• systemCallが指す関数を使用して、システムコールをquake3.exeの目的の部分にディスパッチおよびルーティングします。

クライアントVMとサーバーVMによって提供されるシステムコールのリストは、各ファイルの上部にあります。

: , (char,int,float), (char*,int[]). , struct Visual Studio LCC.

: Quake3 , QVM , C (strlen, memset , ). : Malloc in QVM .

. Unlagged « ».

- :

• .
• Visual Studio.
• QVM . .
• - , .

idTech3 DLL , :



, :

• 解釈されたバイトコード
• x86コマンドにコンパイルされたバイトコード
• Windows DLLにコンパイルされたコード

推奨読書

人工知能

modderコミュニティは、以前のすべてのidTechエンジン用のボットシステムを作成しました。かつて、2つのシステムが非常に有名でした。

• Quake1はOmicronでした。
• Quake2でGladiatorを作成しました。

しかし、idTech3の場合、ボットシステムはゲームプレイの基本的な部分であったため、社内で開発する必要があり、最初はゲームに存在する必要がありました。しかし、開発中に深刻な問題が発生しました。

出典：Masters of Doomブックの275ページ：

— . — , . , . Quake III, , . .

, . , , , . .

, , . , , . . 1999 , .

建築

- (Mr.Elusive), , «Omicron» «Gladiator». , bot.lib :



, - (Jean-Paul van Waveren)
103- . , (Alex J. Champandard) , , . Quake3.