【GDC 2019】「黒い砂漠」におけるMOBナビゲーションのメカニズム

　GDC3日目の3月20日（現地時間）、韓国Pearl Abyssは「Black Desert」（邦題「黒い砂漠」）のボクセルベースナビゲーションに関する講演を行なった。

　登壇したのは、2010年のPearl Abyss創立メンバーにして、本作のモンスターAI、動的天候システム、キャラクターアクションのプログラムを担当したKyungin Min氏。現在は、モバイル版「黒い砂漠 MOBILE」プログラムチームのチームリーダーを務めている。

　MMORPGにおいて、大量の動的オブジェクトを効率良くさばくのは、ひとつの大きなテーマだと言える。実現の手段には、いくつかのアプローチが考えられるが、Min氏は本作にボクセルベースのものを採用した。

　その理由は何か、またボクセルベースのナビゲーションにすることでもたらされた恩恵は何か。本セッションで明らかにされた「黒い砂漠」におけるオープンワールドのメカニズムの一端を早速みていこう。

「黒い砂漠」ではマルチに活躍したプログラマーKyungin Min氏。現在は「黒い砂漠 MOBILE」のプログラマーをリードしている

　ソロプレイ主体のアクションアドベンチャーにおいて、オープンワールドというシームレスフィールドの概念が確立する前から、MMORPGにおいてフィールドは、ずっとオープンワールドだ。ダンジョンや市街地といった、情報密度の異なる特定のエリアでゾーンニングを行なうゲームは今なお存在するが、「黒い砂漠」を始めとするモダンなMMOゲームでは、これらもすべてシームレスに見せる工夫が行なわれている。

　Min氏は、本作をオープンワールドとするためのプログラム的な手段として、ボクセルベースのフィールド管理を採用した。ここでいうボクセルベースとは、フィールド全体を一定の単位の立方体に区切って管理していることを意味しており、グリッドベースやセルベースという概念と基本的には同義だ。管理単位が、平面や複数の平面レイヤーではなく高さを持つ3次元データであることを強調しているに過ぎない。

　このボクセルひとつひとつには、さらにサブボクセルを収めることができる構造で、ひとつのサブボクセルは、空気、水面、水中、地面、地中、道、壁といった、その空間が何であるかのアトリビュートが付与されている。

【ボクセル化されたフィールド】

　ボクセルベースのフィールド管理がもたらしたメリットは、大きくわけてふたつだろう。ひとつは、メモリ内に留める空間データを限定的なものにすることだ。「黒い砂漠」では、地表面で368.82平方キロにも及ぶ広大なワールド全体を、160x140の22,400グリッドに分割している。ひとつのボクセルが担う空間は128立方メートルであり、1グリッドあたりの最大ボクセル数は255×255の65,025であることから、これを22,400グリッド分用意すると約1,456万ボクセルになる。1ボクセルあたりのデータ量は1バイトであるから、1,456万では1.4GB占有することになる。

　このように、たとえ空間のアトリビュートデータだけだとしても、メモリに常駐しておくことは現実的ではないから、ボクセル単位でのメモリへのロードと破棄を行なっている。極論を言えば、動的オブジェクトが今まさに存在しているボクセルとその周囲の合計27ボクセル以外は、そのオブジェクトの移動を決定するのに必要ないから、27バイトで済む。

　サーバー側では、動的オブジェクトの存在しないボクセルとその周辺のデータ以外は必要なく、クライアント側では、プレーヤー以外の動的オブジェクトのポジションデータはサーバーから取得する前提だとすると、プレーヤーの視界外のボクセルデータは不要だということになるだろう。

【ボクセルデータ構造】

　ボクセルのもうひとつのメリットは、パスファインディングの高速化だ。ゲームジャンルを問わず、3Dゲームでは、アート用のポリゴンデータを簡素化したパスファインディング用のナビゲーションメッシュを用いて異動先を決定する方法もあるが、フィールドサイズや形状によっては、粒度とデータサイズの兼ね合いに、それぞれ一長一短が出てくる。

　通常は、ツールで自動的にリダクションして取得したナビゲーションメッシュを、不都合のある部分や大胆に削減したい部分をある程度手作業で直せば必要十分に思えるが、ボクセルには、ボクセルあたりの粒度とデータ量が均一という特徴があるため、オープンワールドのように広大な空間を取り扱う場合、一定のメリットがあると言える。

　本作のパスファインディングでは、現在いるボクセルから移動先のボクセルまでのリニアな直線上を調べ、遮蔽がなく道中の高低差も1ボクセル以内の場合、通行可能と判断している。このリニアサーチに失敗した際には、A*アルゴリズムにフォールバックする。A*アルゴリズムは、隣接するボクセルを総当たりで調べるアルゴリズムだが、「黒い砂漠」では最終移動先までの距離を調べ、近接する方向に進まない中間移動先を候補から除外する最適化を行なっている。

　こうしてボクセルをたどって調べた移動パスに、オブジェクトの挙動が不自然にならないよう、カーブをブレンドして最終的に移動パスを生成している。また、実際の移動の際には、平面上の中間点に対して、ボクセルデータを参照しながら地形の高低に沿って移動するようにしている。

　ナビゲーションに関する実際の話の流れとしては、Min氏は、本作のA*アルゴリズムをじっくりと説明した後でリニアサーチを持ち出して、リニアサーチ方が10倍から100倍高速だ、としていた。障害物がなく直線的に最短ルートを移動するならそれはそうだろうと思うばかりか、それなら最初からボクセルベースではなく、普通に3Dで移動先にレイキャストを一発したほうが高速なのではないか、とも思わなくない。シリアライズされてインデックス付きの配列に収められているとはいえ、リニアな直線上に位置するボクセルをひとつひとつ条件にあうかどうか検索するループを回すのと、簡素化したナビゲーションメッシュを使うにしても、レイキャストして求めるのと、どちらが処理コストが安いのかは実際のところはわからない。

【重力影響による加速】

　このように、「黒い砂漠」のナビゲーションは非常にオーソドックスなもので、意外と保守的だという印象だ。これは、シンプルで無理のない挙動に動的オブジェクトの移動仕様を限定することで、処理負荷やメモリの使用量を抑えることを優先しているということなのだろう。

　加えて、この仕様の背景には、韓国のMMOゲーム発展の歴史的要因があるようにも思える。クライアント上の表示表現が2Dであろうと3Dであろうと、位置情報の管理を平面的な仮想グリッドの分解能で管理しているゲームが、相当長い期間ポピュラーであったことから、位置情報はグリッド単位で管理するものというお約束が、開発者にもエンドユーザーにも暗黙の了解として存在するように思える。

　そもそも、経験値やアイテムといったプレーヤーキャラクターの成長リソースの源泉としてのみ存在し、所詮やられ役に過ぎないモンスターに、さして高度な振る舞いは必要ないということも前提になっているだろう。

　「黒い砂漠」のボクセルベースの実装は、基本的には処理が軽く、データ量の削減に寄与することは間違いないから、これを否定するものではないが、クライアント側はもとより、サーバー側でもGPGPUの隆盛とともに、ロジック処理を主目的とするサーバー製品にも搭載可能なGPUモジュールが存在することから、今後は韓国産ゲームでも積極的に3D座標系を活用するものが増加していくかもしれない。