Project Blocks: 2012

2012/11/28

近況

先週より、ようやく実装中心の生活に戻った所です。『とびだせどうぶつの森』をわずかにプレイしながら。どうぶつの森は、自分でプレイ方針を決めるスタイルのゲームであるため、本当に面白いですね。

DQX については、先の近況報告の時点で利用券購入を止めていましたが、その後、『デモンズソウル』のトロコン、および、『ダークソウル』のトロコンと DLC 攻略に狂っていました。デモンズソウルでは、トロコン以外にも縛りプレイなどを続けていました。
僕は、デモンズソウルやダークソウルの動画と生放送をニコニコ動画で頻繁に視聴しているのですが、観ているとどうしても自分でやりたいという衝動にかられ、その欲望のままに再プレイを始めていました。

最近は、ほぼ毎日のように、夜はダークソウル RTA に挑戦する某氏二人 (落ち着いた口調の方と煽り口調の方) の生放送を視聴しています。正直、僕は、ダークソウルはデモンズソウルと比べると、その面白さがはるかに劣る (比較にすらならない) と感じていますが、RTA の視聴となると、タイムを縮めるための実況者の試行錯誤を垣間見ることができ、非常に面白いです。

実装の近況ですが、色々と悩んだ挙句、今は Minecraft クローンに近いものを実装しています。

僕は、Minecraft のようなゲームを作りたいわけではないですが (そもそもゲームを作りたいわけでもないですが)、ブロックで表現される世界のエディットを考えると、それは Minecraft でブロックを生成および消滅させることと同じであり、ならば Minecraft のような設計がベストであろうと考えるに至りました。

今月中にデータ定義と描画までは終わらせたかったのですが、エディタを考慮したオブジェクトの扱いや、Web 上でのデータの公開を同時に検討していると、一筋縄ではいかず、年内に終われば良いかなと考えている所です。できれば、数年前に上げた動画のように、物理エンジンへの統合とエフェクトの実装までは行いたいですが、あわてず進めていこうと思っています。

2012/08/22

DQX 廃人中から軌道修正中

DQX を、メインにエルフ♂、セカンドにドワーフ♀でプレイしています。

昨日の時点で、メインが僧侶 40、木工 30、セカンドが僧侶 24、ランプ錬金 24 です。シナリオは先輩と 2 人で進行し、人の姿を取り戻した所で長らく止まっています。

発売日から 3 日後位から木工を始め、僧侶上げよりも木工でバザー販売している方が楽しいと感じ、延々と木工をやり続けていました。僧侶レベルは、出品した物が捌けるのを待つ間、敵を適当に狩っていたら上がっていたという感じです。

それで楽しんでいたのに、まさかの 30 キャップで一気に白けました。そこで、次の楽しみを探し、木工での稼ぎの一部を資金として、セカンドでランプ錬金を地味に上げていた所です。

ですが、総じて飽きてきました。徐々にプログラミングのペースを取り戻し、DQX からフェードアウトしようと思います。

2012/08/01

Hydraulic erosion 調査

Hydraulic erosion について色々と調べていました・・・と言うか、幾つかの実装を終えました。その内の 1 つが、F.Kenton Musgrave、Craig E. Kolb、Robert S. Mace による『The Synthesis and Rendering of Eroded Fractal Terrains』で述べられているアルゴリズムによるものです。

で、そのうち調べたことを忘れ、その時に再度英語で論文を読み返すのも疲れると考え、備忘のために自分の解釈でまとめてみることにしました。なお、図解はしませんし、専門家ではないので言い回しの問題はご容赦ください。また、原文の訳を載せているわけではないので注意してください。

Musgrave らの論文の PDF は以下から得られますが・・・これは大丈夫なんでしょうか？

ebookbrowse.com: The Synthesis and Rendering of Eroded Fractal Terrains pdf

日本語で hydraulic erosion を何と言えば良いのか分かりませんが、大雑把には、

雨が降り、
雨により土が削られて土砂が生まれ、
土砂が水に混じり、
水の流れと共に土砂が移動し、
時に土砂が堆積する、

という現象のシミュレートと言えば良いでしょうか。なお、水の流れと言っても、河川のような複雑な水の流れを考えるのではありません。

アルゴリズム

※原文は時間 $t$ から $t + 1$ への変化で説明していますが、なんだか式が見づらくなるので表記を省き、数式をプログラミング言語としての式へ変えています。

Height map 上のセルについて、$a$ (altitude: 地形の高さ)、$w$ (water: 雨による水の量)、$s$ (sediment: 水に混じっている土砂の量) を考えます。

このアルゴリズムの上では、雨による $w$ の定め方については触れません。シンプルな雨の実装としては、各ループの最初に一律で $w$ へ値を加える方法がありますし、少しランダムな状態としたければノイズ関数で値を加えるなどの方法もあります。いずれにせよ、何らかの形で $w$ を与える必要はあります。

なお、シミュレーションの最初のループでは $s = 0$ であり、処理の過程において水が土を削ることで土砂が生まれる点に注意が必要です (最初から土砂があると考えてアルゴリズムを見ると混乱します)。
また、実装では height map 上の全セルについて水の移動を処理する必要がありますが、ここではセル $v$ について、隣接するセル $u$ への移動を説明している点に注意が必要です。

セル $v$ から $u$ へ流れ出る水の量 $\Delta w$ は次式となります。

\[ \Delta w = min(w_{v}, (w_{v} + a_{v}) - (w_{u} + a_{u})) \]

まず、$\Delta w \leq 0$ は、「$v$ には水がない」あるいは「$v$ から $u$ へは水は流れ出ることができない」ことを表しているため、水の移動を考えず、土砂の堆積のみを考えます。ここで、堆積の割合を定数 $K_{d}$ (deposition constant) で定義し、堆積する量を $K_{d} s_{v}$ として堆積を処理します。

\begin{eqnarray} a_{v} &=& a_{v} + K_{d} s_{v} \\ s_{v} &=& s_{v} - K_{d} s_{v} = (1 - K_{d}) s_{v} \end{eqnarray}

一方、$0 < \Delta w$ では水が移動できるため、土砂の移動についても考えます。まず、水の移動は単純に次式で表せます。

\begin{eqnarray} w_{v} &=& w_{v} - \Delta w \\ w_{u} &=& w_{u} + \Delta w \end{eqnarray}

次に、水と共に移動する土砂の量ですが、水が全ての土砂を運べるとは限らず、その能力には限界があります。そこで、水が運べる土砂の割合を定数 $K_{c}$ (sediment capacity constant) で定義し、$\Delta w$ について共に移動する土砂の量 $c$ (sediment capacity) を次式で定めます。

\[ c = K_{c} \Delta w \]

ここで、$c$ と $s_{v}$ の比較で処理が分岐します。まず、$s_{v} \geq c$ では $c$ 分を移動させるだけの $s_{v}$ があるため、そのまま移動させます。そして、移動後の残りの分 $s_{v} - c$ について堆積を考えます。

\begin{eqnarray} s_{u} &=& s_{u} + c \\ a_{v} &=& a_{v} + K_{d} (s_{v} - c) \\ s_{v} &=& s_{v} - c - K_{d}(s_{v} - c) = (1 - K_{d})(s_{v} - c) \end{eqnarray}

一方、$s_{v} < c$ では、$c$ 分の移動には $s_{v}$ が不足していますが、この状態は、「更に土が水に混じる余地のある状態」と考えることができるため、土を削って土砂を生み出すこととします。

なお、シミュレーションの最初の段階では $s = 0$ であり、必ずこの処理に入ります。そして、この処理で土砂が生まれ、$s$ が増加するということになります。

ここで、土砂として水に混じることのできる量に対して、実際に土砂として削る割合を定数 $K_{s}$ (soil softness constant) で定義し、$K_{s} (c - s_{v})$ だけ地形を削り新たな土砂とし、次式で水と土砂の移動と堆積を考えます。

\begin{eqnarray} s_{u} &=& s_{u} + s_{v} + K_{s} (c - s_{v}) \\ a_{v} &=& a_{v} - K_{s} (c - s_{v}) \\ s_{v} &=& 0 \end{eqnarray}

・・・と、以上のようなアルゴリズムを考えるそうです。そして、ここまでの処理を $n$ 回繰り返してシミュレーションとします。

MathJax 導入

数式を書くために、試しに MathJax を導入しました。

$ e^{i\pi}=-1 \tag{1} $
下記サイトの手順に従って導入しました。

Ichiro Maruta Homepage: BloggerでMathJaxを使ってTeXっぽく数式を入れる方法

TeX を使う日が再び訪れるとは・・・流石に構文を思い出せません。

2012/07/30

Terrain Texturing

あまり興味がなかったので、地形にテクスチャを貼ることを無視していたのですが、何だか貼りたくなる発作が起こり、貼りました。

上図では MinFilter = Anisotropic、MaxAnisotropy = 4 としています。MaxAnisotropy = 16 でもそれなりに動いたのですが、描画する範囲が増える局面では 60fps を維持できなくなってしまいました・・・。この辺りを考えると、やはりまだまだ改善すべき点があるのだろうと感じます。

この実装では、下記サイトのデモコードからテクスチャを拝借しています。

dhpoware: XNA 4.0 Terrain Texturing Demo

HLSL も上記サイトとほぼ同じにしていますが、かなりやっつけ仕事として既存の実装へマージした状態です。
仕組は、4 枚の diffuse map を渡し、高さから定まる割合を元に各 diffuse map から得られる色への重み付けを決定してブレンドするという、数多のサイトで紹介されているシンプルな実装です。

ソースコードは以下のタグで取得できます (プロジェクト構成については「XNA Infinite Terrain 改」を参照してください)。

GitHub: TestXna (tag 20120730-2)

やはり、テクスチャを貼ると、それだけで質が上がったような気分になれますね。むしろ、「最初からそうしろよ！」という気がしないでもありません。

XNA Infinite Terrain 改

2012/07/27

Midpoint Displacement による地形生成

Midpoint Displacement による地形生成を実装していました。

Wikipedia (en): Midpoint displacement algorithm - Diamond-square algorithm

日本語では「中点変位法」と呼ぶようです。なお、Diamond-square algorithm については実装していません。

アルゴリズムについては、下記サイトの説明が分かりやすいと思います。

Generating Random Fractal Terrain: Midpoint Displacement in One Dimension
fractalterraingeneration: Midpoint Displacement

極めて簡単にアルゴリズムを説明すると、最初に height map の 4 隅に値を与え、2 点間の中点に対してそれら平均値 + 誤差 (乱数) を与えて決定し、この中点の決定を必要な所まで繰り返すというものです。

検索すると数多の公開コードがありましたが、サイト fractalterraingeneration で公開されているコードが最も綺麗に見えたので、これを元に実装しています。

なお、僕のコードでは、実行中に複数の height map を生成して並べたいため、シードを与えた後、(x, y) に対して一意に値が定まるような擬似乱数を用いています (ノイズの利用で行なっている事と同じ)。
見かけた公開コードの全ては (探せば別の物もあるでしょうが)、基点となる 4 隅の高さや中点の変位量を定める際に、C# ならば Random.NextDouble() に代表されるような擬似乱数生成器の値をそのまま利用していましたが、この方法では height map 間の境界上での高さを一致させることは困難です。

また、サイト fractalterraingeneration のコードでは、変位の際に与える誤差の重み付けが大雑把なため、サイト Generating Random Fractal Terrain の説明にあるようなパラメータ H による制御としています。なお、他のサイトでは、変位量の計算メソッドをオーバライド可にし、柔軟に実装を変更できるようにしているものもありました。

下図は、Midpoint displacement で height map を生成し、高度による色付けを行ってみた結果です。

下図は、「XNA Infinite Terrain アップ」で紹介したコードの Midpoint displacement 版を実行した結果です。

まぁ・・・ノイズ計算と重ね合わせを実行することに比べると、極めて高速です。見た目も十分に地形であり、今まで僕がノイズで作っていた地形よりも地形らしく見えるような気がしないでもありません。

ただし、多様な地形を表現できるかどうかについては、Midpoint displacement では厳しいであろうと考えています (特定の座標にある値を即座に得ることはできない仕組みであるため)。

また別の問題として、僕には今のところ解決の術が見つからないのですが、中点を選んでの変位を繰り返す処理ゆえに、綺麗に中点を選択できなくなる height map サイズを用いる場合、height map 同士の特定の位置にある高さを一致させることが難しくなります。
地形をポリゴンで描画する際、境界上にある頂点の法線を地形同士で一致させるために、僕は通常用いられる height map よりも 1 ピクセル分だけ余分に確保して法線の算出に用いていたのですが、Midpoint displacement ではこれを行うことができません。実行中の height map 生成でなければ、隣接する height map から情報を拝借して済む問題ではあるのですが。
このため、地形描画コードでは、height map 同士が隣接する境界での法線が不正となり、繋ぎ目が見える状態です。

下記にソースコードを置きました。

GitHub: TestXna (tag 20120727)

上記 Git プロジェクトのうち、下記の XNA プロジェクトが対象です (全てをダウンロードしなければコンパイルできません)。

MidpointDisplacementDemo: デモアプリケーションのソリューション
DemoFramework: 基礎的なクラスを含むライブラリ
Framework.Terrain: 地形描画の基礎となるクラスを含むライブラリ
Framework.Terrain.CDLOD: CDLOD のためのライブラリ
Framework.Landscape: 動的地形生成管理のためのライブラリ

また、MidpointDisplacementDemo ソリューションは、以下の 2 つのスタートアッププロジェクトを持ちます。

MidpointDisplacementDemo: 単に色付けしてテクスチャとして表示するデモ
MDTerrainDemo: ポリゴンで実際に描画するデモ

なお、Midpoint displacement の実装そのものだけならば、以下のファイルとなります。

GitHub: MidpointDisplacement.cs

2012/07/22

ボロノイ分割による地形生成

複数の height map を並べる処理をしている間、ボロノイ分割による地形生成も実装していました。

Wikipedia: ボロノイ図

ソースコードは、前回の XNA Infinite Terrain のコードと同じですが、修正を加えた状態が以下となります。

GitHub: TestXna / TiledTerrainDemo (tag 20120722)
(TiledTerrainDemo.Noise.Voronoi クラス周辺)

実行例は、以下のようになります。

距離メソッド = Squred, 選択方法 = Distance0, Frequency = 1

ロジック

簡単に説明すると次のようになります (実際には 3 次元で値を生成しますが 2 次元で考えます)。

まず、float 値の (x, y) について周辺のセル (int) を特定し、それらセルに含まれる母点を乱数で定めます (乱数といっても同じセルなら必ず同じ母点)。
続いて、周辺の各セルについて (x, y) から母点までの距離を測定し、最も近い母点を選択します。
最後に、選択された最も近い母点について乱数を生成し、これを (x, y) の高さの値とします。
結果として、ある母点に近いところにある (x, y) の高さが母点の高さと同一となります。

なお、Wikipedia では分割された領域に色を設定している説明ですが、ここでは地形生成に用いるため、乱数で生成した高さを設定しています。

参考にしたソースコードは以下の通りです。

libnoise: http://libnoise.sourceforge.net/
(module にある voronoi.h/voronoi.cpp)
Blender: http://www.blender.org/
(blenlib にある BLI_noise.h/noise.c)

各種パラメータによる変化を 2D テクスチャで見たい場合には、以下のサイトが分かりやすいです (ソースコードも公開していますが、Blender とほぼ同一です)。

The Nugget Mines: Voronoi Noise

距離メソッド

僕のコードの基本形は libnoise に類似していますが、libnoise の Voronoi クラスでは、Blender にあるような距離の測定方法の変更が行えません (ユークリッド距離^2 で固定)。僕のコードでは Blender にならい、複数の距離メソッドを用意し、delegate で変更できるようにしています。
実装してある距離メソッドは以下の通りです。

Squared: ユークリッド距離^2 (XNA での Vector3.DistanceSquared() に相当)
Real: ユークリッド距離 (XNA での Vector3.Distance() に相当)
Manhattan: マンハッタン距離
Chebychev: チェビシェフ距離
Minkowski: ミンコフスキー距離

各距離の意味は、以下がまとめられていて分かりやすいと思います。

CatTail Wiki: 類似度と距離

なお、上記は統計解析で用いられる SAS というアプリケーションのための Wiki です (関係する人で知らない人はいないのでは？)。実用経験はないですが、僕も訳があり多少かじっていたりします。

以下、距離メソッドを変更した場合での地形の雰囲気を画像で並べます。後述する母点選択方法は Distance0、Frequency は 1 で固定。また、Real は除外。

Squred

Manhattan

Chebychev

Minkowski (p = 0.5)

Minkowski (p = 4)

以上、違いを認識しづらい画像になってしまいましたが、Squared を基本に比較すると、Manhattan や Chebychev はより矩形に近い分割に見える気がします。Minkowski だと領域がより複雑な形状となるのでしょうか。

母点選択方法

libnoise の Voronoi クラスでは、Blender にあるような母点の選択方法の変更が行えません (常に最も近い母点を選択する)。僕のコードでは Blender にならい、母点の選択方法を変更できるようにしています。Blender では距離の選択方法と呼ぶのが正しいですが、僕のコードでは母点の選択方法です。

実装してある母点選択方法は以下の通りです。

Distance0: 最も近い母点を選択
Distance1: 2 番目に近い母点を選択
Distance2: 3 番目に近い母点を選択
Distance3: 4 番目に近い母点を選択
Difference21: Distance1 と Distance2 が示す各母点の中間点を母点に選択
Difference32: Distance2 と Distance3 が示す各母点の中間点を母点に選択
Crackle: よく分からずに実装

Difference21 と Difference32 については、Blender では距離の算出のみで、そこから高さを乱数で算出するようなことをしていないため、自分で勝手に中間点を選択するようにアレンジしました。

以下、母点選択方法を変更した場合での地形の雰囲気を画像で並べます。距離メソッドは Squared、後述する Frequency は 1 で固定。

Distance0

Distance1

Distance2

Disntance3

Difference21

Difference32

Crackle

より遠い母点を選ぶことで、より粗い分割が行われるように見えます。Difference21、Difference32 については、勝手なアレンジをしたので何とも言えません。Crackle は理解していないので更に何とも言えません。

Frequency による調整

Voronoi クラスの Frequency プロパティは、Voronoi 分割を行うまえに、指定した (x, y, z) に対して乗算されます。上手く表現する方法が分からないのですが、名前の通り、生成する値の幅を調整する役目を果たします・・・と言えば良いのでしょうか・・・。

以下、Frequency を変更した場合での地形の雰囲気を画像で並べます。距離メソッドは Squared、母点選択方法は Distance0 で固定。

Frequency = 1

Frequency = 4

Frequency 値を大きくすると、より狭い範囲で分割を行うことになります。

距離を高さに足す

Voronoi クラスの DistanceEnabled プロパティを true にすると、算出した高さに対し、その算出の元となった距離を足します。
つまり、母点に近い位置では算出した高さのままであり、母点から遠のく程に (領域の境界へ近づく程に) 高さが上がる状態となります。

以下、DistanceEnabled を変更した場合での地形の雰囲気を画像で並べます。距離メソッドは Squred、母点選択方法は Distance0、Frequency は 1 で固定。

DistanceEnabled = false

DistanceEnabled = true

距離を高さに足すことで、クレータのような部分が作られます。

2012/07/21

XNA Infinite Terrain アップ

実行時地形生成の実装を一段落させました。

ソースコードは以下にあります。

~~GitHub:~~ ~~TestXna / TiledTerrainDemo (tag 20120721)~~

※ソースコードを大幅に変更しました。下記ページを参照してください。

Blocks Project: XNA Infinite Terrain 改

ソースコードには、複数のノイズ生成および加工方法を組み合わせて height map を生成するためのテストコードも色々と含まれており、とても見辛い状態であると思いますが、もう面倒なのでそのままにしています。

動画での設定は以下の通りです。

解像度: 1280x720
60fps (録画 30fps)
各 height map: 1025x1025
Far plane distance: 300000.0f
フォグ範囲: 20000.0f - 30000.0f
地形ロードに使用するスレッド数: 4
地形生成方法: Improved Perlin noise + sum fractal (octave 7)

遠方の描画がちらつきますが、実際にはより手前でフォグをかけるのだと思います。しかし、あまり手前でフォグをかけてしまうと、遠方で地形が動的に生成される様を見せることができなくなるため、ちらつきが多いまま録画しています。恐らく、通常ならば far plane distance を 300000.0f
に設定することはないであろうと思います。

以下、ひとまず簡単な解説です。もう少し詳しく説明しようと思ってはいたのですが、今のところ非常に実装で疲れてしまい、「興味がある人はソースコード見ればいいじゃん！そもそも興味ある人いないかもしれないし！」へ傾きつつあります。

地形の動的ロードの枠組み

本題となる地形の動的ロードですが、やっていることは極めて簡単なものです。
まず、空間をロードの単位とするための仮想的な区画で区切ります。そして、カメラ位置からどの程度の距離まで近づいたらロードするか、および、どの程度の距離まで離れたらアンロードするかを定め、その距離に含まれる区画の位置を算出します。こうして、ロード範囲にある区画について、それが未ロードならばロードします。また、アンロード範囲から外れた区画について、ロード済ならばアンロードします。

基本はこれだけです。より効率の良い方法がありそうですが、他には特に思いつきませんでした。

Improved Perlin noise の採用

先日、Perlin noise が遅いため Simplex noise を実装しましたが (Simplex noise 実装と計測)、この動画では Improved Perlin noise で height map を生成させました。これは、Simplex noise は確かに処理が高速なものの、生成されるノイズがあまり滑らかではない印象を受けたからです。

原点から大きく離れたカメラ位置での問題

数日、カメラ位置が原点から極めて離れた場合 (例えば x = 100000.0f くらい) に、根本的に描画がちらつく問題に手こずっていました。
どうも、カメラ位置の値があまり大きくなると、頂点を View * Projection で変換させた時に精度が大きく落ちるようで、最終的には各地形の位置を原点とした空間を考え、そこからの相対位置で演算することで解決しました。

基本的に、今回の CDLOD に関わるコードでは、地形の位置を原点とした地形空間で頂点を計算するように統一して修正しています。

しかしながら、カメラ～地形間の距離が離れすぎると結局は同じ問題が発生し、遠方にある地形の描画がちらつきます。これを直そうと思ったのですが、そう簡単に解決できる問題でもないと考え始め、放置することにしました。

地形間の繋ぎ目の問題

地形間の繋ぎ目の問題ですが、これは height map 上でのデータ表現と頂点データ表現とのギャップが原因です。

例えば、height map の右端の値は右端の頂点の高さになりますが、その隣の height map の左端は左端の頂点の高さになります。つまり、height map から生成される頂点データを並べる際には、右端の値は、その右に並ぶ height map の左端の値と一致していなければならないということです。これは、上下の並びについても言えることです。

僕のコードではノイズから height map を生成しているので、値の出力範囲を調整することで、上下左右が隣接する height map と重なるようにしています。

ただし、それだけでは、動的な height map 生成ではまだ問題が発生します。ある頂点の法線情報は隣接する頂点の高さから算出しますが、上下左右の境界上では隣接する頂点の一部を得ることができないため法線を正しく計算できず、ライティングを行うと陰影による繋ぎ目が発生します。

僕のコードでは、height map のサイズを上下左右を更に 1 つ分増やし、隣接する height map と１つ分だけ重なるように値を生成し、境界上にある法線の算出においても必ず隣接する頂点を得られるようにしています。
~~しかしながら、完全に繋ぎ目を消すことはできていません。CDLOD の設定次第では、非常にわずかな繋ぎ目が表れる場合があります。~~

2012/07/19

Simplex Noise 実装と計測

Perlin noise が遅いので Simplex noise を C# へ移植していました。

Wikipedia: Simplex noise

Stefan Gustavson による説明 (ソースコード含む): http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf

Stefan Gustavson による改善コード (C/C++): http://staffwww.itn.liu.se/~stegu/aqsis/aqsis-newnoise/

・・・アルゴリズムを理解せずに移植だけしました。もう動けばいいや、と。

とりあえず、Perlin noise、Improved Perlin noise、Simplex noise を大雑把に計測をしました。対等な比較とは言えないのですが、僕の適当な計測コードにおいては、Simplex noise は Improved Perlin noise の 2 倍ほど高速でした。

一応、以下にそれらソースコードを置いてあります。

Perlin noise、Improved Perlin noise、Simplex noise、および、計測コード:
https://github.com/willcraftia/TestXna/tree/master/NoiseMeasuring

なお、僕のコードでは、C++ 改善コードをベースに少し変更を加えました。元ネタのコードには、(C++ では) 「(int)Math.floor() よりも、ここで利用している式の方が高速である」とのコメントが記載されているのですが、C# では「(int)Math.Floor()」の方がはるかに高速だったので直しています。
リリースビルドにしてませんでした・・・。リリースビルドでは「(int) Math.Floor()」を使わない方がはるかに高速です。

また、僕は Perlin noise、Improved Perlin noise の実装において、permutation テーブルを擬似乱数から実行時に生成しているので、Simplex noise の実装もこれに合わせて修正しています。

後は、gradient の計算式の出力を Improved Perlin noise のベクトルの方向と同じにしたくらいです (かなりどうでも良い)。

2012/07/17

google-code-prettify 動作テスト

ソースコードを載せる可能性も考えて、HTML に google-code-prettify を載せてみました。

google-code-prettify

以下、確認コード。

using System;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

public class GameClass : Game
{
    GraphicsDeviceManager graphics;

    pulic GameClass()
    {
        graphics = new GraphicsDeviceManager(this);
    }
}

直接 HTML を記述する必要があるので面倒ですね・・・。

XNA Infinite Terran (Alpha)

想像したよりも簡単に動的な height map ロード/アンロードの仕組みが作れたので、alpha 版としてニコ動へアップしました。

なお、タイトルでは Infinite と書いていますが、実際には座標を示す float の限界に到達したら落ちると思います。また、Height map をタイル状に繋げてロード/アンロードを繰り返す仕組みを考える場合、無限を想定しなければならず、そこに height map の動的生成を組み合わせると、「結果的に無限のような状態となった」と言うところです。

今回、以下のソフトを用いて、ようやくまともな画質でアップロードできました。

アマレココ: アマレコTV公式ホームページ
つんでれんこ: つんでれんこのお部屋

アプリケーションを画面サイズ 1280x720、60fps で実行し、アマレココで 30fps で録画し、つんでれんこへ Drag & Drop するだけという簡単なお仕事でした。今までの苦労は何だったのか。

現時点では枠組みが完成しただけであり、数多のバグが存在し、また、GC に対する考慮を無視しています (ゆえに、Alpha)。それらの修正を終えたら正式版を公開し、同時にロジックの解説を行う予定です。今回のロジックには元ネタが無いため、わりと真面目に解説する・・・気持ちでいます。

簡単な説明を書いておくと、視点からの距離に応じて必要とする height map を決定し、必要となった時点で Thread を用いて Perlin noise により height map を生成し、後は CDLOD でデータ構造作成と描画を行なっているだけです。

動画では 1025x1025 の height map を生成しています。Perlin noise による height map 生成はかなりの処理負荷を招き、今回のような視点の高速移動を行う場合、Thread で生成処理を並列化しても描画までに追いつかない状態です。
ただし、現段階では、簡易な height map 作成手段として Perlin noise を採用しているに過ぎず、後々は事前準備した height map テクスチャを基本として実装を進めると思います。

2012/07/16

DQX β 終了

CDLOD の実装が落ち着き、DQX を楽しもうと思ったら今日が最終日でした。

β の感想ですが、極めて王道な MMORPG であるがゆえに DQ らしく、一方で、王道ゆえに目新しさがなく、MMORPG の良さも悪い点もそのまま引き継いでいるという印象です。MMORPG をプレイした事がある人には、「そのプレイした MMORPG と同じです」と答えます。しかし、初めて MMORPG に触れる人には、DQ らしく簡易なシステムとなっているため、楽しめるゲームであると感じます。

β の段階では、あまり目立つバグはありません。ですが、製品版でプレイヤが集中した場合にどうなるかは未知な気がします。β では、サーバの限界に到達する程の過密人口になっているとは思えません。

大きな不満としては、DQ ならば、MMORPG に共通して見られる時間的な煩わしさを改善し、より万人が受け入れられるよう再構築してくれると期待していたのですが、β の範囲においては、どうやらそうではないようです。

また、願わくば、ボイスチャットにして欲しかったですかね・・・。テキストチャットは声の調子などを伝えられないことから意思の伝達に十分ではなく、テキストの解釈のほとんどが受け手に委ねられます。これが僕はあまり好きではありません。

とは言え、製品版は買います。友達を下手に誘ってしまい、「予約したよ！」と言われたら引くに引けないという事情がありますが、それなりに楽しめるのではないかと感じているためでもあります。

何にせよ、Wii で MMORPG、どのくらい売れるんですかね？
MMORPG はあまり人へ薦められるゲーム形態であるとは思えません。少なくとも、まっとうな社会人には MMORPG は不適切です。しかしながら、DQ を求める人の多くは既に社会人となったプレイヤであると考えられます。

などと理屈をこねても、ゲームは楽しもうとする意思が無ければ楽しめないので、買ったら楽しむために行動すると思います。恐らく 1 ヶ月程は。

2012/07/15

XNA CDLOD Terrain

XNA へ移植していた Continuous Distance-Dependent Level of Detail (CDLOD) の実装を概ね終えました。

CDLOD: Filip Strugar: Oh no, another terrain rendering paper!

デモコードでは、Perlin noise を用いて実行時に height map を生成し、CDLOD を用いて地形の描画を行なっています。

ソースコード: https://github.com/willcraftia/TestXna/tree/master/TerrainDemo

一応、ざっくりと CDLOD を説明しておきます (深く説明する知識がないのでざっくり)。

CDLOD では、まず quadtree を用いて height map が表す地形情報を level of dedail (LOD) のレベルごとにノードへ分割しておきます。そして、視点からどの程度の距離でどの LOD レベルを用いるかを示すリストを用意しておき、このリストに基いて quadtree から表示対象とするノードを選択します。なお、各ノードは描画で必要とする頂点情報は持たず、対応する height map 上での位置と height map から得られる高さを持つのみです。

続いて、1 つの矩形メッシュを用意しておき、GPU へ矩形メッシュとノードの情報を渡し、vertex shader で適切な座標へ変換しながら描画します。この時、ある LOD レベルのノードで描画するメッシュが、次に粗い LOD レベルのノードで描画するメッシュの形状に近づくように、視点からノードまでの距離に応じて頂点位置をモーフィングさせながら描画します。これにより、LOD の違いによる繋ぎ目や t-junction の発生がなくなるという仕組みです。

こんな感じでしょうか？なお、地形の分割とモーフィングの説明としては、以下のサイトが分かりやすい気がします。

Mistal Research: GPU Terrain Subdivision and Tessellation

僕のコードは、そのままの移植ではなく、幾つかの改変が加えられています。
一番大きな点には、HW インスタンシングの利用、および、そのためのノード選択ロジックの変更があります (オリジナルコードは各ノードごとに DrawIndexedPrimitives() を呼び出す)。ただし、改善と呼べるかどうかは分かりません。

まず、オリジナルコードでは、単一の矩形メッシュを用意するのみであるものの、描画時には矩形メッシュの中で必要とする区画のみを描画しています。これには、必要十分な細かい LOD のノードを選択するというロジックが関与しています。

あるノードには 4 区画が存在し、各区画には対応する子ノード (より細かい LOD のノード) がぶら下がります。ノード選択において、全区画で子ノードが選択されなければ、そのノードをそのまま選択することになりますが、一部の区画では子ノードが選択される (より細かい LOD が選択される) という状況も生まれます。

ここで、親ノードを N、その子ノードを n0、n1、n2、n3 とし、ノード選択において n0、n1 が選択されるとします。オリジナルでは、N、n0、n1 を選択状態にし、n0 と n1 はそのまま矩形メッシュを描画しますが、N は n0 と n1 の区画を含むため、n0 と n1 に重なる区画を描画しないようにインデックスデータを調整してから矩形メッシュを描画します。

一方、僕のコードでは、HW インスタンシングを行うために、n0、n1 が選択されたら n2、n3 も強制的に選択し、N を破棄します。つまり、全ノードを同一メッシュで描画するために、N が矩形ではなくなる状態を回避しています。しかし、これは、定義した LOD レベルの範囲を超えたノード選択を行なっている (選択されるノード数がオリジナルよりも増える) ことにもなります。

細かい変更としては、Draw() 呼び出しごとに渡さずに済む Effect パラメータを事前に設定したり、選択する LOD の範囲を定めるロジックをわずかに簡易な物にしたりなどしています。

ただし、改善すべき点は、簡単に気付く所でもまだまだ残されています。僕のコードでは (オリジナルもそうですが)、view frustum とノードの AABB との単純な交差判定で frustum calling を行なっています。これには、事前に球同士の交差判定で除外するなどの余地があります。また、CDLOD で期待する描画を維持するには、かなり遠方まで距離と LOD レベルの関係を定義をしておく必要があり、僕のコードではそれをそのまま用いているために、視覚範囲を越えた部分のノードまで判定してしまいます。

一応、動画を YouTube とニコニコ動画へ上げてあります。ニコ動版は、どうもアップロード時に画質が劣化してしまったようで (もうニコ動は投稿が面倒すぎて直す気が起きません)、YouTube 版を見た方が良い気がします。

実行画面におけるワイヤフレームの立方体は、ノードの AABB を表しています。その色は LOD レベルを表しており、レベル %= 4 で 4 階調にしたものです。ある地点に近づくにつれ、より大きな AABB がより小さな AABB に置き換えられていく (LOD レベルが切り替わる) 様子を見ることができると思います。
また、ワイヤフレーム表示時には、モーフィングしていく様子を見ることができると思います (解像度の問題で若干見辛いですが・・・)。

Height map は、実行時に Perlin noise で作成しています。動画でのサイズは 4096x4096 ですが、実際に使う場合には、(512 + 1)x(512 + 1) や (1024 + 1)x(1024 + 1) などにするかと思います。なお、CDLOD では height map をテクスチャとしてシェーダへ渡す必要があり、このテクスチャは SurfaceFormat.Single となるわけですが、 XNA HiDef プロファイルで扱える最大サイズが 4096x4096 であるらしく、その限界で heigh map を作成してみたという所です。

地形描画は、その高度情報に応じた色分けとブレンドで済ませています。リアルな地形を望むならばテクスチャをどのように貼るかを考えなければならない所ですが、今のところ僕には興味が無いため無視しています。

この後は、複数の height map を用いて、実行時にロード/アンロードを繰り返しながら、より大きな地形を描画するためのコードを書こうと思っています。

2012/07/12

CDLOD 実装中

Continuous Distance-Dependent Level of Detail for Rendering Heightmaps (CDLOD) を XNA で実装してます。

CDLOD: MAD VERTEX'S - Oh no, another terrain rendering paper!

オリジナルコードは C++ (DirectX) なので、これを XNA 環境へアレンジを加えながら置き換えているという感じです。

一応、既に XNA 実装を公開している人がいます。

davidlively.com - XNA CDLOD Example

ここで公開されているコードも、単純な移植ではなく、多くのアレンジが加えられています (アレンジし過ぎで原型を留めていない・・・)。

そのまま丸パクリしようと思ったのですが、僕には LOD 判定処理に誤りがあるように見える (高さによる判定しか有効になっていないように見える) こと、および、至る所でオブジェクトを new している (恐らくサンプルとしてコードの見易さに重点が置かれている) ことから、参考程度にとどめることにしました。
ただし、HW インスタンシングを用いるアレンジについては、欠点もありますが、そのアイデアを僕も採用することにしました。

現時点では、単にワイヤフレームで LOD レベルに応じた色分け表示を行い、基本動作を確認できるところまで実装が終わっています。もう少し、視覚的に地形であるとみなせるように実装を追加したら、いったん動画化して公開しようかと思います。

2012/07/05

DQX βテスト参加

先輩が DQX の β テストに参加していて、先輩からの友達紹介という事で、僕も今日から β テストに参加しました。数年ぶりの MMORPG 、数ヶ月ぶりの Wii 起動。

2012/07/01

Perlin Noise と Height Map

Perlin noise および height map 実装が一段落しました。

上の画像は、Perlin noise を元に 257x257 の height map を 5x5 個生成し、各 height map に対して高度による色付けとライティング (バグっている気がしないでもない) を行って作成したテクスチャを並べたものです。例えば、右下隅の height map をテクスチャ単体で見た場合は、以下の画像となります。

タイル状に繋がる height map は、ノイズを生成する関数 (重ね合わせも含む) が、入力に対して一意のスカラー値を返すことを利用し、各 height map ごとに利用する入力の範囲を区切ることで作成できます。このロジックは libnoise を参考に実装したので、仕組みについては Tutorial 3: Generating and rendering a terrain height map の "Tiling terrain height maps" を読むと早いかと思います。

ソースコードは以下に置いてあります。

GitHub: TestXna / PerlinNoiseDemo

シンプルな fBm、少し複雑な fBm、その他色々なコードをネットで拾えたので、それらも実装して効果を試していましたが、どうにも複数のパラメータをコード上でいじりながら試すのは難しいですね。
で、実装を終えた後もネット上でソースコードを調べていたら、多くの人は以下の書籍を参考にしているのだと知りました。

Amazon: Texturing & Modeling A Procedural Approach Third Edition 日本語版 [単行本]

せっかくなので買おうと思いましたが、価格を見てやめました・・・14,700 円って。中古もあるようですが、どうもこの手の本を中古で買うのは嫌で。英語版ならばもっと安いようなので、どうしようかなぁ・・・と。

次は、Height map を作成しただけでは何の意味も無いので、続いて頂点データの構築と表示を実装しようかと思います。ひとまずは、ごく普通の地形表現で頂点データを作り、3D における height map の状態を確認したいところです。

2012/06/28

Perlin Noise を実装中

結局、自動生成や様々なシミュレーションの簡易さを考慮し、当面は heightmap からの地形生成のまま進めることにしました。そこで、自分のアプリケーションから heightmap を生成して編集できるようにしようと思い、Perlin noise (パーリンノイズ) を調べて実装している最中です (過去作成した地形では L3DT で出力した heightmap を利用していました)。

Heightmap や procedural texture を調べると、頻繁に Perlin noise という言葉が出てきます。このため、アルゴリズムの説明や公開コードも豊富であろうと考え、気楽に実装を始めたのですが・・・想定外のハマり方をしました。

結論からは、Perlin noise の説明や実装は簡単に見つかります。しかし、その多くが「Perlin noise ではない」のです。この答えに到達するまでに随分時間が掛かりました。

Perlin noise は、gradient と呼ばれる擬似乱数のベクトルをグリッド上に配置し、任意の位置 (グリッドに沿っているとは限らない) のノイズ値を、それを取り囲む 4 点にある gradient から重み付けを考えて算出する仕組みかと思います。
恐らく、Perlin noise を理解しようとした場合、Matt Zucker による The Perlin noise math FAQ を読むことがベストだと思います。

Perlin noise は、gradient を元にしたアルゴリズムであることから、gradient noise として分類されるそうです。

Gradient noise: http://en.wikipedia.org/wiki/Gradient_noise

上記ページには、興味深いことが書かれています。「しょっちゅう value noise と混同されます」と。事実、Perlin noise 実装を謳ったコードの多くが、この value noise に分類されるものです。Wikipedia の記述からは、あまりに混同されるために gradient noise と value noise という分類を作ったという印象を受けます。

Value noise: http://en.wikipedia.org/wiki/Value_noise

上記ページには、Perlin noise ではないにもかかわらず Perlin noise として説明している某サイトへのリンクが value noise の説明として貼られています。
厄介なことに、Perlin noise を検索すると、このサイトが上位に現れます。このサイトでは、擬似乱数のスカラー値をグリッド上に配置し、それらにブラーをかけ、更に補間を行ない、滑らかなノイズとしているようです。

このサイトの内容は非常に有益でしたが、誤ったタイトルを付けたことで、Perlin noise ではないものを Perlin noise であると解釈した人が大量に生まれたのではないかと推測します。
僕も Ken Perlin にのみ従っていれば良かったのですが、誰かの C# コード丸パクリで済まそうとしたことで、この混乱の渦へ自ら身を投じてしまったようです。

と言うことで、Ken Perlin によるオリジナルコード、および、 Matt Zucker によるらしい C++ コードを見つけたので (見つけた場所が怪しいためリンクを貼りません) 、それらを元に XNA で実装しています。
先行して、Ken Perlin による Improved Noise reference implementation (Java 実装) を C# へ移植したのですが、ちょっと gradient の式が理解できていません・・・。

他には、libnoise というノイズ生成のためのオープンソースライブラリも参考にして進めています。libnoise のコードはクラス設計が綺麗に纏められており、コードを読んでいて心地良いです。

2012/05/14

FF13&FF13-2

結局開発はせずに FF13 & FF13-2 をやり、FF13-2 を今クリアした所です。

Skyrim は面白いのですが、クエストは極めて退屈で、僕は内容を無視し、アイテムや能力取得のために取捨選択というプレイです。で、そうこうしているうちに、久しぶりに凝ったシナリオの RPG をプレイしてみたいと感じ、思い出したのが FF13-2 で、FF13 合わせて GW 頭辺りからひたすらプレイしていました。まぁ、昨今の FF のようなゲーム形式を RPG と呼ぶのかどうかという問題はありますが。

本当は、FF13 を買いたくなかったです。買いたくないと思った FF は、オンラインも含めて FF13 が初めて・・・ですが、FF13-2 のタイムトラベルのシナリオに興味があり、FF13-2 を楽しむには FF13 を買わざるを得ず。

FF13 はネットで言われる数多の批判そのままですかね。3000 円程で Collection 版を買いましたが、それなら見合う額かな？（中古ならもっと安いかな？）。

FF13-2 は期待した質で楽しめました。アマゾンで 2000 円強でしたが、ちょっとこの額ではスクエニに気の毒な感じもします。まぁ僕はタイムトラベルというだけで楽しいので、ちょっと観点が違うかもしれない。FF13 の続編と考えると、そりゃそうだろうという気もします。

ED は真 ED や DLC の類ではなく、続編への布石と解釈しましたが、出せるのですかねぇ・・・。

とりあえず、後少し FF13-2 のクリア後要素を楽しみ、開発に戻ろうと思いつつも、Mass Effect 3 もやりたいのに放置状態で、どうしようかなぁ・・・。
ゲームをやりながらも、コードを書くための準備として調べ物などは行なっていますが、どうにも気持ちが入ってこないことが問題で。

2012/05/07

近況

先の動画投稿の辺りから胃の上部に違和感があり、全く集中できない状態であったため、開発は停止していました。集中できないどころか生活そのものに影響が出ていたというか。
数週間症状が緩和しないので病院に行き、採血、胃カメラ、検便の調査を待ちつつ、薬を飲みつつ、何をしても辛いので Skyrim 廃人となって養生（？）していました。

GW 中に出た検査結果は「健康そのもの」。原因不明なものの投薬で緩和されてもいて、もうしばらく投薬を続けて終了のようです。違和感もほぼ無くなってきたので、そろそろ開発を再開しても大丈夫かなと。

しかし、開発のリズムを完全に失ったことが問題で、これを取り戻すことが案外大変。

2012/04/09

モデルの非同期＆分割ロード

先日上げたデモ動画では、モデルのロードで非同期処理と分割処理を組み合わせています。ここでは、それらの実装について書いてみようかなと。

最初は、モデルファイルの読み込みから VertexBuffer の作成までを 1 つの処理とし、Game Thread とは別の Thread へ渡してみましたが、上手く動きませんでした。Game Thread が呼び出す Game.Draw() では SpriteBatch などが描画処理を行いますが、その最中に別の Thread が VertexBuffer.SetData() を呼び出すと、どちらかの Thread の処理がコケます。
僕は GPU が絡む部分がよくわからないので、詳しい人からのツッコミが欲しい所ですが、恐らく、どちらも GPU へ命令を渡す部分であり、そこでの競合が発生するのだと思います。

こういう問題があったため、モデルのロード処理を、まずは以下の 2 つに分割しています。

モデルファイル読み込みから頂点データを作成
1 で作成された頂点データから VertexBuffer を作成

こうしておき、1 だけを別の Thread へ渡します。この時、コールバックメソッドも同時に渡し、1 を終えたら呼び出されるようにします。そして、コールバックメソッドは 2 を Game Thread で管理するキューへ入れます。
この時、更に 2 を分割してからキューに入れます。僕の用いるモデルは複数の VertexBuffer を用いるため、VertexBuffer の単位で処理を分割してキューに入れます。XNA の Model クラスで喩えるならば、ModelMeshPart を個別に構築する感じです。

キューに入れられた処理は、Game Thread が呼び出す Game.Update() で順に取り出され、VertexBuffer を作成します。そして、何度かの Game.Update() の呼び出しで全ての VertexBuffer の作成が完了したら、モデルのロードが完了したということになります。

要するに、1 だけを非同期にし、2 を Game.Update() 内で行うようにしたわけです。そして、2 を可能な限り細分化し、Game.Update() での負荷を下げたという感じです。

1 の非同期処理は、僕は ThreadPool を利用して Thread に割り当てています。ただし、そのまま使うと Thread 数の制御ができないため、ここでもいったんキューに入れ、Thread 数を制御しながら割り当てています。

で、ここまでやってデモアプリを計測したら、1 を非同期にする程でもなかったというオチでしたが、今後のコード次第ではどうなるか分からないので、このパターンのままやろうかなと。
ContentManager.Load() でロードする場合でも、その単位でキューに入れれば Game.Update() の負荷を下げられるんじゃないかと思います。

なお、デモ動画の段階では、1 の処理完了で即座にコールバックメソッドを呼び出していますが、今はこれもいったんキューに入れ、Game.Update() 内でコールバックが呼び出されるようにしています。
基本的には、多少回り道をする処理となっても、同期をとる箇所をまとめてしまう方が、他の部分で lock を書いたりせずに済んで見通しが良いのではないかと思います。lock 漏れも怖いですし、それらのデッドロックも怖いですし。

ソースコードの例としては、非同期処理については、以下のコードを HTTP 通信の非同期処理に用いています。

https://github.com/willcraftia/Blocks/tree/master/Framework/Threading

上記はモデルのロード処理ではないですが、同様のパターンを用いて非同期処理を行なっています。
モデルのロード部分は、専用モデルを用いていることから複雑でありオススメできないサンプルですが、興味のある人は以下などをどうぞ。

https://github.com/willcraftia/Blocks/tree/master/Blocks/Content

上記にある InterBlockMeshLoadQueue が非同期処理、BlockMeshLoadQueue が VertexBuffer 分割キューです。
※master にあるコードなのである日突然消えたりするかもしれません。

なるべく短命なオブジェクトが生成されないように工夫してみたつもりですが、どうですかねぇ・・・。

2012/04/03

はじめに

はじめまして、あるいは、こんにちは。

過去、 3D でドット風モデルと物理システムを用いたプログラムを XNA で作成し、それを動画として上げていましたが、3D グラフィックスの分野は全くの素人であったため、試行錯誤により滅茶苦茶なプログラムを書いていました。また、いつしか目的を見失っていた所もありました。

最近は、それらを頭で整理できるようになってきたので「ちょっとブログでもやってみようかな？」という軽い気持ちで始めています。なお、このブログのハンドル名は、Google 先生が最近怪しいので、気持ち程度に本来のものから変更しています。

XNA の話題が多くなるかもしれないですが、XNA の範囲にない技術も使っていくので、色々と雑多な内容になるかと思っています。開発やゲームに関係するという縛りの上で、しょうもない日記も上げるかもしれません。

いずれにせよ、飽きるまではやってみようかな・・・と。

ひとまずは、XNAで作成した UI Framework のデモ動画を用意しているので、近いうちにニコニコ動画へ上げると思います。

それではよろしくお願いします。

登録: 投稿 (Atom)