進捗状況(2011/07) - FPSを作ってみる@wiki

(2011/07/25)

マルチスレッドと描画が遅いのと

引き続きTwitter APIを利用するためネットワーククラスを整備している．が，前回書いたとおり
いくら「作ってみる」とはいえシングルスレッドでサーバーから応答が来るまで止まるのは論外．
従って非ブロッキングAPIに切り替えるかマルチスレッドにする必要がある．
例の如く前にもターン制ゲームでやったんだけどね・・・と思ってファイルの日付を見れば丁度一年前．そんな昔か．
当時のことなどとうに忘れたのでソースを読んだら本スレッドとは別にスレッドTを1つ作成し，Tがソケット通信全てを仕切る形で
ネットワークから返答が来る度にシグナルによってTが起動するようになっていた．
つまりシングルスレッド的な解決法である．

まぁ実を言うとソースを読む前に通信要求に応じて新しくスレッドを作成するタイプの
マルチスレッドな実装をしてしまった訳だが・・（この類のデザインパターンがありそうだが名前を知らない）
当方素人なもので双方がどういった利点や欠点を持つのかイマイチ把握してないし
単にブロッキングを避ける為ならどちらでも難度は大して変わらないんじゃないかなんて思ったり．

自作GUIの方も同時進行．JSONでウィンドウ配置を記述できるようにしたので
調子に乗ってウィンドウ数をどんどん増やしていたらデバッグビルドとはいえ動作が異様に遅くなった．
一瞬「スクリプトに頼りすぎか？」ビクッとしたが
よくよく調べれば描画関連，とりわけDrawPrimitiveの呼び出し回数が原因と判明．
そりゃあね．文字1文字描画するのにDrawPrimitiveしてりゃあ遅くもなりますわな．文字列描画クラスを書いた当時は効率なんか全然気にしてなかった．

ウィンドウ1つの内訳は矩形描画に1回，枠描画に1回，文字列長は平均20=20回として22回
それを32個描画したら激重になったという事は毎フレーム700回程呼び出していた計算になる．
なんでもXBoxとかのゲーム専用機と違ってPCの場合描画APIの回数がネックになりやすいとか（HALOのPC版が重いのもこのせいだとか）．
当然減らす方向で考える．

矩形と枠に関してはテクスチャは共通だからそれぞれ頂点をリスト一本化すれば良さそうだ．
文字列はテクスチャを一枚に纏めようか．シンプルに考えたらUnicodeの基本的なBMPをカバーするには
UTF-16でいうサロゲートペアと私用領域を除いた57000文字くらいを全部1枚のテクスチャに・・・と，そこで諦めた．
どんだけメモリが要るんだよ．そもそも制御文字なんて描画しないだろと．
じゃあ英語と日本語で使われるであろう文字だけを含めたらどのくらいだろうか？
ゲーム専用と割り切るならもっと絞れるが今回はTwitter用なので顔文字に使われるかもしれない記号類を全て含める方向で行けば，
アルファベット，平仮名，片仮名，CJK漢字，記号・・・うぬ．40000文字とか行ってしまうな．
それ以前にどの部分が描画の必要なくてどの部分がそうでないのかがグループでガッツリ分かれてなくって調べるのが面倒極まる．
こんなの商用以外のソフトでやるべきじゃないと判断．

他に考え付く妥当な手法としてはテクスチャ複数枚か．
文字列を与えるとフォント描画用の頂点リストとテクスチャのペアが1組～複数組返ってくるようなインタフェースで良さそうだ．
あるテクスチャがカバーしない文字コードの矩形はα値を0にする等で透明にしておく．
後は必要に応じてテクスチャでソートするなり何なりと．

問題はテクスチャを分ける基準である．
単純に文字コードでやってもいいが，やはりよく使う文字を一枚にしたいと思うのは自然であるからして
使った文字を先着順に登録していって溢れたら次のテクスチャ領域を確保して・・という形にしたい．

(2011/07/17)

OAuth

Twitter APIは簡単なのにOAuthが手ごわい．言うなれば最初の街から出た直後の敵がレベル10みたいな．
認証方式は他にxAuthという簡易版があるようだがユーザー名とパスワードをアプリケーションに入力してもらう必要があるので
微妙だなあと思ったり思わなかったり．
そりゃまぁ，毎回パスワードを平文で送るbasic認証よりはマシだが
やはり大事な情報はtwitter本家と直接やり取りしてもらった方が一手間増えるにしても安心感が違うだろうと．
OAuthは有名な仕組みなので世に出回っているライブラリを使うのも手だが勉強も兼ねて自作してみた．
（流石にSHA1ハッシュ生成はソースぱくった）

詰まったのは何と言っても認証文字列の生成．
これはコマンド，URL，認証パラメータ等を一定の規則でもって繋げて1つの文字列に加工するもので
その中にURLエンコード（URLに使えない文字や記号を%(文字コード数値)の形に変換する作業）があるのだが
URLエンコードと言いつつwebで言うURLエンコードと違うという．
というかそもそもOAuthのドキュメントではURLエンコードなんて単語は使われておらず「パーセントエンコーディング」や
「パラメータエンコーディング」と呼称し
はっきりと”webの奴とは違う”と書いてあるじゃあないか．
何時だったか先輩の「ネットの非公式資料は当てにならん」発言が思い出される・・・

署名アルゴリズムを間違うと当然の如くハッシュ値が違うとしかエラーだしてくれないから
何所が悪いのかサッパリわからない所がミソ．
URLエンコーディングとOAuthのエンコーディングは一部だけ違う関係で
送信する文字列によっては認証が通ったり通らなかったりとか．
逆に言えばそれ以外はすんなりと実装できた．
今のところはシングルスレッドのブロッキング動作で使い物にならんけど後々改良の方向で．

(2011/07/15)

Twitter API

自分のtwitterを注意深く観察していた人がもし居たら気づいたかもだが
現在twitter APIを勉強中である．
何故既に沢山あるtwitterクライアントを作るのかといえば，単純に作ってみたいってのが一つ，それと
ずっと開発途中なのは心が折れそうなので小規模でも完成品が欲しくなったというのが一つ．

twitter APIは2種類用意されていて，それぞれ
コンテンツを明示的に取得しに行くpull型（REST API）と
コンテンツが自動で届けられるpush型（Stream API）である．

REST API自体は例えばパブリックTLが欲しかったらhttp://(twitterのホスト)/statuses/public_timeline.jsonにHTTPリクエスト（GET）を送れば
結果をJSONで返してくれるような単純な物だ．
あるtweet以降のだけが欲しければ予めドキュメントに記載されているパラメタに従って since_id=(tweetのID) などとやればいい．
ここまで何気にREST, RESTと書いたが，単語の意味を知らなかったのでググッて調べてみたりもした．

RESTはRepresentational State Transferの略．
Webを見る限りRESTの定義は曖昧な関係上ここでは厳密にRESTとは何かという話は無しにして
とりあえず自分は

• HTTPメッセージがそれ1つで完結していて，サーバやクライアントのセッションの状態に左右されない
• リソースはすべてURIを持ち，ユーザーはリソースにHTTPメソッドを適用する事でデータのやり取りを行う
• リソースが他のリソースを指し示す際にはやはりURIのリンクを用い，別途レジストリのような情報を必要としない

そのようなAPIをRESTと呼ぶのかなあと思っている．間違っていたら指摘してくれれば有り難い．

話を戻して基本的にはユーザーはURIにアクセスして情報を取ってくか，又は情報を更新するだけである．
しかしユーザーアカウント情報を使って何かする場合
これだけだとどのユーザーのリクエストか，権限があるのか等区別できないので実際には他に認証用のヘッダが付く．
Twitterの認証にはOAuthが使われていて
こいつが中々の曲者で勉強時間の殆どが費やされたといってもいい．詳細は次の機会にでも書く．
まぁ一端出来てしまえばどうという事は無いのだが・・・・

で，Stream APIについてはどうなのか．
まだRESTの方に手一杯なもんであまりよく知らない．
RESTでやってたような通信を一回一回切らずに接続したままにしておき，必要に応じてサーバが情報を送ってきてくれるような物．としか．
少なくとも更新があった時にだけ通信が行われるしRESTで何度も問い合わせるより負荷を抑えられそうだ．

(2011/07/13) #2

自前GUI

物事集中するには懸案事項を先に済ませておくのが鉄則．であるからして立て続けに進捗回想報告をする．
自前のGUIといえばその昔，3年前の動画で既に実装しているのだが当時は（今も）プログラムの組み方も碌にわからず
動いてはいるがソースが立派なスパゲッティであった．
で，今回LuaでGUIを再実装しようという訳だ．
マウスカーソルとGUI部品の判定に早速書いたばかりの当たり判定モジュールを使っている．
結合を疎にする為，クラス間の通信はメッセージパッシング方式とした．（関数を直接呼ぶのではなく命令やパラメタを記載したメッセージを送付する）

自分はGUIの中でもとりわけWindows(vistaより前)を触っていたからか，やればやるほどWin32APIに似てくる所から
「あの一見面倒くさいWindow初期化は，なるべくしてなった仕様なのかー」とか思ったりして
より理解度が高まった気もする．
(vista以降は知らないがwindowの描画バッファは個別に持っているようだしよりスマートなんだろう)

基本的に前やった物の再実装なんで特に書くことがない・・・
変わったといえばカーソルを持っていくとその部品にフォーカスが移る方式（Linuxみたいな？）から
部品をクリックするとフォーカスが移る方式（Windowsですな）にして，
ウィンドウの表示順位と後ろに隠れた当たり判定の無効化もちゃんとしたくらいか． <= 前はテキトーだった．

新しく追加したい機能は一回一回ウィンドウの初期値にサイズや色を渡すのが面倒で取り回しもしにくいと感じたので
JSONでウィンドウレイアウトを定義して適用する機能．
テンプレから一部だけ違うウィンドウを作る場合も想定しJSONをLuaテーブルとして読み込む関数を用意．
初期値としてそのテーブルを渡せばいいかな？

(2011/07/13)

当たり判定(2)

作業の気乗りがしない時はページを更新すれば良さそうだ．適度に何かしてる感があって宜しい．
ええと前回話が長そうだから区切ったはずだが（書くはずの内容があやふやに・・），引き続き当たり判定について．
判定の手順は問題ないとしてLuaで定義した球や円柱の判定形状をどうやってC++に渡すのか．
身も蓋も無い言い方をすれば「Luaスタックに詰んで，C++で読み取る」わけであるが
渡すタイミングと頻度を考慮すると幾つかの方式に分けられる事に気づく．
ゲームを通して静的な形状なら初期化時に全てC++に転送しておけば無駄がない．問題は動的な形状である．
一口に動的といっても大きく分けて2種類考えられ
「ポリゴンの頂点を行列で変換する（キャラクターの関節など）」場合と
「関節関係無しに何らかの計算でもって変形する」場合がある．
前者はLuaから渡す情報を関節の角度に限定すればデータ転送量を節約できるし，重い行列の計算をC++側で行えるだろう．
後者についてはまぁ・・・地道に転送するしかあるまいな．

便宜上名前が要るので今後静的な形状をSTATIC形式，動的形状（行列変換）をTRANSFORM形式，動的形状(独自変形）をDYNAMIC形式と呼ぶ．
STATICは説明不要．事前に判定形状クラスをC++とLuaで用意しておいてテーブルから値をチマチマ取得してくだけ．
階層構造は，基本的にヒットしない事を前提としてキャッシュ効率を考え深さ優先ではなく幅優先にしてしまったのだが
効果の程は両方やってみないとワカランという．
TRANSFORMはオフセット，回転，拡縮を含んだPose構造体を各ノードに置く．更新は毎フレーム一回．
DYNAMICは形状を変更したらユーザーが手動でフラグを立てる方式に．
いちいち関数を呼ぶのが手間だがメタテーブルをいじって自動検出にしたら速度低下のデメリットが大きそうなので見送った．

何分ちょっと前の事なんで細かい所で処理の効率化を図ったりはしているが，概ねそんな流れ．
更新が遅れ遅れになって恐縮である．ついでに申すと今回の分でようやく7月という・・　～続く～

(2011/07/05)

当たり判定

個人的にゲームの要は当たり判定だと思っている．ゲームはユーザーの操作に対してインタラクティブに変化しなければならない．
インタラクションに欠かせないのが当たり判定というわけだ．

ところで自作エンジンのスクリプトに関する方針は

• Luaを採用しアプリケーション全般の動作をこれで記述する
• APIを呼んだり重い処理のみC++が担う

である．理由は自分が同じフレームワークであれこれやりたい性分なので（云々・・）以下略
ちなみに市販ゲームなんかのLuaスクリプトファイルを覗くと概ねそのゲーム専用の関数と用意されたクラスを使って
初期化なら初期化の手順，敵のアルゴリズムならそれ用にと局所的な使用に留まっている．というか処理速度の点からもそれが普通だと思う．

例の如く話が逸れた．要するに当たり判定も球と線分ならそれオンリーでガッツリ組み上げるんでなくて
もっとフレキシブルにしたいという事である．さしあたって幾つか考える事項がある．

第一に当たり判定をするからにはサポートする基本形状を定義する必要がある．前述の球や線分，ポリゴンに円柱といった具合だ．
第二に当たり判定の構造を表現する何らかの手段が要る．球の集合とか，キャラクターなら木構造の円柱とか．
第三に判定アルゴリズムは当たり判定構造と分離させたい．例えば球で大まかな判定をした後にポリゴンで詳細な判定をさせる場合に
　　「球で判定して，当たっていたらポリゴンで判定する」ルーチンを用意するんではなくて
　　「球で判定する」のと「ポリゴンで判定する」のを別々に用意しておけば後はエンジン側で組み合わせてやってくれる寸法．

1に関してはストレートに使いそうな形状を構造体で定義するだけである．
2は・・・一言で説明するならば当たり判定構造を1つの32bit数値(4bitずつに分け, それぞれ形状のIDを表現)とした．
3は2で定義した32bit数値をビットシフトさせつつIDを読み取り，予めリストアップしておいた判定関数を呼び出す形となった．

んん？この話前に書かなかったっけ？と思ったらやはりあった．
http://www11.atwiki.jp/slice/pages/66.html　の，19日．
読んでもらえば分かるがこの記事ではまだIDを作るとこまでしかやってない．一応，本丸の判定処理は部分的に実装していたのだが・・

長そうだからここで一旦区切る．　～続く～

(2011/07/03)

エクスプレッションテンプレート

約1ヶ月放置．やっちまったな．前回何書いたかも忘れてしまった．
見たら行列，ベクトルのクラス書いてたんか・・
例によって例の如く6月14日と19日の書きかけの記事が残っているのでこれを混ぜつつ進捗．

まずあの後エクスプレッションテンプレート(ET)という手法を勉強し，数学クラスに適用していた．
詳しく書くと長すぎてまた記事がお蔵入りしそうなので手短に説明する（長いけどこれでも結構端折っている）

ETとは見た目の分かりやすさを維持しつつ処理の効率化を図る手法だ．
C++の宿命というか特有の問題なのだが例えばベクトルクラスA,B,Cがあったとして
X = A + B * C;
と記述したらまずB*Cで一旦ベクトルクラスが作られ次にそれにAを足し再度クラスを生成，最後に結果をXへコピーするという動作になる．
言わずもがなコピーの動作が余計なので従って処理効率が悪いという訳だ．
普通に考えたらX.x = B.x * C.x + A.xと，一度に計算してしまえばベクトルクラスの一時領域なんて要らない．また，そうして欲しい．
もちろん一行ずつ　X = B;　X *= C;　X += A;　とやれば目的は達成できる．が，読みにくいし何より格好悪い．
今時のコンパイラは優秀だから実際VisualStudio2008で試したらこの程度じゃ最適化され全く問題ないが
行列だと計算式を展開し切れなくてはじめに書いたような動作になってしまう．
これを解決するのがETである．

B * C と書いた時点ではまだ計算はせずに「BにCを掛ける」という情報を返す．
これに更にCを足すなら「(BにCを掛ける)にAを足す」というようにどんどん付け足していく．
ここで疑問に思うのが「どこにそんな情報を格納するのか」であるが，これは型として表現する．C++お得意のテンプレートですな．
今の例で擬似的に表現するとAdd< Mul<B,C>, A> という感じ．
で，いざ結果が欲しいとなれば結果のベクトルをRとすると
R.x = B.x * C.x + A.x;
R.y = B.y ...
という風に各成分毎に計算する．こうすれば使う記憶容量は最小限で済む．

ここまでが6月14日の分．　～続く～