2003-02-01
ここ数日， GDAlgorithms へのポストが増加傾向にある。いくつかの興味深い質問が挙げられており，それに関しての議論で盛り上がっているようだ。その中でも特に混迷を極めているのが "Game Entities" スレッドだ。
http://www.radiumsoftware.com/excerpts/game_entities.txt
最近よく，ゲーム中に独立したコードとして動作するオブジェクトのことを "Entity" と呼んでいる所を見かけることがある。これよりももう少し原始的なものについては "Object" と呼ばれ，逆に自律するくらい高度なものになると "Actor" に変化するようだ。なんて言うか，出世魚みたいなもんかな……。僕が初めてこの "Entity" というタームを見かけたのは "Quake" のコードの中だった。それ以前にもこういった用語が一般的に使われていたものなのかどうかは分からないけれど，なんとなくこの辺りが発祥であるような気がしないでもない……。
似たような疑問は "Avatar" という単語についても感じられる。最近は特に，サイバースペースに投影されるプレイヤーの分身のことを指してこう呼ぶようだ。恐らく，発祥は "Ultima" シリーズにあるのではないかと考えている。
http://www.everything2.com/index.pl?node=avatar
ええと，それはさておき……件のスレッドの内容は，エンティティを動的に生成しまくっているとメモリの断片化が怖いねえ，って感じの話題だったんだけれど，途中からは，エンティティの派生をどのように管理すべきか，という話題にシフトされている。
前者の質問に対しては，やはり，メモリプールのような緩衝機構を用意しておいて，ある程度まとまった範囲での確保・廃棄が効率良く管理できるようにしておくのがいいんじゃないか，というような流れになっている。僕はこの問題に関してそれほど危機感を持っていないんだけれど，確かに，広大かつシームレスなワールド構成のゲーム（"Jak and Daxter" みたいなやつだ）とか，やたらと多彩なエンティティが大量に登場するゲームなどでは，色々とやっかいな問題が発生しそうな感じがする。
この受け答えの中で， Boost Pool Library に関する記述が出ていた。
http://www.boost.org/libs/pool/doc/index.html
ああ，こんなのもあったか……。もしかしたら役に立つかもしれない。未チェックなので，後で調べてみようと思う。
メモリ管理に関する話題は比較的早い段階で終わっていて，あとはクラスの継承・派生に関する話題がメインとなっている。この手の議論は定期的に話題にのぼってくる傾向があるようで，今回もここぞとばかりの盛り上がりを見せている。これという結論が得られ難いために議論が終着しないというのもあるんだけれど，その時々の状況によって要求されるレベルや実現可能な範囲などが変化し続けていることを考えると，やはり定期的に検討すべき項目なのかもしれないと思う。
今回の議論で特に興味深いのは，継承を繰り返すことによって徐々に抽象度を下げ，ツリー構造状の派生パターンを構築するという，いわば教科書的な方法が，昨今の大規模なゲーム内容には適していないのではないかという指摘だ。この問題に関しては， GDC 2002 における Scott Bilas 氏のプレゼンテーションが詳しく触れている。氏が実際に "Dungeon Siege" の開発において利用した手法を中心に解説が展開されており，実用面から見ても非常に参考になる資料なのではないかと思う。
http://www.drizzle.com/~scottb/gdc/
一言で表すならば，「継承ではなく集約を意識せよ」ということになるかな……。あとは，属性の特化を担う部分を，上手くデータ制御に持っていくことがキモのように思われる。ううむ……。
この話題に関しては，もうちょっとゆっくり考えて整理してみようと思っている。何しろ，ゲームを作る上で最も重要な部分かもしれないんだから……。
2003-02-02
とある事情で C のコードを書いている最中に，ふと C++ の癖で， for 文の中に変数の宣言を書いてしまった。
これを gcc 3.1 以降でコンパイルにかけると，次のような警告が出てくる。
あ，一応コンパイル通るんだ……。どうやら C99 仕様と関連があるらしい。 C99 仕様なんて言うと，なんとなく名前だけは聞いたことがあるものの，まともに調べたことは一度も無い。むむ……。
この機会に，ひとつおさらいしてみようと思う。
C99 (C9x) についての情報は，次のページによくまとめられている。
http://home.tiscalinet.ch/t_wolf/tw/c/c9x_changes.html
日本語なら，次のページの解説が丁寧で非常に読みやすい。
C99 は ISO 委員会によって定められた C 言語の標準規格の一つだ。旧仕様からの変更点の一覧を見てみれば分かるように，今までは各コンパイラによって拡張機能としてサポートされていた，言わば事実上の標準のようなものが，正式な規格としてまとめ上げられている。
http://wwwold.dkuug.dk/JTC1/SC22/WG14/www/newinc9x.htm
特に，文法に関する拡張には重要なものが多く含まれている。
http://home.tiscalinet.ch/t_wolf/tw/c/c9x_changes.html#Synta...
http://home.tiscalinet.ch/t_wolf/tw/c/c9x_changes.html#Seman...
http://seclan.dll.jp/c99d/c99d07.htm
例えば，構造体の初期化におけるメンバ名の指定方法や，不定長配列，不定初期値，０長配列，……などといった機能は，これまでも gcc や VC++ の拡張機能としてサポートされていたものだ。むしろ，これらが標準仕様でないと意識していることの方が少ないだろうと思う（だから "-ansi --pedantic" なんて付けた日にゃ，警告が死ぬほど出てくる始末になるわけだ）。
これらの仕様が正式に規格化されたことによって，何かが大きく変化するというわけではないものの，精神的な負担を軽減するという意味では効果があるかもしれない。０長配列なんてのは，いかにも手抜きのテクニックっぽいんだけれど，正式に使うことができるとなれば，これはこれでなかなか便利な機能だと思う。
逆にあまり馴染みが無いのが，変数宣言とコードの混在，とか， for 文の中での変数宣言，などの新仕様だ。特に Compund Literal （無名オブジェクト）などは，他の C++ からの天下り仕様とも違って，今までになく特異な要素のように思われる。
http://gcc.gnu.org/onlinedocs/gcc-3.2.1/gcc/Compound-Literal...
あっ，でも，昔もあったような気がするなあ……。たしか "Constructor Expression" とかいう名前だったんだ。
http://gcc.gnu.org/onlinedocs/gcc-2.95.3/gcc_4.html#SEC80
この辺りは gcc の拡張機能のなかでも特殊性の強いもののように感じられていたので，なるべく使用を避けるようにしていた。でもまあ，これも標準仕様になったわけか……むむ。
文法の拡張の他にも，コード生成に影響を与えるオプションなどが，新たにいくつか定義されている。 inline についてはともかくとして， restrict 属性については少し調べてみる必要があるかもしれない。
http://www.lysator.liu.se/c/restrict.html
仕組みは理解できるものの，生成コードに対してどの程度の影響を与えるものなのかは，実際に出力されたコードを観察してみないことには分からない。もともと "--strict-aliasing" オプションなどを日常的に利用している人もいるだろうから，そういった場合には，改めて目立った効果を上げることはできないかもしれないと思う。
最後に，実際のコンパイラがどの程度 C99 に対応しているものなのか把握しておく必要がある。 gcc については次のページに詳しく解説されている。
http://gcc.gnu.org/c99status.html
文法に関しては gcc 3.1 の時点でほとんど対応されているものと考えていいみたいだ。数値演算の補足仕様やワイド文字の周辺に問題が目立つものの，どれも個人的には縁の無い領域ばかりなのが救いだ。
VC++ については， Visual Studio .NET 2003 の出来次第かな，と思う。
http://msdn.microsoft.com/visualc/productinfo/visualc03/over...
初の C++ 標準規格完全サポートをうたっている VC++ 2003 だけれど…… C99 に関しては情報が何もない状態だ。まあ， VC にとって C99 って，とりたてて重要そうなものでもないしなあ……。
2003-02-03
つい先日， "Avatar" という単語について軽く調べていたときに，この単語の元となったゲーム "Ultima" のことを思い出してしまった。僕はこのゲームのフリークではないけれど，まだ「洋ゲー」という単語が存在しない頃から独特の雰囲気を放っていたこのゲームのことは，幼い記憶の中にも印象的なものとして刻み付けられている。
"Ultima" は言うまでもなく， Richard Garriot 氏によって制作された一連の RPG 作品のことを指している。
http://yach.tri6.net/ultima/index.html
http://www.gamespot.com/features/ultima/03.html
近年の作品 UO - "Ultima Online" において MM-ORPG の先駆けとなり，一大ブームを引き起こしたことは記憶に新しい。このシリーズはそれ以前からもずっと，伝統的なコンピュータ RPG の代表格として，その名をとどろかせていた。難解なストーリーと微妙なゲーム性は賛否両論を呼ぶところかもしれないけれど，洋ゲーに独特の自由度の広さや，冒険心をくすぐる優れた世界観の構築など，まさに大陸的とでも言うべき風格を備えたゲームとして，何物にも変えがたい独特の魅力を放ち続けていた。
Richard Garriot 氏は， Ultima シリーズにおいて，一貫して "Lord British" と呼ばれる統治者の役を演じていた。 Lord British とは，言わばゲームの道先案内人だ。プレイヤーに対して冒険の目的を与え，他の登場人物が知り得ない事実を告げ，時には死んでしまったプレイヤーに対して再び生を与えたりする。無敵にして万能の存在だ。
さらに氏は，シリーズの中盤以降において，「Ultima 世界の創造主である彼自身がプレイヤーを召還する」というメタ設定を好んで用いていた。ブリタニア（Ultima 世界の固有名称）において何らかの異変がもたらされると， Lord British はそれを解決すべく Avatar を召還する。ここで言う Avatar とは， Ultima 世界に対して投影されたプレイヤー自身の姿のことだ。
プレイヤーは "Ultima" というゲームソフトを介してブリタニアの世界に触れ，そして Lord British と出会い，冒険の真の目的を知らされる。しかしその Lord British とは，実は Richard Garriot 氏の分身に他ならない。ゲームをプレイする人と，ゲームを創造する人の関係が，その瞬間に，実に暗喩的な形で表現されているという構図だ。
そんなわけだから，僕は，てっきり， Ultima シリーズの最終作では，こんな感じのラストが演じられるものだと思い込んでいた。
しかし，ついぞそんな終焉を見ることはなかった。 Ultima シリーズは Richard Garriott 氏の解雇という形で幕を閉じてしまったのだ。
http://www.4gamer.net/specials/special_garriott.html
自らが育てた Origin Systems から解雇されてしまうとは，なんとも悲痛な幕の閉じ方ではないかと思う。たとえ，何らかのまぐれによって Ultima シリーズが再開されることがあったとしても，利益を第一に追求する EA 社の手によって，以前のように荒唐無稽なスケールを誇る物語としての "Ultima" が作られることは，二度と無いだろうと思う。
http://home.att.ne.jp/gold/uo/richard.html
2003-02-04
このところ，やたらミーティングが多くて，コードを書く時間が短くなってきているような気がする。しかし，ちょうど手持ちのタスクに煮詰まりを感じつつある時期にあったことを考えると，むしろコーディングから距離を置くことは良い機会なのかもしれないと思う。ひたすら書きつづけていたコードを，ふと立ち止まって見返してみると，以前は見落としていたものが，急に見えるようになってくることもある。……っていうか，それは設計が悪いせいなんだけれど。
ほんのちょっとの間，気を休めてから，また気合を入れて行こうと思う。
Tiago Sousa 氏の照明モデルのデモ "Illuminatu" を見てみた。ポルトガルのゲーム制作ポータル "GameDev PT" 内にある氏のサイトからダウンロードすることができる。
http://realtimecg.gamedev-pt.net/research.html
これは，いわゆる DOOM III 方式の統一照明モデルを実装したもののようだ。ステンシルシャドウ， per-pixel シェーディング，法線マッピング，簡易グロー（非ＨＤＲ式）など，流行りのギミックが一通り盛り込まれている。なかでも最も強力なのは，本物の DOOM III からモデルとテクスチャを拝借してしまっていることかもしれない。これってたぶん，違法に入手した流出モノの DOOM III から勝手に引っこ抜いたものなんだろうなあ……。これはもちろん非常に宜しくないことなんだけれど，そのことについては敢えて追求しないでおこうと思う。このデータのおかげで，観察対象としては興味深いものになっているからだ。
このデモを見ていて一つ思い出したことは，光源の当たっていない部分において凹凸感が著しく失われるという現象についてだ。この現象については以前から幾度となく指摘があって，一応の問題としては認識していたんだけれど，実際にこれを目にしてみると，思った以上に影響があることを知ることになった。
http://www.radiumsoftware.com/img/030204_fig0.png
この現象は，法線マッピングを使用している場合の注意点として挙げられることが多いものの，元来，この現象と法線マッピングの間には，あまり関連性が無いもののように思われる。法線マッピングによって見た目のデテールが過剰に強調されているがゆえに，アンビエントのみになった場合の凹凸喪失感が一層強くなっている，という勘定ではないかと思う（だから，単純にハイポリを使っても同じような状況に陥るだろうと予想している）。
これについては，以前も GDAlgorithms において Dan Baker 氏が指摘していたように，環境光として半球ライティングを利用するなどの工夫で乗り切ることができるのではないかと思う。……ええと，僕はすっかりボケてしまっていて，この照明モデルに半球ライティングを組み込むことがどの程度のコストになるか見切ることができないんだけれど……恐らくそれほど苦労することは無いだろうと見込んでいる。
本当は，こういった実験をまめに繰り返していきたいんだけど……最近は文字を打つのが精一杯で，どうにもうまく行ってくれない。いつまでたっても国語が苦手科目だ。せめて，１時間あたり二千文字ぐらい打てるようになりたい……。
2003-02-05
眠い……。なんだか知らないけれど，今日はとてつもなく眠い。ソースをちょっと眺めているだけで，たちまち睡魔が襲い掛かってくる。おかげでデバッグがちっとも進まない。ああ，もう……。
プリントアウトを電車の中で眺めていても，すぐに眠たくなってきてしまう。今は，ちょっと前に GDAlgorithms で盛り上がっていた "Game Entities" スレッドを読んでいるところなんだけれど，これがやたら長くて，なかなか読み終わってくれないのだ。
こんな眠たい調子で遅々と読んでいても埒があかないので，飛ばし飛ばしでざっと目を通してみることにした。……うーん，どうやら途中からどんどん論点がずれているようだ。いつの間にか，データドリブン制御のスタイルに関する論争に持ち込まれてしまっている。
Chris Hecker 氏が，高度なシステムを利用してデータ側からの自由な制御・構築を可能とする方向性について盛り上がっているのに対して， Christer Ericson 氏は，デザイナやアーティストがプログラマの手を介さずにある程度の作業が行えるようになっていればそれで十分だとなだめている。前者が「右派」スタイルだとすると，後者は「左派」スタイルかもしれない……などと揶揄しているのは， Ericson 氏自身の言葉だ。
http://sourceforge.net/mailarchive/message.php?msg_id=367516...
偏執的なデータドリブン化の方向性が，技術者の自己満足的性質を含んでおり，作業工程を破綻させる危険性を秘めている，というのは正しい指摘だと思う。ただ，デザイナやアーティストが自力で創造や生産を行うことの出来るようなシステムを構築することは，ゲーム内容を充足させる上で非常に意味のある要素となってきている。偏重は危険だとは言え，この点に関して必要以上に保守的になってしまうことは許されない。
一方で，デザイナやアーティストに対して設計を行う手段を提供することは，同時にバグを埋め込む能力を与えてしまっていることも忘れてはならない。プログラマの手を介さずにデバグを可能にするというポジティブな見方もできるけれど，多くの非プログラマは設計能力に限界があることを認めなくてはいけない（あるいは，設計能力をも備えた「スーパーデザイナ」を養成するか……）。
とまあ，こんな感じで，ある所は右に寄ったり，ある所は左に寄ったり，ってのが昨今のゲーム制作現場の状況のようだ。恐らく最適のパスは真ん中に存在するんだろうと思う。例えば Scott Bilas 氏のプレゼンにある "Dungeon Siege" の例などは，まさに極右に属する類のものであり，決して素人が真似してはならないパターンの一つなのかもしれない。
http://www.drizzle.com/~scottb/gdc/
氏の才能と実力があってこそ，実現が可能となったのだろうと思う。プレゼンの前半には参考になる部分があるんだけれど，後半部分などはただただ感心するばかりだ。こりゃあ真似できないなあ，って類の……。
件のスレッドの後半は，本来の主題をほとんど外れてしまい，単なる応酬戦へと成り果ててしまっているように見える。「emergence とデータドリブン手法の間には相関性があるかどうか」なんて話題で揉めてるし……。なんだかなあ。
ここで登場する "emergence" とか "emergent gameplay" というタームは，日本語に訳するなら「偶発性」とか「偶発的ゲーム性」とでも言えるもので，近年のゲームデザイン手法において重要な意味を占めることになるのではないかと注目されているもののようだ。これについては， Ion Storm 社のゲームデザイナである Harvey Smith 氏が "Deus Ex" のデザイン手法について述べた記事 "The Future of Game Design" の中に詳しく記されている。
http://www.planetdeusex.com/witchboy/articles/thefuture.shtm...
ううむ。 "Deus Ex" って，名前はよく聞くんだけど未チェックなんだよなあ……。各所での評価は非常に高い作品だ。今度，機会があったら購入してみようと思う。
2003-02-06
"Emergent Gameplay" という言葉からまっ先に連想するのは……なんと言っても "Grand Theft Auto III" のことだ。
http://gta3.zoo.co.jp/main.html
Ion Storm の Harvey Smith 氏自身も，同じデザインコンセプトを持ったゲームの例として GTA3 のことを挙げている。
http://www.gamasutra.com/features/20020911/mclean_01.htm
GTA の特徴を論じる際に，どうしても注目を集めてしまうのが，その過激なまでの暴力性についてだ。たしかに，このゲームのカラーを支配している暴力性や犯罪性，それから，自らの自由を追求するという，いかにも「アメリカ的」なスタイルなどは，このゲームを印象付けるための強力な表現として欠かせないものとなっている。しかしながら，このゲームの，ゲームとしての面白さを形作っているものは，もっと他の部分にあるように思える。
例えば，このゲームの「都市生活シミュレータ」的な完成度の高さなどは，多くの人が指摘している所だ。これは以前の GTA シリーズにも当てはまることなんだけれど，このゲームでは， "Liberty City" というひとつの町そのものの有様を，ゲームという枠組みの中で表現することに成功している。
http://www.cityofsound.com/blog/archives/000237.html
http://ps2.ign.com/articles/091/091619p1.html
GTA の世界とは， CPU の中に作られた箱庭のような存在だ。この箱庭は，ある一定のルールに従って動いている（そして，このルールこそが Rockstar Games のデザイナ達が苦心して作り上げたものだ）。実際のゲームプレイでは，ゲームのモチベーションとして数々のミッションやストーリーラインが与えられるものの，「あるミッションのために用意された特殊ルール」というようなものは極力少なくなるようにデザインされている。だから，プレイヤーは，前述のルールに従う限り，どんな方法でもこれらのミッションをこなすことができる。極めて高い自由度と幅広い可能性が与えられているわけだ。
http://www.gamespy.com/editorials/december01/direction/index...
僕がいちばん好きだったのは， Liberty City の構造を把握することが，ゲームプレイ上において重要な意味を占めていることだ。例えば……「たしか，市庁舎ビルの横には細い路地があったはずだから，そこで警察を撒くことが出来るかもしれない」……「図書館から港へ向かうんだったら，最短経路を通るよりも，広くて高速な湾岸線を使ったほうがいいだろう」……「この先のモーテルにトレーラーが留まっているはずだから，それに乗り換えれば，この激しい銃撃に耐えられるかもしれない」……こんな感じで，自由な発想から攻略を組み立てることが許されている。
欧米のゲーマーが特に好むという「発見的な喜び」の要素が，こういった点に結び付いているのかもしれない。
話題に上っていた "Deus Ex" を買ってみようかと調べてみたところ，日本語版は 9000 円近くもすることが判明した。
http://www.eidos.co.jp/title/deusex/DE_top.htm
日本の PC ゲーム市場の現状を考えると，このくらい取らないことにはやっていけないのかもしれないけれど……それにしたって，オリジナルが半額以下で入手できることを考えると，少し辛いものがある。
http://www.amazon.com/exec/obidos/tg/detail/-/B00005B44D/
やっぱ，買うとしたらこっちだなあ……。
2003-02-07
昨日から泊まり……今日，飲み会があることを聞いて，その分の時間を代わりに確保したいなあ，とか，そんな動機で泊まったんだっけ。相変わらず机の下は寒くて，調子が悪くなってしまいそうだ。あまり意地は張らんほうがいいと思う。
昨晩は，「格闘超人が全品回収」という話題が突然舞い込んできて，にわかに盛り上がっていた。決して他人事では済まされない話だけに，みんなの関心は高かったようだ。
http://slashdot.jp/article.pl?sid=03/02/07/1845234
実に微妙な問題だと思う。「再販の予定は無し」との言葉は，作品自体に対する否定とも受け取れる。制作側にとってみれば絶望的な展開だ。ミスの内容からすると少し厳しすぎる仕打ちのようにも思えるけれど，マイクロソフトの立場（と某国の世相）を考えると，こうするのがもっともな解決手段なのかもしれない。
個人的には，ゲーム業界における表現規制の仕組みは，意外と厳しく働いているように思える。出版業界や放送業界のような，手本となる母体が身近に存在していたことが大きいのかもしれない。だからこそ，今回のようなイージーミスがまかり通ってしまったことに対して，むしろ驚きを感じる所があった。
表現規制に関する問題は，倫理やら思想やら社会構造やら……とにかく多種多様にややこしい要素を抱え込んでおり，取り扱いが非常に難しい。堅い言葉で言えば「表現する立場の人間として守るべきこと」としての自主規制もあるんだけれど，集団のビジネスとして運営している以上，純粋なリスク回避として行われる表現規制という考え方も存在する。問題のある表現を行えば，社会的な糾弾を受け，企業としてリスクを負うことになる。だから，表現は規制しなければならない……というわけ。「放送禁止用語」なんて考え方は，まさにその典型例だと思う。
http://members.jcom.home.ne.jp/ksmiracle/Kokugo/Taboo.html
一個人としてこれらの問題に解答を出していくのならともかくとして，集団で対処するとなると，どうしても盲目的な（！）ルールの履行に陥ってしまいがちなのではないかと思う。それでも純粋なリスク回避としてなら十分に機能する……などと考えるのはとんでもない勘違いだ。問題の本質を理解していない限り，本当の意味でのリスク回避を行うことは難しい。現状を見てみても，例えば，少しでも規制コードに触れる語があればすぐさまにそれを改めるのに，内容のバックグランド（ストーリーやキャラクタの設定など）に関しては比較的無頓着であるような風潮が感じられてならない。
「格闘超人」で問題となったのは， BGM の一部にコーランが用いられていたことらしい。禁止用語や特定シンボル（十字架や鉤十字等）のように，目で見て明確に分かる部分ならともかくとして， BGM の音ネタにリスクが潜んでいた，などというのは，チェックの非常に難しいケースであるように思える。このことからも分かるように，ある一定のルールの適用や，機構側でのチェックなどでは，到底カバーできない領域というものが存在する。だからこそ，表現に関わる者の一人一人が義務感を持って対処することが望ましいし，それを常識として浸透させなければならないのだと思う。
とまあ，雇われ人としての理屈は置いといて……個人が個人として表現を行う場合においては，その人の良心こそが規制の基準となるものだと思う。しかし，そんな場合においても，最低限守らなければならないルールというものが存在する。赤十字の標章に関する制限などは，その最も分かりやすい例と言えるかもしれない。
http://www.jrc.or.jp/about/mark/c.html
この理屈はもっともなものだし，守らなくてはならないこととして納得することもできる。法律面からも堅くサポートされており，国際的な常識として通用するもの（通用しなければ困るもの）なのだと思う。
http://www.jrc.or.jp/about/mark/f.html
しかし，こんなの数年前までは余裕で使ってたよなあ……赤十字の描かれた箱を取れば体力回復，なんてのは，ゲームにおける常識だった。今ではこの制限も常識として浸透したようで，例えば "Quake II" などでは……って，あんた！ おもいっきし使ってるし！
http://www.quake2.com/q2wfaq/faq_healthtypes.html#Medikit
やっぱだめじゃん……。
2003-02-08
なんて言うか，今日は普通の休日で……行きつけの本屋にふらっと立ち寄ったついでに，勢いでレッシグの「コモンズ」を買ってしまった。
http://www.amazon.co.jp/exec/obidos/ASIN/4798102040
以前からすごく興味のある本だったんだけれど，あまりの厚さにしり込みしてしまい，なかなか手を出すことができないでいた。中身を覗いてみると，意外と密度は高くないことが分かるものの，ちょっとした辞書ぐらいの厚さはあるわけで……。ハードカバーではないため殺傷能力は持たないものの，ピストル弾ぐらいだったらこれで防げそうだ。何につけても，向こうの人が書く本は厚ぼったくてたまらん。正直なところ，絶対に読み切らないだろうという自信がある。うう。
他にも本を物色していると，こんな本にも目を誘われた。
http://www.amazon.co.jp/exec/obidos/ASIN/4894714086
「省メモリプログラミング」ということで，少ないメモリを効率的に運用するためのデザインパターンについて取り集めた本だ。げーはなさんが紹介していたような気もするなあ……。ともかく，基本的なアイデアは真新しいものではないものの，こういった職人技的なものをきちんと分類し語彙として扱えるようにしておけば，何がしかのメリットが得られるのではないかと思う。
ただ，その本屋に置いてあったやつは，ちょい汚れ気味だったので，結局買いはしなかった。覚えていたら，いつか amazon 辺りで注文してみようと思う。
もうひとつ興味を引いたのは，この本。
http://www.amazon.co.jp/exec/obidos/ASIN/4894717565
Extreme Programming の導入書として有名な Addison-Wesley の "The XP Series" の最終章（？）「懐疑編」だ。 XP に手を出したこともないのに，いきなり「懐疑編」なんてのも変な話だけれど，いままでこういった方法論とは無縁の世界で暮らしていた人にとっては，一歩引いた位置から中立的な立場で覗くという視点が，それなりに重要な意味を持っているように思える。
なにしろ，開発プロセスなんて何も存在しない状態からのスタートだからなあ……。超長期的なスケジュール進行や，節操の無い人事異動が横行しているような状態では，反復によるプロセスの洗練など，非現実的な話のように思えてならない。
http://jibun.atmarkit.co.jp/fengineer/special/cmm01/ccm02.ht...
しかし……「作業の仕方が場当たり的で、ときには混沌的」，「ほとんどのプロセスは未定義」なんてのは，ひどく皮肉な表現だな，と思う。
http://jibun.atmarkit.co.jp/fengineer/special/cmm01/ccm03.ht...
レベル１ですか。とほほ。
2003-02-09
なんとなく気まぐれで，ネットワーク関連の基礎資料を当たってみている。最近はこの手の資料も充実してきたようだ。
まず，ネットワークゲームの基本中の基本テクニックとして挙げられるのが "Dead Reckoning" かもしれない。
http://www.gamasutra.com/features/19970919/aronson_01.htm
"reckoning" という単語には，「測定」とか「計測」とか，そんな感じの意味があり， "dead reckoning" には「推測航法」という用語が当てられている。もともと航測関連の用語であるようだ。
http://www.jal.co.jp/jiten/dict/p295.html
この語源からも分かるように dead reckoning とは，外挿法 (extrapolation) によってオブジェクトの動きを補う手法のことを指している。最後に与えられた位置情報と速度情報から現在位置を推定するわけだ。これに加速度も含めることもあるようだけれど，その分パケット容量が増加してしまうことを考えると，場合によりけりで判断しなければならないだろうと思う。
このテクニック自体は大したものでもなくて，ネットワークゲームにおいてはごく日常的に用いられているものだ。よく FPS 系のゲーム（例えば "Quake III Arena" など）をプレイしていても，先ほどまで直進していたはずのキャラが，突然にワープしてしまうなど，プレイヤーの予期せぬ挙動を見せることがある。これは，通信帯域が狭いあまりに，位置情報の更新頻度が想定よりも低くなってしまい， dead reckoning の誤差が許容量を超えてしまったことから引き起こされる現象だと考えることができる。
ところで，この dead reckoning における「不安定な挙動」を許容することは，実はちょっとした問題を含んでいる。 Umass （マサチューセッツ大学アムハースト校）の Brian Neil Levine 氏の論文 "Cheat-Proof Playout for Centralized and Distributed Online Games" では， dead reckoning の抱える諸問題について詳しく触れている。
http://signl.cs.umass.edu/pubs/baughman.infocom01.ps.gz
http://www.cs.umass.edu/~brian/
例えば， dead reckoning を用いる限り解決不可能な問題の一つとして挙げられているのが "suppress-correct cheat" と呼ばれるものだ。原理はそれほど難しい話でもない。単に，送信するパケットの間隔を「ロード落ち」する寸前のレベルまで意図的に落としてしまうだけだ。こうすることによって，相手プレイヤーから見たチーターの動きは非常に予測し難いものとなってしまう。断続的かつ不規則，ワープなんかも頻繁に発生してしまうわけで，これをレールガンで狙撃しようなどというのはとても無理な話だ。それでいて，チーターから見た相手の動きは通常のものとなっている。これは立派なチートと呼ぶことができるはずだ。
この "suppress-correct cheat" は，原理はとても簡単なものでありながらも，検出することは非常に困難なものとなっている。これが，果たして本当に帯域の制限から発生しているものなのか，それとも不正行為によって引き起こされているものなのか，外からの観測によって知ることは不可能なためだ。原理的なことを言えば，トランスポート層以下の機構に手を加えることによっても実現することが可能であり，そうなるとアプリケーション側から不正を検出することはほぼ不可能となる。チーターがそこまで気合の入ったハッキングを行うかどうかは別問題として，原理的に問題を抱えているということは確実に指摘することができる。
dead reckoning の持つ諸問題は， RTS (Real Time Strategy Game) 等ではもっと深刻な問題を引き起こすことになるかもしれない。さっきまでそこに居たはずのユニットが急に消えてしまったら……あるいは，本当はとっくに破壊されているはずのユニットが，遅延のためにゾンビ状態になっているとしたら……プレイヤーは非常に混乱するだろうし，不公平だと感じることもあるだろう。
僕が RTS にハマっていたのは AOE や StarCraft の辺りだけれど，この頃は，ユニット同士の相互干渉（ダメージや破壊等）以外については dead reckoning がヘビーに利用されていたようで，回線が重いのに混戦状態に持ち込んだりすると，ゾンビ状態のユニットがちょくちょく発生し，無駄な攻撃に時間を費やしてしまうことが度々あったような記憶がある。
結局のところ，前述の論文では， dead reckoning を用いる限り「公平なゲーム」 (fair playout) を実現することは不可能だと結論付け，固定進行法 (lockstep protocol) の導入を勧めている。また，この論文では， lockstep protocol を更に強化することによって，完全に不正の入る余地の無い通信方式を実現しようとしている。
あまり関係ないんだけれど， Umass について馴染みが無かったので調べてみた。 MIT とはぜんぜん別物なのね。
http://www002.upp.so-net.ne.jp/parasa-amherst/amherst.htm
いいところだ……。僕の母校は「キャンパス」というものが存在しなかったものだから（へぼ……），余計こういうのには憧れてしまう。
2003-02-10
前述の論文 "Cheat-Proof Playout for Centralized and Distributed Online Games" の著者 Nathan Baughman 氏は，執筆当時， Umass Amherst 校の SIGNL (The Secure Internet and Group-Networking Laboratory) 研究室に在籍していた。
この研究室は，インターネット上における多対多コミュニケーションとセキュア通信についての調査と研究をテーマとしているようだ。件の論文は，そういった情報通信分野の学術的な見地から見た場合における，現在の一般的なオンラインゲーム通信方式が持つ危うさを指摘し，それに対して耐性を備えたプロトコルの作成を提案するものとなっている。
http://signl.cs.umass.edu/pubs/baughman.infocom01.ps.gz
また，同研究室が group networking をテーマとしているためか，この論文では分散型モデルを主体として扱っているような風がある。原理的にはクライアント−サーバモデルにも適用可能なものだけれど，分散型の利用を考えている場合には，特に参考になるのではないかと思う。
この論文では，まず，従来の通信方式が看過していた潜在的な危うさと， dead reckoning 手法が抱える各種問題について触れている。それは，前述の suppress-correct cheat の問題であったり，相互干渉処理の破綻ケースの問題であったりする。これらの問題はゲーム内容に対して直接的な影響を与えるものではないけれど，「不公平 (unfair) な」状況を作り出してしまう可能性を持っている。そして結論として，これらの問題を根本的に解決するには，逐次停止型プロトコル（全クライアント間でターン毎に同期を取る方式）を導入するしかないとしている。
しかし，単純な逐次停止型プロトコルにも穴はあるようだ。この方式では，ゲーム進行のタイミングが処理の最も遅いクライアント（パケットを最後に送信したクライアント）に縛られるという制限がある。ならば，常に最後のクライアントになるように，わざと送信を遅らせれば良いのではないか……ということだ（著者はこれを "lookahead cheat" と呼んでいる）。要するに「後出しジャンケン」のようなものだと言えば分かりやすいかもしれない。
この "lookahead cheat" によって，具体的にどのような不正が可能になるかは，ゲームの内容に大きく依存するし，むしろ問題にならない場合も多いと思う。……他にもこの論文では，ちょっとパラノイアックな風に受け取れる部分が少なからず存在するんだけれど，こういった小さな可能性も漏らさず逐次検証していくことが，インフラとして大切なことなのかもしれないと思う。
それで，結局のところ，この論文では， "lookahead cheat" への対策として "lockstep protocol" を導入することにしている。原理は簡単で，まず最初に各クライアントにおける決定内容をハッシュキー化して交換し，全員の同期が取れたところで，改めて決定内容を交換し合う，というものだ。もし「後出し」行為があれば，決定内容とハッシュキーの間に差異が生じるはずだから，そういったチートの可能性は防ぐことができる，というわけだ。
2003-02-11
lockstep protocol のような逐次停止方式を導入する際に最も問題となるのが，ゲーム進行速度の低下の問題だ。 lockstep protocol では，ターン毎に全クライアントに対して同期を要求するため，進行速度が最低の条件に縛られてしまうという欠点がある。例えば，あるクライアントが一瞬処理落ちしたり，ある通信路が一瞬重くなったりしただけで，ゲーム全体がもたついてしまう。この「もたつき」が発生する確率はクライアント数の増加に伴って高くなるから，多数のクライアントが相互接続するような場合においては，非常に深刻な問題となることが考えられる。
同論文では，逐次停止方式の持つ制限を部分的に緩める方法として AS - "Asynchronous Synchronization" という同期方式を提案している（つまり「非同期型同期方式」……奇妙なネーミングだ）。この "AS" では， SOI - "Spheres of Influence" という，あるゲーム要素が影響を及ぼす範囲について単純化したモデルを導入し，この SOI 集合同士の重なり判定を取ることによって，同期の適用範囲を狭めることができるとしている。
SOI 自体は，非常に単純な範囲情報であり……端的に言ってしまえば，ただの球の集合だ。ただし，単に半径と位置情報だけではなく，毎フレームにおける許容移動量として「デルタ値」を持たせるようにしている。これによって，相手方の完全な SOI 情報を持っていない状態においても，影響範囲の推定を行うことが可能となっている。単純にデルタ値を半径に加算してやれば，未来の時点における最大の可能性としての SOI 集合を導き出すことができるというわけだ。
これは重要なポイントで， AS 方式の非同期性を高めることに貢献している。 SOI の重なりが検出されない限りは，各クライアントにおいて独自の時間軸を保持し，非同期状態でゲームを進行させることが可能となるわけだ。そして，重なりの可能性が検出された場合には，改めて正確な情報を交わし合うことになる。その結果として lockstep の必要性が見出されたならば，そこで初めて完全な同期を取り始める……といった流れになる。
また，未来の時点における SOI が推定可能なことは， SOI 情報の取りこぼしを補うためにも役立てることができるようだ。これにより， SOI 自体は信頼性の無い (unreliable) 通信方式で交換することが可能であり，必要とされる負荷量を最低限のものに抑え込むことが実現されている。
前述のように， lockstep protocol において最も問題となるのは，ゲーム進行速度の低下の問題だ。これを改善するために AS 方式を提案しているわけだけれど，果たして実際にどの程度改善されるものなのか，という所が焦点になってくる。同論文では，オープンソースのネットワーク対戦ゲーム "Xpilot" に対して実際に AS 方式を導入してみることによって，アプリケーションにおけるパフォーマンス変化量の測定を試みている。
Xpilot の仕様上の問題や（あまりクライアント数を増やせないらしい），果たして Xpilot が分散型ネットワークゲームの例として相応しいものか，という疑問は残るものの，それなりに説得力のある実験にはなっているかと思う。結果を見れば， SOI を利用した AS の導入によってある程度のパフォーマンスの改善が実現されていることが分かるはずだ。
結果的なことを言えば……ある通信方式における，潜在的なチートに対する耐性と，体感するパフォーマンスとは，トレードオフの関係になっているようだ。チート耐性を強めれば強めるほど，非同期処理で進められる場面は狭まっていき，通信路の状態や各クライアントのもたつきが顕著に影響を及ぼすようになってしまう。それを軽減するために提案された AS 方式も，ほとんどの SOI が重なり合ってしまうような「混戦」状態では，ほとんど効果を発揮できなくなってしまうのではないかと思う。
……というように，潜在チート対策に対してネガティブな印象を持ってしまうのは，昨今のネットワークゲームが，これらの問題に取り組まなくてはならないほど洗練された状態にはなっていない，というのが理由として大きいのではないかと思う。基本的なセキュリティの強化や，平均的なパフォーマンスの改善など，もっと先に解決すべき問題が山積みに残されているような気がしてならない。
http://slashdot.jp/article.pl?sid=02/10/17/152211
2003-02-12
一昨日，昨日と，暖かい日が続いていたものだから，すっかり油断してしまっていた。もう，今日の冷え込みようと言ったら，昨日までの陽気をまるで無視するかのような勢いだ。うう，寒い……。
何故か腹の調子が芳しくない。休日は松屋の牛丼しか食っていないというのに……。牛丼にあたった？ そんなはずは……はあ。
そんなわけで……，対チート性を高めようとすればするほど，どうしても同期の回数が増えてしまう傾向にあるようだ。この手のストリーム処理では，非同期処理を上手く使いこなすことが，途切れの無い進行を実現する上での鍵となるのではないかと思う。それなのに，このように逐次同期を要求されたのでは，たまったものではない。結果として，ゲームの滑らかな進行が寸断されてしまう恐れが出てくる。
ナローバンドにおいても快適なマルチプレイを実現した "Diablo" は，発売してしばらくした後に，悪夢のようなチート地獄に襲われることになってしまった。元々ローカルエリアでのプレイを意識していたであろう分散モデルの設計が，コミュニティベースのマルチプレイヤーゲームとして保証すべき信頼性を保証する所まで達していなかったからだ。ここでの失敗を踏まえて，チート耐性を格段に強めたはずの "Diablo2" は，今度は逆に，ネットワークのもたつきを顕著に感じさせるゲームへと変貌してしまっていた。
今や時代はブロードバンドなわけで，状況は当時と明らかに異なるんだけれど……ゲームプレイの快適度と信頼性のトレードオフという話に着目すると，つい，そんな昔話を思い出してしまう。
ふと立ち寄った本屋で， Interface 増刊「リアルタイム/マルチタスクシステムの徹底研究」を購入してみた。今回のような話も含めて，比較的ローレベルな部分のシステムを設計する際に，何かインスピレーションとなるものが得られるかもしれないと思ったからだ。
http://www.cqpub.co.jp/hanbai/books/523010.htm
組み込みシステムにおけるマルチタスクの話など，参考になる点が多くあるように思える。しかし，実際に本を開いてみると，どうも興味が湧いてこない。果たして，僕の読み方が悪いのか，それとも本の内容が悪いのか……。題名だけ見るとすごく面白そうに見えるだけに，そのギャップが不可解に感じられる。
本の全体を通して，表層的な部分をさらっと流すことに主眼が置かれており，実はとっかかりの部分しか紹介されていない，というようなきらいが感じられなくもない。実用面で活かそうと思うのならば，まずは参考文献を当たって深く掘り下げてみないことには，どうにも始まらなさそうだ。
現在のトレンドを何となく把握する，という意味では，参考になる部分が少なからず存在するかもしれないと思う。
2003-02-13
出社前に新宿のヨドバシへ寄って， Anubis (ZOE2) を購入した。
http://www.konamijpn.com/products/zoe2/japanese/
いつの間にかポイントが貯まっていたようで，ポイントだけで購入することができた。液晶ディスプレイを購入したときのポイントがいまだに余っているのかな……。
いかにも平日の午前らしく，店内は閑散としたものだった。明日は GBA SP の発売日ということで，もうちょっと活気に満ちた感じになるかもしれない。
http://www.nintendo.co.jp/n08/hardware/gbasp/
初期出荷台数が少ないとの噂をどこからか耳にした。きっと即日完売だろうなあ……。早く触ってみたいのだけれど，実際に手にするのは，もうちょっと先のことになりそうだ。
spin の更新が相変わらず激しい。最近では，もうすっかりニュースの部分がメインとなってしまった感がある。
最近のニュースの中で特に興味を誘われたのは，因数分解による Ashikhmin BRDF のハードウェアレンダリングの話題と， Jakko Lehtinen 氏の "Matrix Radiance Transfer" の話題だ。
Ashikhmin シェーダの方は，ちょっと前に読んだ "Making Shaders More Physically Plausible" からの流れで興味を誘われるものがあった。
http://www.cs.ubc.ca/labs/imager/tr/lewis.1994a.html
ところで，この "Ashikhmin BRDF" という名前は，初めて聞くもののような気がする。どうやら，元ユタ大の Michael Ashikhmin 氏によって開発された反射モデルのことを指す名称であるらしい。
http://www.cs.utah.edu/~michael/
ちなみに，氏は現在 Stony Brook University の Computer Science Department に在籍し，助教授を務めている。
http://www.cs.sunysb.edu/~ash/
Ashikhmin の反射モデルは，基本的には Phong モデルなどと同じく現象的モデル (phenomelogical model) に属するものなんだけれど， BRDF としての「正しさ」をカバーしている所が特徴として挙げられる。つまり，エネルギーの保存則や，ヘルムホルツの相互律など，物理モデルとしての「正しさ」の条件を満たしているということだ。また，異方性反射やフレネル効果など，今となっては欠かすことのできなくなった各種効果も取り揃えている。それでいて Phong モデルのような扱い易さを備えているというのだから，否が応でも興味を誘われるものがあると思う。
この反射モデルは，本当に完全な現象的モデルが元となっているようで，論文の中には物理的な理由付けがほとんど出てこない。拡散式の中に出てくるマジックナンバー "28 / (23 * pi)" なんて，妙にこじつけっぽくて思わずニヤリとしてしまう。結局のところ，実測値を用いない場合のマテリアルデザインにおいては，アーティストにとっての扱い易さこそが重要なポイントとなるのだろうと思う。 Ashikhmin のモデルとは，そういった要素を重視したモデルと考えることができるのではないかと思う。
"Matrix Rdiance Transfer" の方は……うう，難しい。まずは PCA (Principal Component Analysis) を調べてみようか……。
http://cis.paisley.ac.uk/mcdo-ci0/PCA.htm
時折耳にする単語なんだけれど，嫌な香りが漂ってくるので（数値解析っぽい話は鬼門なのだ……），あえて目を逸らしてきた。 PCA とか FEM とか，いつか恐れずに使えるようになりたいねえ。
2003-02-14
気の抜けた金曜日。案の定，GBA SP を入手した人は誰もいなかったようだ。
http://www.watch.impress.co.jp/game/docs/20030214/gbasin.htm
職場に放置されていたお古の PC をひっくり返して，おもむろにソフトウェア RAID の実験を始めてみた。
http://unthought.net/Software-RAID.HOWTO/Software-RAID.HOWTO...
http://www-6.ibm.com/jp/developerworks/linux/010427/j_l-raid...
http://www-6.ibm.com/jp/developerworks/linux/010518/j_l-raid...
Linux kernel 2.4 以降ではソフトウェア RAID のサポートが標準的なものになっている。今回は HDD の信頼性を上げることが目的なので RAID-1 （ミラーリング）がターゲットだ。適当に howto の手順通りに進めてみると，あっという間に RAID が構築された。思ったよりも簡単なもんだなあ……。
ソフトウェア RAID での RAID-1 は，書き込み時に単純計算で２倍の帯域を利用するため，バスのスループットがネックとなってしまうことがあると指摘されている。確認のために，大量の書き込みリクエストを行ってから sync までの経過時間を計測してみたのだけれど，それほどの速度の低下は見られなかった。少なくとも，体感できるような速度低下は無い。
以前は IDE RAID デバイスを利用したハードウェアベースでの RAID 構築や，外部接続の RAID ストレージを利用することを考えていたのだけれど，ソフトウェア RAID がここまで高速に動作してくれるとなれば，これでも十分事足りるかと思えるようになってきた。業務上重要なデータを保守するわけでもなく，単にワーキングディレクトリ（各種設定ファイルとか）の損失を防ぎたいだけだからね……。その程度の用途であれば，何かと制限の付きまとうハードウェア RAID よりも，「とにかくパーティションが２つあればなんとかなる」的なソフトウェア RAID の方が，何かと選びやすいのではないかと思う。
家に帰ってからは Anubis をプレイ。ものすごい密度のゲームだ。久しぶりに 3D 酔いしてしまってクラクラする。目が回るってば……。
2003-02-15
一日中 Anubis をプレイ。１周目は６時間程度で終了して，今は２周目とエクストラミッションを探索しているところだ。やり込み要素を用意しておくことで不足気味のボリュームをカバーしようという試みのようで，それなりに長く楽しめるような作りになっている。ていうか，ゾラディウス……。
そんなわけで，だいぶ不健康な日だった。目が痛い……。
2003-02-16
ウェブでネタ情報を集めながら， Anubis をまったりとプレイしていた。もうそろそろお腹いっぱいかな，と思う。
結局のところ，１周で約６時間，２周目とやり込み要素をちょっと消化して１０時間程度，ってのがプレイ時間の目安になると思う。恐らく，ボリュームに関する不満が最も多く噴出するものと思われるけれど，その分密度は濃いものとなっているわけだし，逆にそれ以外の不満点を見つけ出すことも難しいかもしれない。
とにかく，現時点で最高の密度を誇るゲームなのではないかと思う。少なくとも，僕が遊んできたゲームの中では，最も高密度で高品質なゲームだと言い切ることができる。全編を通して無駄に思える部分がまったく存在しないほどにシェイプアップされたゲーム内容は，プレイヤーから中断のタイミングを完全に奪い取ってしまうのではないかと心配してしまうほどのものだ。
言うまでもなく，演出面の技術力は現時点で最高のレベルに達している。映画的な技法を取り入れ洗練されたカットシーン演出と，驚異的なプログラム技術から生み出される特殊効果の数々は，プレイヤーの目を常に捕らえて放さないものとなっている。 PS2 の機能を最大限に引き出していることはもちろん，下手にケチることなくとことんまでリソースを注ぎ込む強気の姿勢が，凡庸なビジュアルからの脱却を果たしているように思える。「質」だけではなく「量」の点でも驚きをもたらされる所が， MGS2 までとの違いと言えるかもしれない。
前作を悶えながらプレイしていた身としては，シナリオ面にも評価すべき点があると思う。前作 ZOE や MSG2 のような，どこか破綻してしまったストーリーとは違い，非常に良くまとめられたシナリオが展開されている。キャラクターの描写が安定しており，物語の根底を流れる主題も一般性の高いものとなっていることから，素直に感情移入することができるようになっているのではないかと思う。また，シナリオ面と関連して，セルアニメーションとの融合という新しい試みを無難にクリアしてしまっている点にも注目したい。
最後に，隠れがちだけれど重要なファクターとして，サウンドにも注目を当てたい。場面を盛り上げる優れた BGM 群は，様々なジャンルと無国籍風に彩られており，このゲームの雰囲気を決定する要素として十分な効果をもたらしているように思える。アクションシーンのアップテンポな BGM 群は非常にキャッチーだし，カットシーンの演出と効果的に連動した BGM はまるで映画音楽のようだ。独創的な効果音の数々も，迫力や爽快感を演出する要素として非常に効果的な役目を果たしている。
そう言えば， ZOE や MGS シリーズでは，ほとんどの BGM を内蔵音源のシーケンスによって実現しているようだ。ポーズしたときなどに，微妙にリリースが残ることから伺い知ることができる。全体的に言ってシーケンスの質は非常に高く，この手掛かり（リリースが残ること）さえ無ければストリームだと勘違いしていたことだろうと思う。
更に，前作 ZOE では，戦闘状態と平常状態においてミキシングを動的に入れ替えるという演出を行っていた（ちなみに，この演出は本編仕様の変更から今作では無くなってしまったようだ）。平常状態ではオーケストラルで落ち着いた BGM が，敵機の接近に伴ってリズムセクションが入り込み，アグレッシブな BGM に変化するという仕掛けだ。内蔵音源によるシーケンス方式だと，こういった応用を効かせやすいのが面白いところだと思う。
しかし，制作コストの点で言えば断然にストリーミング方式の方が優れていることから，最近ではストリーミング方式を優先することの方が多くなったように思える。現行のハードウェアならば，ストリーミングを行うのに十分なロード速度とマシンパワーを備えているのだから，なおさらのことだ。前述のリアルタイムミキシングのような技法だって，マルチチャネル・ストリーミングを利用することで解決可能だろうと思う。現状では多少の懸念材料が残っているとしても，次世代こそはストリーミング方式が標準的な方法になるものと踏んでいる。
しかし， PS2 が出た頃にも「これからのカットシーンは全部 MPEG になる！」とか騒いでいたことを考えると，やっぱりなんだかんだ言ってシーケンスがいいよねー，ってことになるのではないかと危ぶんでいる。まあ，それはそれで面白いからいいけどね……。やはり，無制限にストリームを垂れ流しってのも，やけに味気ないものだと思うのだ。
2003-02-17
ゲーム制作やリアルタイムＣＧに関わったことのある人なら大抵が知っていることだけれど，標準数学関数ライブラリ (math.h) に含まれる sin や sqrt などの数学関数は，非常に動作が重い。場合によっては深刻な問題を引き起こすことが考えられるほどのものだ。これは，これらの関数が応答速度よりも精度に重点を置いていることに起因している。もともと数値処理のために作られたものなのだから，いくらゲーム屋さんが悪態をついたところで，どうしようもない問題なのだろうと思う。
従って，大抵のゲーム屋さん（リアルタイムＣＧ屋さんも含む）は，自力で高速な数学関数ライブラリを作成するか，あるいは出来合いのものをどこかから引っ張ってくるか，あるいは気付かないフリを決め込むか……とにかく，いずれかの手段をとらなくてはならない。 x86 系の CPU を扱っているのならば， NVIDIA の "Fast Math Routines" を使うなんてのは，なかなか良い解決案かもしれない。
http://developer.nvidia.com/view.asp?IO=fast_math_routines
ここで自作する方を選ぶとなると，テイラー級数を用いた近似式の応用や，オフライン処理によるテーブル化などを利用することになるんだけれど，なにしろ用途が特殊なだけに，参考にすべき資料が見つからなくて苦労することが多い。適当な多項式やテーブルを利用すれば速くなることは確かだ。しかし，「これで本当にいいんだろうか」という，うっすらとした不安が常に付きまとうことになる。少なくとも僕の場合はそんな感じだ。
SCEA (Sony Computer Entertainment America) の研究開発部門に所属する Robin Green 氏の論文 "Faster Math Functions" は，そんな悩みに対して明確な答えを与えるものになるかもしれない。
http://www.research.scea.com/research/pdfs/RGREENfastermath_...
これは GDC (Game Developers Conference) 2002 において Green 氏が行った同名のレクチャーに基づくものだ。
https://www.cmpevents.com/GDx/a.asp?option=C&V=11&SessID=484
ちなみに SCEA の研究開発部門では，この他にも基礎研究の一部をウェブサイト上で公開している。
外部の組織（主に大学の研究室）と合同で研究を行っているものも多いようだ。日本の SCE では，こういった基礎研究は行っていないのかな……。 PS2 Linux 以降，あまり楽しげな話を聞かないような気がする。
件の論文では，三角関数の近似を例にとって，高速かつ正確に動作する近似関数をデザインする手法について解説している。三角関数の近似と言えば，なんと言ってもまず，単純なテイラー級数（マクローリン級数）による近似が思い浮かべられる。
http://mathworld.wolfram.com/MaclaurinSeries.html
例えば， sin 関数の展開式を７次までで打ち切った近似式は，次のようなものになる。
しかし， Green 氏の指摘によれば，この式の係数を以下のように変更するだけで，格段に精度を上げることが可能であるとしている。
実際に誤差を測定しプロットしてみると，本当に精度が上がっているのだから驚きだ。
この論文は，上の例が顕著に表しているように，ほんのちょっとの数学的な「手抜き」が大きな誤差の元となっていることがある，という事実を指摘する内容となっている。逆を言えば，ほんのちょっとの工夫で精度を上げることのできる余地が，まだ方々に残っているんだということを思い知らせてくれる，というわけだ。
少なくとも，僕の場合は大いに思い知ることになったわけだ。
2003-02-18
昨晩からの泊まり作業で空ききった腹を埋めるべく， "Pret" こと「プレタ・マンジェ」に向かう。
ここのサンドイッチは，やけに高いことで有名なんだ……。相応に品質が良いとは言え，サンドイッチ１パックに５００円も払うのは，やはり何か腑に落ちないものがある。一緒にコーヒーを頼んだら確実に８００円オーバーだ。赤坂とかならともかく，庶民の町こと中野に来られてもねえ，って気がしてならない。
この無謀とも思える価格設定も，やはり物価高騰都市の成せる技なのかなあ，などと考えていたのだけれど，実は本家の英国でも同程度の価格帯が設定されているようだ。
http://www.pretdelivers.com/lunch_menu.htm
値段が値段だけあって，味は確かなものだし，「食材へのこだわり」といううたい文句にも偽りは無いのだろうと思う。しかし……やはり，僕が気軽に通えるような店でないことは確かだと思う。
"Faster Math Functions" の，前述の例における「種明かし」は， minimax 多項式を用いた近似法（Chebychev 近似）にある。数値解析のことはよく分からないので，いまいち詳細については掴みかねているのだけれど……とにかく，計算機数学では日常的に利用されている近似法の一つであるらしい。 minimax という名が表しているように，最大誤差を最小に保つ (minimization of the maximum error) という特徴を持っている。
http://www.ifp.uiuc.edu/~lqian/Research/Papers/minimax.pdf
http://www.library.cornell.edu/nr/bookcpdf/c5-8.pdf
http://mathworld.wolfram.com/ChebyshevApproximationFormula.h...
この辺り，ちょっと調べてみたところで，さっぱり理解できない。学校でこういうのやらなかったからなあ……。
minimax 多項式を求めるのに使われるのが "Remez Algorithm" というものらしいんだけれど，これもまったく分からない。
http://mathworld.wolfram.com/RemezAlgorithm.html
本来なら，この時点でかなり絶望的なシチュエーションだ。しかし，当の Robin Green 氏も，この手法の詳細についてはあまり触れずに，適切な道具を用いて対処することを勧めている。
Maple には，まんま "minimax" という関数が存在するらしい。ああ，そんな楽ちんな。
http://www.wolfram.com/products/mathematica/
まあ，その辺りは気にせずにガンガン使ってこうよ，ってことみたいだ。僕は Mathematica 持ってないけどね……。
2003-02-19
そんなわけで……三角関数については minimax 近似を用いることで精度の向上を望めることが分かった。もし，三角関数にこれ以上の精度を求めてはいない，というのならば，トレードオフで速度を獲得すればいいだろうと思う。なんにしろ，ほとんど同じ手間で性能を向上させることができるのだから，知っていて損はないはずだ。
ただし，少し残念なことに，件の論文には範囲 [ -pi/4 : pi/4 ] における sin 関数の minimax 近似式しか載っていない。 pi/4 間隔でのレンジ圧縮を用いることを前提としているからだ。この式から値域全体をカバーするには，三角関数の加法定理を用いるべしということなんだけれど，これは即ち sin, cos の両関数を揃えていることが前提となる。
結局のところ， cos 関数の近似式を自力で求めないことには， sin 関数の近似さえままならないということだ。ううむ，できれば論文に載っている式を丸写しで済ませたいと思っていたのだけれど，そういうわけにも行かなくなってしまったようだ……。
もちろん，手元に Mathematica さえあれば，論文と同様の手法で cos の minimax 近似式を求めることができるに違いない。しかし悲しいかな，肝心のソフトは僕の手元に存在しない。買おうたって，とても気軽に手を出せるような価格ではないのだ。
http://www.wolfram.com/products/mathematica/index.html
だからといって， minimax 近似を行うプログラムをわざわざ自作するのも面倒そうだしなあ……うう。
もし，運良く身近に Methematica を持っている知人がいる場合や，あるいは，手早く調達可能なポケットマネーを３０万ほど所持している場合には，それを利用して解決するのが手っ取り早い。不幸にもそうでない場合は， GNU Octave に頼ってみることが，良い解決法となり得るかもしれない。
GNU Octave は，各種の数値演算を行うソフトウェア・パッケージだ。 MATLAB 互換のスクリプト言語を利用して，実験室的なデータ処理や数値解析を行わせることができる。そう言えば， MATLAB なんてのも使ったことが無いな……。
http://www.mathworks.com/products/matlab/
Octave には "polyfit" という，任意のデータ列から任意次数の近似多項式を導出する関数が用意されている。もしかしたら，これを利用することができるかもしれない。
http://www.octave.org/doc/octave_25.html
ただし，この関数は，単純に平均誤差値を小さくするようなアルゴリズムを利用しているようだ（詳細については分からなかった）。これに対して minimax 近似には，重み付け関数を与えることで全体的な相対誤差値を減らす働きがあるらしい。それと比較したら，恐らく polyfit の近似は多少貧弱なものになってしまうのではないかと思う。
ううむ，まあ，この際，背に腹は替えられぬのだけど……。
この GNU Octave は，完全に無料ながらも相当に高度な機能が利用できることから，教育機関などでよく利用されているようだ。 google で単純に "octave" と検索してみれば， ac.jp 関連のページを多く見つけることができる。今回の用途のように軽く利用する程度であれば，ここから得た情報で十分にまかなうことができるはずだ。
http://www.google.co.jp/search?num=50&lr=lang_ja&q=octave
これを参考にして適当なスクリプトを捻り出して……と。そんな感じで，あっという間に作業は完了した。ううむ，こんな便利なツールもあったものか……。
2003-02-20
色々と近似関数を作った仕上げとして， Gnuplot を使って誤差値のプロットを取ってみることにした。
Gnuplot ぐらいになると，僕もさすがに使ったことがある。操作方法はほとんど忘れてしまったけどね……。オンラインヘルプ（これが意外と充実している）や "gnuplot tips (not so Frequently Askked Questions)" を参考にしつつ，微かな記憶から使い方を思い出してみた。
http://art.aees.kyushu-u.ac.jp/members/kawano/gnuplot/
Gnuplot なんて言うと，あまり飾り気の無いグラフばかりを出力するような印象がある。もとが学術向けなだけに，どうしてもストイックな内容になってしまうのかもしれない。それでも，細かく設定を行うことによって，それなりに凝ったグラフを生成することが可能なようだ。
http://art.aees.kyushu-u.ac.jp/members/kawano/gnuplot/galler...
最近の gnuplot は png 形式での出力もサポートしている。 HTML などでドキュメンテーションを行う場合は，この機能を利用するのが最も手軽な方法だ。ただし，見栄えを追及するならば，やはり postscript での出力が優れている。 dpi を上げた状態でビットマップ変換を行い，それから縮小をかけるようにすれば，アンチエイリアス効果を狙うこともできる。
画像の変換には，画像処理ツール集としてお馴染みの ImageMagick を使う。
これらのコマンド群を覚えておくと，とっさにバッチ加工を行いたい場合などに便利だ。例えば今回の場合なら，こんな感じになる。
長いシェルコマンドが一発できまると気分がいい。なんだかんだ言って，いまだにシェルに頼る機会は多いような気がする。少しでも複雑な処理になると perl や python の出番になるんだけれど，ちょっとしたバッチ処理ならばシェルの方が使いやすい。 sed や awk と引用符を妙に使いたがるようになってきたら，立派なシェル中毒と言えるかもしれない。
2003-02-21
今日も大して進まなかった作業のことを悔やみながら，寝袋の中に入って短い休息を得ようとしている。最近は寝ようとしてもなかなか寝付けないことが多く，それがつい夜更かしをしてしまう原因となっている。暗闇の中で目を閉じて横になっていると，何故か不安なイメージばかりが頭の中に入り込んでくる。この数年間で，急に心だけが老けてしまったんだろうか。身体上の衰えを感じることは何も無いけれど，考え方がどんどん暗くなってきたような気がする。
常に自分の上にタスクを積み上げておかないと落ち着くことが出来ないのも，そんな心理状態なのが原因なのかもしれないと思う。常に仕事や勉強で心が煩わされていれば，自分の事を考えなくても済むようになる。嫌なことばかり考えている間は，もっと嫌なことを忘れていることができる。
疲れた体を寝袋の中に横たえている間は，不思議と落ち着けることができる。自分は努力しているんだと思い込むことが，この上ない励みになることがある。自分が人よりも恵まれていないと思い込むことで，自分自身を慰めることができる。自己憐憫は蜜の味だ。安っぽいペシミズムが自分を孤高の存在へと変えていく。本当は単に悦に入っているだけなのに……。そうやって，徐々に人との接点が薄らいでいくことに気付こうとしない。鏡の向こうに見える自分の存在さえ透けて見えるような気がする。
そんな妙な妄想も，一晩の眠りがすべて吹き飛ばしてしまうのだから不思議だ。きっと明日になれば全て忘れて元通りになっているに違いない。そう思って気を楽にすれば，やがて眠りにつくことができる。
だから，たぶん，早く寝た方がいい。こんなことを考えているよりも，もっと早く寝て，起きて，多くの時間を有用に使った方がいい。その結果が自己満足であれ何であれ，下らない妄想に頭を悩ませていることと比べれば，ずっと意味のあることなのだから。
2003-02-22
謎の会合に出席すべく渋谷に移動。軽く雨が降っている。寒い。
久しぶりにお好み焼きなど食しながら，これまた久しぶりに酒を飲むことになった。相変わらずアルコールはダメだ。飲んでしばらくすると，顔の赤らみと共に，風邪をひいたときのような症状が出てくる。頭がズキズキして，末端が痺れてきて，腰が重くなってきて……全然いいこと無しだ。
酒を飲みながら話したことと言えば……うう，いろいろあったと思うんだけど，全然覚えていない。カシスソーダを一杯飲んだ後はもう，ずっと上の空だ。過去の統計データと身体的特徴から人格の推定を行う手法についての話だっけ……。手に付いた線が長かったり短かったりすると，長生きしたり早死にしたりするんだ。面白い。
その後二次会があったみたいなんだけれど，とても参加できる具合ではなかった。ズキズキする頭を抱えながら，命からがら逃げ帰ってくることになった。いやあ，ネコに餌をあげなきゃいけないから，帰らないとダメなんですよ。そのネコってのがね，蓋を開けてみると死んだり死ななかったりするんで大変なんですけどね……とかなんとか。
帰ってからも，アルコールの症状が酷くて，何もまともなことを出来ぬまま，しまいには眠りこけることにした。
2003-02-23
C++ において，クラスや関数の利用を翻訳単位の中にとどめるために，無名名前空間という機構を利用することがある。
クラスに関しては，この利用方法が適切であることは明らかだ。でも，関数の場合はどうなんだろうか，と考えてしまうことがある。 C にはもともと静的リンケージ (static) という機構があるわけだし，これは C++ にも継承されている。どちらも同じ目的を達成することは想像に難くないけれど，果たしてどちらを用いるのが「より適切な」方法と言えるんだろうか。
サーチなどで軽く調べてみると，だいたい次のような結論に落ち着いていることが分かった。
http://www.mvps.org/windev/cpp/nspaces.html
つまり，とりあえず static のことは忘れて，スタイルの問題として無名名前空間を選択することにしましょう，ってところかなあ。まあ，特に異論は無いからいいけど……。
そう言えば，翻訳単位と関連する問題で，もう一つ気になることがあったのを思い出した。インライン関数の中に置かれた文字列の扱いについての問題だ。
GCC 2.9x 系では，インライン関数内に実装されたデータ（文字列）が，そのインライン関数が使用されている如何に関わらず，オブジェクトファイル内に混入してしまうという，ちょっとバグっぽい挙動が存在していた。
例えば次のようなソースを例にとってみると，よく分かる。
実質的なコードは一切存在しないのだけれど，文字列だけが混入してしまっている。
これはつまり，例えばインライン関数内で printf など使用すると，そのヘッダをインクルードしたソースすべてについて，その文字列の複製が無条件に生成されてしまうことを示している。たとえ一つ一つは小さな文字列でも，ファイルが増えれば増えるほど複製されてしまうというのは困りものだ。特にインラインを酷使しがちな C++ では問題となりやすいのではないかと思う。 boost のようなライブラリを利用する場合は注意する必要がある。
MIPS 系では，短い文字列が short data section に別途格納されるという仕様があるため，ここのオーバーフロー（仕様上 64kB に制限されている）から問題が露見することがあった。
http://gcc.gnu.org/onlinedocs/gcc-3.2.2/gcc/MIPS-Options.htm...
新しい技術を導入する際に最も恐れているのが，この手の，プロジェクトが巨大になった時に初めて露見する類の問題だ。クラスライブラリなんて，できれば内部のことを知らずに扱いたいものなのだけれど，どうしても内部構造について調べなければならない理由が，この辺りに存在してしまっているような気がする。
この問題は， GCC 3.x 系では改善されているようだ。
そういうわけで，これからは安心してインライン関数内で文字列を使うことができる。しかし逆を言えば，これでまた一つ GCC 2.9x 系を使えない理由が増えてしまったわけだから，あまり喜んでばかりもいられないような気もする。例えば，ゲーム向け開発環境の整備で有名な SN Systems は GCC 2.95 系を堅持することを主張しているし，同様の態度をとっている所も少なくないようだ。
https://www.snsys.com/PlayStation2/ProDGFAQ.htm#t3
まあ，内部のヤバさを知っているからこそ，移行できない理由ってのもあるんだと思うけどね……。しかし，絶え間ない変容を許容できることこそが GCC の存在意義の一つであるとしたら，それに乗っていかない手は無いのではないかと思う。末端の開発者の勝手な言い分としては，そんなところだ。
2003-02-24
昨日の一件が少し気になって，某コンパイラでも試してみることにした。……ううむ，やはり C では件の症状が出るんだけれど， C++ ではそれが無くなっている。 GCC 2.95 から 2.96 の間に改善されたんだろうか。いやむしろ， GCC 2.96 なんてバージョンは存在しなかったはずだ。
http://gcc.gnu.org/releases.html
なんだか混乱してきた……。しばらく落ち着いて調べてみると， "GCC 2.96" は「とあるベンダ」が自作のカスタムバージョンに対して勝手に与えた呼称であるらしいことが分かってきた。
http://gcc.gnu.org/ml/gcc-announce/2000/msg00003.html
そんなわけで，一昔前の Red Hat Linux には "GCC 2.96-RH" とかいう不思議なバージョンの gcc がインストールされている。ちょうど Red Hat が Cygnus を買収した頃の話かなあ，と思う。
http://www.redhat.com/about/presscenter/1999/press_cyg_merge...
誇り高き白鳥が一瞬にして赤帽おじさんへと変化してしまったのは，ちょっとショッキングな事件だった。いや， Red Hat もいい会社だと思うけど……。
Minimax 近似について， jiro さんと，げーはなさんからご教授を頂いた。有り難いことです……。そこで山のような参考文献リストを頂いたものの，とても全部を読んでいるわけには行かないので，およそ手っ取り早いのから手を付けてみようと思っている。
最もお手軽なところで， CFXweb にある Bonz 氏のレクチャーに手を出してみた。 Hugi Magazine からの転載だ。
http://www.cfxweb.net/modules.php?name=News&file=article&sid...
すごく軽い調子で minimax 近似について解説している。こういうテッキーのくだけた雰囲気は，なんだか懐かしい香りがする。昔はよく，こんな感じの記事を hornet.org から落としては読んでいたものだと思う。今だと flipcode とかがそんな存在に相当するのかもしれない。
ただ，この記事はちょっとざっくりとし過ぎているきらいがあって，読んでいるうちに僕の方が混乱してきてしまった。要点は，第一種チェビシェフ多項式 (Chebyshev Polynomial of the first kind) を使って近似を行うというところにあるらしいことは分かってきた。チェビシェフ多項式自体については WOM に詳しい。詳しすぎて訳がわからないほどだ。
http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKi...
チェビシェフ多項式の特徴は，その直交性にあるようだ。このように直交性を持つ特殊な多項式のことを直交多項式と呼び，これを利用して曲線の近似を行うことを直交多項式近似と呼んでいるらしい。馴染み深いラグランジュ補間やエルミート補間も，この辺りから派生する流れにあるのかな……。
http://www.google.com/search?hl=ja&q=%92%BC%8C%F0%91%BD%8D%8...
と，ここで Numerical Recipes をもう一度見返してみると，チェビシェフ多項式とその近似法について，ずばりそのものが載っていることがわかる。あー，やっと内容が分かるようになってきた。
http://www.library.cornell.edu/nr/bookcpdf/c5-8.pdf
しかし，いまだに minimax 近似の具体的な定義は分かっていないし，いつぞやの Remez Exchange Algorithm に至っては，跡形も無く消えてしまった。うう，単に三角関数の近似を行うだけだったのが，どんどん泥沼にはまりこんでいるような気がする。
2003-02-25
今日もソースをちくちく書いたり，ミーティングに出席したり……。色々と未確定の部分が多くて，一進しては一退することが多くなっている。ちょっと手を広げ過ぎなのかもなあ。
気晴らしに，少し前に書いたソースの高速化などを試みてみる。ソースをこねくり回している間は，純粋にモノいじりの楽しさを得られる瞬間だ。設計に頭を悩ませている間などは，同時に命を擦り減らしているような気がしてならない。
以前は，調子に乗って関数を丸ごとアセンブリ化してしまうようなこともあったけれど，最近では，できるだけそういう無軌道な行動を控えるようにしている。それでも，Ｃソースレベルでの実行順序の入れ換えなんかに凝り出して，気付いた頃にはＣらしからぬＣコードに変貌してしまっていた……なんてこともあるから，注意しないといけない。
それにしても，ちょっとした書き方の違いから，生成コードに違いが出てしまうことは事実なのだから，悩ましい問題だと思う。
例えば，以下のようなコードがあるとする。
これはこれで何ら問題の無いコードだ。人によっては下のような書き方を好むかもしれない。
ポインタ嫌いの理系学生なんかは，こういうの嫌がるかもなあ……。それはともかくとして，この２つの関数の間には，実は単なるスタイル以上の違いが存在している。下のコードの方が明らかに効率が良いのだ。
２つの関数を比較してまず目に付くのが "a->ptr + a->i" の演算だ。この程度の処理ならオプティマイザが最適化をかけて，両者とも同じようなコードにまとめてくれそうなものだけれど，そうは行かない理由が存在する。ポインタのエイリアシング問題だ。
例えば，次のようなシチュエーションで test_func をコールしてみたら，どんな挙動が得られるだろうか。
前者の関数の場合，１行目の代入によって a->i の値が書き換えられてしまうため，２行目の実行前に再び a->ptr + a->i を算出する必要が出てくる。条件によっては以降の行でも同様の現象が起こりうるわけで，結局全ての行に対して a->ptr + a->i を算出する必要があることが分かる。ちなみに，後者の関数ならその必要も発生しない。
前者の関数のアセンブリリスティングを取ってみると，実際に a->ptr + a->i を毎回算出するようなコードが生成されていることがわかる。 x86 系ならまだしも， RISC 系だともう少し冗長なアドレス算出になるから，だいぶ効率が悪くなるかもしれない。
この問題は，ポインタ a および a->p が同じ領域を参照する可能性を持っていることに起因している。しかし，このような状況が例外的であることは，誰の目にも明らかだ。 a と a->p がカブるようなことは，まず想定されていない。そのことをコンパイラに伝えることができれば，問題は解決できるはずだ。
この指定を行うのが， C99 において追加された新仕様， restrict 指定子だ。
こうして restrict 指定を加えたソースからアセンブリリスティングを取得してみた。
うう，なんかヘマやってるな。 eax + edx を先にやっつけちゃえば，もっと効率良くできるのに……。ええと，まあ，ちょっと変な所もあるけれど，基本的には効いているみたいだ。
ここで挙げたエイリアシングに関する諸問題と restrict 指定子の詳細に関しては，以下の資料に詳しく解説されている。
http://www.lysator.liu.se/c/restrict.html
こんな感じで，たとえアセンブリには手を出さないとしても，コンパイラの機能を十二分に引き出そうとするならば，重箱の隅をつつくような解析と，泥臭い調整作業を行う必要が出てくる。やはり肝心なのは１０−９０の法則を守ること……負荷となっている部分を的確に推定し，ピンポイントで高速化を行うことにあると思う。そのときになって初めて，こういった知識が役に立つと言えるかもしれない。
2003-02-26
Jiro さんや，げーはなさんの助言のおかげで，なんとなく勘を掴むことができたようだ。ある程度の予備知識が付いたところで Numerical Recipes を読み返してみると，以前は漠然としか分からなかった内容が，ほぼ十分に理解できるようになっていた。これで一気に解答へと近づくことができるかもしれない。
http://www.library.cornell.edu/nr/bookcpdf.html
読み返していて感じたことなんだけれど， Numerical Recipes の文体は意外とくだけていて読みやすい。全体を通して，複雑になり過ぎない程度の解説が常に与えられており，解答までの道程の短さにも関わらず，一応の直感的な理解が得られるようになっている。そこには，実用性と即効性を重視しながらも数学のブラックボックス化を防ごうという，著者の深い意図が含まれているようだ。この分野に明るい人に言わせれば，ちょっと危うい部分も見受けられるらしいんだけど，工学系の学生や技術者のように，数学を道具として使いこなしたいと考えている人々にとってみれば，ちょいど良いバランスを保っているのではないかと思う。
それにしても，この無料配布版 pdf からの印刷だけでも，相当溜まってしまったような気がする。そろそろいいかげん，書籍版の購入を考えた方がいいかもしれない。
http://www.amazon.co.jp/exec/obidos/ASIN/0521750334
http://www.amazon.co.jp/exec/obidos/ASIN/4874085601
日本語版もあるけれど，版が少々古いところが珠に傷だ。ページ数も増えているし，ついでに言えば値段もかなり違う。ううむ……。
上にある図はチェビシェフ多項式（第一種）の４次式までを別個にプロットしたものだ。このように，チェビシェフ多項式は -1 から +1 の範囲において周期的な形状をしている（厳密な周期性は無い）。また，各次の式はそれぞれ直交性を保持している。これらの特性から，チェビシェフ多項式は直交多項式の代表的な存在として挙げられることがあるようだ。
http://mathworld.wolfram.com/OrthogonalPolynomials.html
チェビシェフ多項式の持つこれらの特性を応用すると，ちょうどフーリエ級数のような感じで，任意の関数をチェビシェフ多項式の合成として表現することができる。これを利用したのが「チェビシェフ近似」と呼ばれる手法だ。
http://www.library.cornell.edu/nr/bookcpdf/c5-8.pdf
チェビシェフ近似がテイラー級数による近似と比較して優れているのは，前述のようにチェビシェフ多項式が周期的な形状をしていることにある。テイラー級数は各次が単項式から構成されているため，高次成分を切り詰めたことによって発生する誤差が，値域の両端に対して顕著に現れるという特徴を持っている。これに対してチェビシェフ近似では，切り詰めた高次成分は例の通り周期的な形状をしているため，誤差も同様に周期的な形状として現れる。これは一般に，誤差を値域に対してまんべんなく分配するという効果をもたらすようだ。
このようにして得られたチェビシェフ近似式は，最も理想的な近似式である「ミニマックス近似式」に非常に近い形をとっており，場合によってはその代替として用いることも可能であるとされている。ミニマックス近似式は解析的に求めることが不可能であるとされているのに対して，チェビシェフ近似式は非常に簡単なプロセスによって導出することが可能なため，このことは大きなメリットとなり得るということだ。
実際に Numerical Recipes の解説を元にしてチェビシェフ近似式を導出するプログラムを組んでみると，これが非常に手軽な方法であることが分かると思う。 Numerical Recipes にはお手本のソースが掲載されているんだけれど，これを参照する必要がまったく無いほどだ。それでいて，近似の質はかなり良い。こりゃあおいしいかもなあ……。
2003-02-27
そんなこんなで，チェビシェフ近似法を用いた近似多項式の導出までコマを進めることができた。これは一般的な多項式近似法としてなかなか良い性質を持つものであることが分かったものの，実際に今回のケース（高速動作する近似三角関数の導出）に当てはめてみると，実は期待したほどの効果を挙げられていないことが分かった。やはり値域の端の方で誤差が跳ね上がってしまうのだ。ううむ……。
この「誤差の跳ね上がり」は，どうやら近似プロセス内で行っている式の変形に起因するもののようだ。 Robin Green 氏の方法では，できる限り項数の少ない式で効率良く近似を求められるようにと，近似対象となる式の変形を行っている。これは結果的に，近似式の絶対誤差を x の３乗に比例した形で増幅する効果を与えてしまっている。
それにも関わらず， Green 氏の導出した近似式は，値域内において一定の誤差量を保つことに成功している。これは，氏の利用している「レメッツ交換法」 (Remez Exchange Algorithm) と呼ばれる方式がカギとなっているようだ。レメッツ交換法では，任意の重み付け関数 W(x) を与えることによって，許容誤差量を自由に操作できるようになっている。この性質を利用すれば，逆変形後の近似式に含まれる誤差が一定量へと収まるように，制御を加えることも可能となるわけだ。
この「レメッツ交換法」は，デジタルフィルタ − 特に FIR フィルタ（有限インパルス応答フィルタ）の設計に利用されることが多いようだ。 google などで検索にかけてみると，その手のページを多く見付けることができる。
http://hiraws1.ms.kagu.sut.ac.jp/spedu/Remez/A_Remez.htm
http://www.mathworks.com/access/helpdesk/help/toolbox/filter...
このアルゴリズムの考案者である Evgeny Remez 氏については，こんな感じの情報がある。
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Reme...
大戦の辺りに活躍したキエフ大（ソビエト）の教授だそうだ。比較的新しいんだね……。
レメッツ交換法自体は，具体的には，ミニマックス近似における係数の改良プロセスを担うアルゴリズムの一種であるらしい。例えば，以前参照した CFXWeb の記事では，このプロセスを古典的なニュートン法によって解決している。また，げーはなさんに頂いた資料では，係数の修正条件を線形システムに直し，それを LU 分解法を用いて解き，また条件を組み，解き……といったプロセスを反復することによって，最終的なミニマックス近似式へと近づける，という方法を用いていた。
こんな感じで，解法自体は色々と存在するんだけれど，その中でも特に優れた手法としてレメッツ交換法というものが存在するらしい……という認識でいいかな，と思う。
それじゃあ，そのレメッツ交換法ってやつを実装すればいいのか，という話になるんだけれど，これはそう簡単に解決できる問題ではないようだ。 Green 氏曰く，レメッツ交換法は演算誤差に対して非常に敏感なアルゴリズムであり，まともに解を得るには最低でも４０桁程度の演算精度を保持する必要があると指摘している。
このような演算精度の問題に対して， Mathematica や MATLAB などの数値演算パッケージでは，有理数演算や任意精度演算を導入することによって対処しているようだ。さすがにこの辺りまで来ると，とても素人には手出しできなさそうな雰囲気が漂ってくる。概念の難易はともかくとして，そこまでする手間が，ね……。適当な道具があれば，是非ともそれに頼りたいところなんだけれど，果たしてどうしたものだろうかと思案している。
2003-02-28
そもそもの事の発端となったのは， GDC 2002 における Robin Green 氏の講演 "Faster Math Functions" だった。今年（しかも，もうそろそろ）開催される GDC 2003 でも，同名の講演を行う予定のようだ。
https://www.cmpevents.com/GDx/a.asp?option=C&V=11&SessID=484
去年の講演では，講演前半の導入部分が IEEE 浮動小数点形式 (IEEE 754) の発祥について触れる内容となっており，これがなかなか興味を誘うものとなっていた。
現在ではデファクトスタンダードとして広く用いられている IEEE 754 だけれど，その標準化過程には，意外と奥の深い物語が存在するようだ。仕様自体は比較的シンプルなものにも関わらず，規格の立案から制定までに実に８年の歳月を要することになったというのだから，驚くべきものがあると思う。
この辺りの話については，標準化委員会の中心的人物であった William Kahan 氏へのインタビュー記事 "An Interview with the Old Man of Floating-Point" が参考になる。
http://www.cs.berkeley.edu/~wkahan/ieee754status/754story.ht...
http://www.netfact.com/dr-chuck/papers/columns/r3114.pdf
ちなみに氏は，この標準化作業への貢献を評価され， 1989 年に ACM チューリング賞を受けることになった。
今でこそ float （単精度浮動小数点）と言えば「仮数部が２３ビットで指数部が８ビットのアレ」みたいな常識が成立するものの， IEEE 754 が制定される以前は，ハードウェアによって形式はまちまち，仕様もまちまち，挙動もまちまちで，プログラマは常にターゲットマシンの特性を把握した上でコードを書かなければならない状態だったそうだ。
そんな状況下から，浮動小数点形式の標準化への機運が高まり，ついに "IEEE 754" として標準化過程が開始されることになった。これが 1977 年のことだ。当時 Kahan 氏は Intel から FPU プロセッサ（かの有名な 8087 に相当する）の設計への協力を依頼されており，結果的にここで培った設計思想が IEEE 754 に対して影響を与えることになったようだ。
http://www.atmarkit.co.jp/icd/root/94/57610894.html
http://www.itofamily.com/ito/collections/16bit/8087/
Kahan 氏が提案した形式は，彼の教え子である Jerome Coonen 氏，それに客員教授の Harold Stone 氏を含む３人によって作成されたことから「KCS 形式」と呼ばれていた。この「KCS 形式」案に対して最も反発していたのが，当時の DEC であった。 DEC の主力製品であった VAX マシンでは， FPU がハードワイヤ実装されており，これを KCS 形式に準拠させることは困難を極めると考えられていたからだ。これは， KCS 形式がマイクロプログラムでの実装を前提したものと受け取られていたことが大きく