過去の独りごち/独りごとはこちら
過去のJavaアプレットはこちら
　

8/25 ネトゲ大好きさ

　うるせー、笑うな！(挨拶

　ネットゲームのいいところというのは、別にゲームをプレイするつもりがなくてもクライアント自体は無料でダウンロードできる事が多いので、入ってる曲データだけは遊ばなくも普通に聞けてしまうし、一部の画像データもひょっとすると見れてしまう点ではないかと思ってしまう昨今です。いや、逆アセやら解析やらする必要も無く、パックされてなければ普通に見れてしまうわけで。

　PSOBBではogg形式でPSOの名曲達が聴けてしまうし、あの光吉氏のボーカル曲も入ってます( ﾟДﾟ)　TalesWeaverではSoundTEMPの一番人気、ESTi氏らによる渾身の作品群が全曲MP3で入ってますね。TalesWeaverはゲームは今ひとつですが(ｺﾞﾒﾝ、曲は超お勧めです。…こう書くとThe Schemeを彷彿させますね。

　ともあれ、プレイへの意欲をそそるという意味合いで、曲データと一部の画像データをわざとパックせずにそのままにしておくというのは案外いいんじゃないかとも思います。

　

旧いランドスケープ

　さてさて、掲示板でも触れたように、またぞろランドスケープエンジンに手入れをしようとして色々と考え込んでいます。　ハイトフィールドによるランドスケープエンジンというのは色々と欠点もあり、

  1. 基本的にX-Z平面およびグリッドに束縛されてしまう
    • 規則的な格子模様がユーザーにバレる
    • 90°の切り立った崖が作れない、などのデザイン上の不便が生じる
    • グリッドの束縛から逃れようとすると例外処理を色々と盛り込む必要が出て面倒くさい
    • 立体交差のあるフィールドの扱いが非常に面倒(単一のランドスケープオブジェクトでは表現不可)
  2. 地形メッシュにテクスチャ座標を持たせると、LOD管理アルゴリズムが非常に限定される
    • ハイトフィールド全体でテクスチャ座標の連続性を前提にしているアルゴリズムが多い(というより、そうしたアルゴリズムしか不勉強な僕は知りません…

　パッと思いつく致命的なの物として、二つ。どれも痛い、痛すぎる。

　↑のスナップショットは、四年前にコソコソと作ったランドスケープエンジンの試作品のサンプル画像でして、テクスチャ座標の割り当てが適当なせいもあって見事に格子状に地形が区切られているのがわかります。また、LOD管理もやってませんというか、テクスチャ座標をグリッド上の各点に自由に割り当てられる仕様なので、頂点を纏めたりできないんです。

　仕方ないのでPVSでも勉強…って適用が違いすぎますね _n○

　さて、どうしたもんか…

　まず、LOD管理の例として、地形を幾つかのブロックに分割して、遠くにあるブロックの頂点を纏める事で減らす、という方法にした場合、先に述べたテクスチャ座標の問題がでてきます。　そうしたアルゴリズムについての解説文書を読んで、テクスチャはどうしているのかと調べたところ、1024x1024サイズのテクスチャを地形全体にベターッと張ってるだけ…とか。256x256セルしか無いランドスケープだとしても、1セルあたり4x4テクセルのボケボケのテクスチャが貼られるわけで、そんなんで本当によかったんだろうかと思ってしまいます。実装時に気を払ってるけど明かしていない(書くのが面倒くさい)事というのはままあるわけで、その部分に僕の知りたい事が盛り込まれているのかもしれませんが _n○

　やはり、少数精鋭戦略ゆえに限られた、1人ないし極めて少数のプログラマを投入せざるを得ず、DirectXの利用そのものに人的コストを割くわけにも行かず、ツールの調達も自前となるためにRADツールとしてのDelphiの恩恵もフル活用してこそ、はじめて困難な現場を乗り切れるのだ！というようなゲリラ的アプリケーション製作を主眼に置いているQuadruple Dでは、データ作成時の利便性を優先し、パフォーマンスはある程度切り捨てた方が良さそうです。となると、LOD管理云々以前に気になるのがQuadtreeを用いた際のグリッドに拘束される点、そして、立体交差のあるマップが扱えないという点が問題となります。

　で、結局何がしたいのか。

　Metasequoiaのようなポリゴンモデラ(*1)で地図を作って、その中を自由に探索したいわけです。　これならエディタを各アプリケーションプログラマの皆さんが血涙を流しながら作る必要も無く、折角作ってくれたみたいだけどエディタとかスクリプトの使い方わかんねーから、お前がマップも作ってよ、と無茶な事を言われもせず、ただただマップデザイナーさんにマップ作成作業を丸投げに出来ます、ブラボォ！

*1 以下、ポリゴンモデラの代表格として、作者のO.Mizuno氏に敬意を払う意味でも、単に「Metasequoia」と表記します

　…いや、ポリゴン職人さんも込みで１人でやってる場合でも、大したメリットはあると思いますよ。うんうん。

　それには、どうすればいいのか？

　まず、地形そのもののLOD管理とかは置いといて、ビューフラスタムと、できればオクルージョンを頼りにカリングを行うことで高速化を図ります。　レゾナンスエイジというMMORPGでは、おそらくビューフラスタムカリングのみで、ゲーム世界を表現するに充分なディテールを表現しつつ、良好なパフォーマンスを叩き出していたという事実があるので、とりあえず欲張らなければ昨今のVGA環境ならば満足なパフォーマンスを期待できます。

 「ResonanceAge Master of Epic」より
( (C)HUDSON SOFT ALL RIGHTS RESERVED.　↑の画像は株式会社ハドソンの著作物です。配布や再掲載等、株式会社ハドソンの著作権を侵害する行為は禁止されています。)
多数の敵NPCおよびPCによる集団戦。深い谷に掛かる橋の上での戦闘ですが、
数十m下の谷底に落下(墜落死)できるだけでなく、
谷底に繋がる通路から歩きに行くことも可能です。

　次に、高速化を「全く」考えなければ表示の上でなんら問題が無いのは、当然だと思います。Metasequoiaで作ったポリゴンデータをTDGVerertexBufferに収まる大きさに切り取って、全部描画すればいいだけですから。しかし、地形との接触判定や、地面の高さの算出などを行おうとすると地形のポリゴン数をｎ、シーンに登場するキャラクタの数をｍとするとＯ(ｎ＊ｍ)の計算量が必要になります。

　そんなのでも1000ポリゴンくらいの地形と5体くらいのキャラだったら問題なく動かせそうな気がしますね、うんうん、欲張らなければ何も考える必要ないですね。

　…流石にそれでは欲張らなさすぎのような気がします。

　というわけで、ボクセル分割を導入する事にします。使用する道具は、やはり、Octet-treeです。　まず、描画及び歩き回る対象となるモデルは既知の大きさなので、Metasequoiaのエクスポータとしてマップ出力ツールを作成した場合は、Octet-treeを構築する際に、一辺何ボクセルに分割するかといった事や、ボクセルの一辺のサイズを指定させてOctet-treeを構築することが可能です。

　ボクセルに放り込む情報としては、そのボクセルは何番のポリゴンと交差するか？というリストです。　これにより、地形とキャラクタとの当たり判定を行うには、

  1. キャラクタと交差するボクセルの集合[V]を求めます。
  2. [V]と交差しているポリゴンの集合[P]と、キャラクタとの当たり判定を行うことが出来ます

　ここで懸念されるのは

  1. キャラクタとボクセルの交差判定を行うのに時間はかからないか
  2. ボクセルという事で、ボクセル数自体が大変な量になり、メモリがパンクしないか
  3. ボクセル当たりの交差するポリゴン数が多数になった場合、パフォーマンスはガタ落ちにならないか
  4. 結局、「地面の高さ」はどうやって求めるのか

　1.についてですが、当たり判定を緩めにすれば特に問題ないと思われます。外接球か、OBBとボクセルとの当たり判定に落とし込めば行けそうです。さらに極端な緩め方としては、キャラクタの外接球と、ボクセルの外接球の当たり判定に落とし込む方法です。それならアセンブラ使ったコードでもすぐかけますね。長細いキャラクタだったりすると大変な事になりそうで、当たってないはずのボクセルが当たったことになる確率は、一辺の長さが他の二辺の長さに対して５倍の直方体だったりすると、 約13倍になります。よって、キャラクタの長細さを指標にして場合分けでもすればよいのかなぁ。可視判定の場合にはビューフラスタムとの当たり判定になるので、球でもそんなに問題は無いんです。ビューフラスタムの縁にあたる部分で誤差が出るだけなので、球で近似したことで体積が増えた分だけ、当たってないのに当たったという判断が下されるわけでもないんです。しかし、自分の含まれるボクセルを求める、というこのケースでは、体積に比例して、ボクセルとの接触範囲は増えます。

　次に、2.ですが、よほど立方体の中にギチギチにポリゴンを詰めない限りは、Octet-treeの各ノードは子ノードを持たない空ノードが多くなると思われます。特にランドスケープではQuad-treeの二倍程度のノード数で収まるのではないかと思います。

　3.については、ボクセルをケチって減らしすぎると、そうなることが懸念されます。ボクセルを増やすとメモリ効率の低下のほか、ボクセルと視界の交差判定の回数・ボクセルとキャラクタの交差判定の回数が増えるわけですが、減らしすぎるとポリゴンとキャラクタの交差判定が増えるので、そのあたりの匙加減が重要になってきます。間違いのない高速化法としては、地形のポリゴン数を減らし、それにあわせてボクセルの間隔も緩くすることです。

　そして、4. この方法では壁にしても床にしても、同じ「ポリゴン」として扱われます。なので、キャラクタの足元(重力の働く方向)に伸びる長い柱を考えて、柱とボクセルの当たり判定を行い、キャラクタの足元より下にあるうち、もっともキャラクタに近いポリゴンから遠いポリゴンに対して、順次柱との交差判定を行います。これにパスした最初のポリゴンが、「地面を構成するポリゴン」となります。

　…3.と4.が引っかかりますね、とても。充分なディテールを確保しようとするとキャラクタごとに複数回の交差判定を行う必要があり、また地面の高さを求めるのも容易ではありません。地面の高さになぜ拘るかと言うと、地上を歩き回るタイプのアプリケーションではキャラクタを着地させるための計算が簡便である必要があるからです。空中を飛びまわるアプリケーションではそれほど神経質にならなくて良いのかもしれませんし、むしろForsakenのように閉じた空間を飛びまわるゲームでは、どの向きを向いたポリゴンも均質に扱われる、今までに述べたモデルは良く馴染むかもしれません。

　結局のところ、何を作りたいかによって、背景を描画するためのエンジンには全く異なるアプローチが必要になる、というごく当たり前の結論に帰着するわけです。

　…つまらん。お前のいう事は実につまらん！

　と、怒っても始まらないので、また別のアプローチを考えて見ます。ターゲットとなるのはランドスケープエンジンで取り扱うような、比較的開かれた場所について、地面の上を歩き回るのがメインのアプリケーションなのは変わらずとして、まず、背景は、ただただ描かれるだけではなく、いくつかの機能を持っているべきです。

  1. 視覚的な情報を伝える機能　…　描画の側面だけ見ると、この機能しか持ってないという事になります
  2. 障害物としての機能　…　キャラクタの移動量を制限する障害物としての機能です
  3. 位置にリンクした情報を伝える機能　…　例えば宝箱が置いてあり、殴れば開ける事が出来る、とか、その地点の床は水面になっており、歩くと水滴が跳ねてバシャバシャ音がする、といった、位置と関連付けられる情報を伝える機能です。

　ここで、レンダリングする方法については、わりとなんとでもなる、というのが正直なところです。実はSXLibには元々カリングの機能が備わっているので、描画に関してはそれに頼れます。もう少し具体的に言うと、SXLibでは、フレームの親子関係を利用して、親フレームは子フレームと、自分のフレームに付いているメッシュを全て包むような外接球を持っています。つまり、親フレームが画面に描かれないならば、子フレームも画面に描かれない事が保障されます。このため、地形を覆う空間全体が一番上のフレームに入ってると考え、その下に配置されるフレームには空間を適宜分割した物を入れます。そして、最下層のフレームには、フレームに割り当てられた部分空間ごとに分割されたポリゴン群を、メッシュとして格納します。

　描画に関して問題がないならば、まずは、障害物としての情報を簡単かつ便利に取り出せるようにする必要があるわけです。

　というわけで、障害物に関しては、メッシュに含まれる頂点情報や、TSXMeshに収まらない超巨大なメッシュを考慮して、Metasequoiaのmqoファイルにも対応しましょう。で、メッシュに含まれる頂点情報から、座標データと面の構成に関する情報だけ抜き出して、壁リストとでも呼ぶべきものを作り、それからBSPツリーを作ることで、現在位置から最寄の壁はどれか？という事を簡単に知ることが出来るようにします。実際のコードでは、

var
  i:Integer; //カウンタ
  hit:Boolean; //壁にあたってる？
begin
  BSPTree:=TBSPTree.Create;
  //壁情報用のメッシュを入れて、BSPツリー構築
  BSPTree.BuildFromMesh( WallMesh );
  //現在位置はWallMeshのモデル座標系で与えるので、場合によっては変換が必要です
  node := TBSPTree.GetHolderNode(現在位置); 

  //壁から1m以内に入っていれば hit = true
  hit:=False;
  for i:=0 to node.Triangles.Count-1 do begin
    if NowPointInPillar(現在位置, node.Triangles[i], 1) then
      hit:=True;
  end;

　こんな感じになる予定です。

　最寄の壁ゲットには、TBSPTree.GetHolderNodeを使って、現在位置がBSPツリー内の、どのノードに入っているかを取得して、ノードに含まれる壁をnode.Trianglesでゲットできるわけです。簡単そうに聞こえてるといいなぁ。

　次に、マップに埋め込まれた付加情報ゲットの方法ですが、これはOctet-treeを利用したほうがいいでしょうね。巨大マップをフレームに分解・格納する過程でフレームに関連付けるという方法がよいのではないかと勝手に思っています。ID埋め込み用のポリゴンには、metasequoia上で決まった名前でスタートするオブジェクト名を持つ、という感じで。

　なぜBSPを使わないかといいますと、BSPではポータルを設けることの出来ない屋外のシーンなどでは役に立たないためです。確かに、最寄の壁を探す事はできるのですが、ビューフラスタムに含まれる範囲はどこからどこまでか、というのは分からないんです。(僕がそういう方法を知らないだけかもしれませんが…)

　実装の方針も決まりましたし、BSPツリーによる衝突検出の実装もこっそり進んだので、この路線で行って見ますか。

Taku Hayase(SANDMAN)

戻る