HOME | PRODUCT | BBS | CODE
Code | Memorial | Sample | Reference
List | -10 | -20 | -30 | -40 | -Latest
since 2000/10/01
#31 (2001/01/29 )
 ビットカウント
#32 (2001/02/22 )
 拡大 for WonderWitch
#33 (2001/02/28 )
 拡大の逆襲 for WonderWitch
#34 (2001/03/10 )
 エミュのススメ
#35 (2001/04/05 )
 キレイな弾幕は好きですか?
#36 (2001/05/19 )
 Microsoft的コンパイラ実装法
#37 (2001/07/06 )
 お手軽なCSG描画
#38 (2001/07/24 )
 多面性による二つのレベル
#39 (2001/08/09 )
 テーブル枠の作り方
#40 (2001/09/06 )
 弾幕の作り方−序章編−

Tip Mark
欄外情報FOOTNOTE  参考リンクLINK  補足事項NOTICE
sanami@aya.or.jp

第31回ビットカウント
いつものイントロ

みなさん、ざわざわ。 ありがたいことに暁のコーダ部屋も10000アクセスを記録しました。 今回は、これを記念していろいろごたごたとお送りします。 わざわざ10000アクセス記念用のページを用意すると残しておくことが面倒になるので、 特別企画もPEACE CODE内に入れてしまいます。 そして、特別企画の中身は・・・

  1. PEACE CODE特別編公開
  2. 伝説の仄香スクリーンセイバーソースコードプレゼント
  3. ラブラブティファビューワーソースコード公開
1の特別編が、この文章です。どのあたりが特別かというと、いつもより内容が薄い(笑)。 そして、プレゼントは番組の最後で。

ところで、10000アクセス記念などと言っていますが、実は暁のコーダ部屋が10000アクセスなのは(おそらく)もっと以前なのです。 コーダ部屋の第一回は2000年2月21日なわけですが、このときにはアクセスカウンタがついてなかったのですね。 いつからカウントし始めたかというと、aya.or.jpに引越してから、それは2000年10月1日です。 そうは言っても、切りがいい数字を記録したわけなので、なにかしてみたくなったのでした。

今回は、10000カウントということで数を数えることにこだわってみたいと思います。

32ビットカウント(初級)

数を数えるからには何かの数が必要、ということで32bitレジスタの1になっているbitの数を数えることにしましょう。 たとえば、0x12345678という値(図1)が入力された場合、

ビット列の例
図1:ビット列の例

13という数字をゲットするのが目的です。

単純に数えるならこんな感じで書けます。 aが入力とします。
int count = 0;
for(i = 0; i < 32; i ++, a >>= 1)
    count += a & 1;
この場合、32回の計数が行われますが、 次のように変更すると半分の計数で同じことができます。
int count = 0;
for(i = 0; i < 16; i ++, a >>= 1)
    count += a & 0x00010001;
count = (count >> 16) + (count & 0x0ffff);
カウンタを16bit x2のフィールドに分割し、 同時に二つの部分を計数するわけです。 と考えると、8bit x4、4bit x8、2bit x16、1bit x32とすることができるのはわかると思います。 そのときのコードは次のようになっているはずです。
int count;
count = ((count & 0xaaaaaaaa) >>1) + (count & 0x55555555);
count = ((count & 0xcccccccc) >>2) + (count & 0x33333333);
count = ((count & 0xf0f0f0f0) >>4) + (count & 0x0f0f0f0f);
count = ((count & 0xff00ff00) >>8) + (count & 0x00ff00ff);
count = ((count & 0xffff0000) >>16) + (count & 0x0000ffff);

まずこの状態での無駄を省いておきましょう。 二つのフィールドの計数値を足し合わせる前にマスクをかけているのは、 足し合わせたときに計数値がゴミの入った場所まで使用する可能性があるため、 そのゴミを掃除しておいているわけです(わかんねぇって)。 もう少し詳しく説明することにしましょう。
count = ((count & 0xcccccccc) >>2) + (count & 0x33333333);
について考えます。32bit幅もあると図を描くのが大変なので、 4bit幅にして話を進めます。
count = ((count & 0x0c) >> 2) + (count & 0x03);
ということです(図2)。

2bitの折りたたみにおけるフィールドの衝突
図2:2bitの折りたたみにおけるフィールドの衝突

2bitのフィールドには2bit幅における1の数が入っています。 とり得る値の範囲は0-2です。これを足し合わせた場合、 新しく得られる4bitのフィールドにおける値の範囲は0-4となります。 最大4ということは3bitのフィールドが必要です。 下位から3bitのフィールドを確保すると上位2bitと1bit重なります。 したがって、この重なった1bitはクリアしておく必要があるわけです。

次の場合を考えてみましょう(図3)。
count = ((count & 0xf0f0f0f0) >>4) + (count & 0x0f0f0f0f);

4bitの折りたたみにおけるフィールドの使用状態
図3:4bitの折りたたみにおけるフィールドの使用状態

この場合、足し合わせる前の4bitのフィールドには4bit幅における1の数が入っており、 そのとり得る範囲は0-4です。足し合わせた後の範囲は0-8ですね。 最大8ということは4bitあればOKです。 ということは、重なっている部分がありませんのでクリアしておく必要はありません。 コードはこのように書き直せます。
count = ((count >> 4) + count) & 0x0f0f0f0f;

ここまでが初級講座です。 次に中級に入りましょう。

32ビットカウント(中級)

count = ((count & 0xaaaaaaaa) >>1) + (count & 0x55555555);
これは次のように書き直せます。
count = count - ((count & 0xaaaaaaaa) >> 1);
結果だけ見ると難しく見えますが、種明かしをすれば実に簡単です。 ちなみに、僕は方法を思いついて、実際に値を代入して動作が正しいことを確認してから、 その種に気がつくまで数時間かかりました(笑)。

まず入力値を2bitとして、上位bitをA、下位bitをBとして表すこととします。 つまり入力値はABと表されます(AとBが並んでいることを表します)。 結果として欲しいのは2bitのフィールドにA+Bを計算した結果です。
count = ((count & 0xaaaaaaaa) >>1) + (count & 0x55555555);
最初のコードでは、ABをAとBに分離してA+Bを計算しています(図4)。

2bitの折りたたみによる計数
図4:2bitの折りたたみによる計数

ここで、AB=Ax2+Bであるということを利用してみます。 結果の値はA+Bですから、
A+B +A=Ax2+B=AB
ですね。 となれば後は簡単です。
AB-A=(Ax2+B)-A=A+B
なわけです。これを使うと、最初のコード
count = count - ((count & 0xaaaaaaaa) >> 1);
が得られます。

32ビットカウント(上級)

最後に上級(ある意味、低レベルではあるけど)です。 最後の2行
count = ((count & 0xff00ff00) >>8) + (count & 0x00ff00ff);
count = ((count & 0xffff0000) >>16) + (count & 0x0000ffff);
の順番を入れ替えてみましょう。
count = ((count & 0xffff0000) >>16) + (count & 0x0000ffff);
count = ((count & 0x0000ff00) >> 8) + (count & 0x000000ff);
これでも問題なく動きます。32bit幅といっても1の数は0-32で5bitあれば表現できるのですから、 8bit以上のフィールドにもなれば、順番はどうでもいいのです。 このように書き直したのは、 最後の1行のようにすることでパーシャルレジスタが使えるからです。 アセンブラで書いてみます。eaxにcountが入っていると思ってください。
mov ebx, eax
and ebx, 0xffff0000 // 不要
shr ebx, 16
and eax, 0x0000ffff // 不要
add eax, ebx        // 1行目終了
add al, ah
これでALにカウント値が入るわけです。

ここまでの内容をまとめてアセンブラにしてみます。計数する32bitはeaxに入っているとします。
mov ebx, eax
shr ebx, 1
and ebx, 0x55555555
sub eax, ebx
 
mov ebx, eax
shr ebx, 2
and ebx, 0x33333333
and eax, 0x33333333
add eax, ebx
 
mov ebx, eax
shr ebx, 4
add eax, ebx
 
mov ebx, eax
shr ebx, 16
add eax, ebx
 
add al, ah
こうです。

思わぬ落とし穴

ここで大きな問題があります。 実はこのコード、(内容的に)同じコードが既出なのです(笑)。 僕が持っている資料は幻(?)のA MAGAZINE 1998 April1です。 この中で、日経MIXのアセンブラ会議でmoritan(森田和郎氏)が提示されたコードとして紹介されているのです。 掲載されているコードはmov+shrではなくshldを使っていますが、ほぼ一緒になってます。 せっかく考えても同じものがあるのでは、「おまえ、真似したろー」と言われるのがオチです。 まるで、特許です(笑)。ということで、このコードはサブマリンコードと・・・

とりあえず、どこか一箇所でもオリジナリティを発揮できればいーやーということで考えた結果、 なんとかオリジナリティが少しはある・・・かな?というコードを開発しました。 ああ、よかった。とかいいつつ、誰か考えてそうな気はすごいするんですけどね。

別解

count = count - ((count & 0xaaaaaaaa) >> 1);
これを、
count = (count + (count & 0x55555555)) >> 1);
とします。ただし、これ、C言語では動きません(笑)。 Carryフラグを使いますので。 アセンブラで書くと、
mov ebx, eax
and ebx, 0x55555555
add eax, ebx
rcr eax, 1
となります。 動作の原理は、まず2bitフィールドにおける1の数を数えるとして、 上位bitをA、下位bitをBとします。 仮に上位bitが空であるとして、
0B
という状態を考え、これに同じ値を加えると、演算結果は、
B0
になります。 ここで重要なのは、今までBのあった場所が0になることです。 なぜ重要なのかは数秒後にわかります。

さて、ABという値を考えたとき、
AB = A0 + 0B
と分離することができます。 この値に0Bを加えると、
A0 + 0B + 0B = A0 + B0
となります。AとBはそれぞれ1bitの値ですが、 加えると2bit必要になります(0-2の値をとるため)。 ここで先ほどの重要な点が生かされます。 A+Bの結果を得るために、 フィールドを1bit増やさなければならないわけですが、 それが一つ上位のフィールドなのです。
  ABAB = A0A0 + 0B0B
 
  A0A0 + 0B0B+0B0B = A0A0 + B0B0
一つ上位のフィールドの最下位bitは先ほどまで(一つ上位の)Bがあった場所です。 この場所は、0B0Bを加えたことによって0になることが保証されていますから、 0クリアする必要がありません(図5)。

2bit計数の新手法の動作の様子
図5:2bit計数の新手法の動作の様子

これで、AB+0B=Ax2 +B +B = Ax2 +Bx2 = (A+B)x2の説明ができたわけですが、 それでは最上位のフィールドの桁上がりはどうなるでしょう。 それはCarryフラグに入ります。 ということは、最後に右に1bitシフトする際に、Carryフラグも含めてシフトしてあげればいいのです。 残念ながら、Carryを含めたシフト命令はないので、ローテイト命令で我慢します。 1bitのローテイトなら1クロックなので問題ありません。

以上のようにして、
mov ebx, eax
and ebx, 0x55555555
add eax, ebx
rcr eax, 1
というコードが動くのです。 そんなわけで、森田さんとタメをはることに成功しました(違)。

ビットの上下反転に応用

話はもう少し続きます。 上で用いた方法を使うと、ビットの上下反転にもちょっとだけ使えます(図6)。

2bitの上下反転
図6:2bitの上下反転

まずは、森田さんの示したビットの上下反転のコード。
ROR EAX, 7
MOV EBX, EAX
AND EAX, 55555555H
XOR EBX, EAX
ROL EBX, 2
OR EAX, EBX
MOV EBX, EAX
AND EAX, 33333333H
XOR EBX, EAX
ROL EBX, 4
OR EAX, EBX
MOV EBX, EAX
AND EAX, 0F0F0F0FH
XOR EBX, EAX
ROL EBX, 8
OR EAX, EBX
BSWAP EAX
最初の2bitの上下を反転するのに苦労してるようです。 この部分は、
mov ebx, eax
and ebx, 0x55555555
add eax, ebx
rcr eax, 1
add eax, ebx
と書くことができます。命令数一緒なので、苦労してることになるわけですが(笑)。 これは、先ほど説明した手法をもう一段階適用すると得られる方法です。
AB -> A0 + 0B
 
A0 +0B +0B = A0 +B0
 
右に1bitシフト
 
A +B
 
0Bを加える
 
0A +0B +0B = 0A +B0
不思議なようですが、図示すれば難しくありません(図7)。

2bitの上下反転アルゴリズム
図7:2bitの上下反転アルゴリズム

数式では、
BA = Bx2 +A
   = B +B +A
   = (Bx2 +Bx2 +Ax2)/2
   = (Bx2 +Ax2)/2 +B
   = (B +B +Ax2)/2 +B
   = ((Ax2 +B) +B)/2 +B
   = (AB +B)/2 +B
と変形すれば明瞭ですね。2で割っている部分が右1bitシフトです。

特別企画その2

伝説の仄香スクリーンセイバーのソースコードを抽選で10名様にプレゼント!!

1997年に初めて開発した仄香スクリーンセイバーのソースコードを抽選で10名様にプレゼントします。 謎さんのご好意により、使用したすべてのパターンを添付しており、 どちらかというと、パターンのほうの価値の方が高いという噂です。 なお、体験版仄香スクリーンセイバーはver.2であり、今回プレゼントするものとは大きく異なります(笑)。 さらに、久しぶりに起動してみたところ、 ある常駐ソフトと干渉してすぐに終了してしまうということが判明。 ver.2では干渉しないのに(笑)。

それでは、賞品の特徴です。

次に、注意事項です。 以上のことに了解した方だけご応募ください。

応募方法です。 subjectを「仄香が欲しい」にしたメールをsanami@aya.or.jpにお送り下さい。 subjectが間違っている場合、抽選対象から外れますのでそれだけはご注意下さい。

応募〆切は・・・20001年2月13日とします。メールの日付が2001/2/13ならOKです。 当選者の発表は、2月14日の予定です。

特別企画その3

ラブラブティファビューワーソースコードフリー公開!!


図8:実行例

なにがラブラブなのか、よくわかりませんし、ティファしか見れないわけでもないのですが、 あのスクウェアのFinalFantasyVIIのポリゴンビューワです。 パーツごとのポリゴンビューワはほかに見かけましたが、 連結情報を(少しだけ)抽出している点が異なります。 また、ソースコードを公開しますので、これをベースにティファのドルフィンパンチを再現することも夢ではありません。 っていうか、誰か、再現して僕に下さい(笑)。

使用上の注意

また、さらなる愛と努力と時間と勘と少しの能力があれば、多分、動きます。 僕はモーションデータを解析するところで挫折しましたが。 ちなみに、モーションデータを解析するつもりがあるのなら、 PC版の購入をお勧めします。PC版なら、バイナリデータを直接いじくれるので、 実際に値を変更した結果がどのようにモーションに影響するかを見れるのです。 ちなみに、角度は4096分解能であることは発見しました。 パーツの連結情報はどうやらあっているっぽいので、ほんとにモーションデータだけあれば・・・。

PS版は、各キャラクターごとに圧縮ファイルが存在しますが、 PC版では一つのファイルに無圧縮で連結されていました。 まぁ、PS版からデータを使うのが常識的でしょう。 データ自体は全く同じだったりします。

他にテクスチャをbmpに変換するための手動解析ツールもあったりしますが、 中途半端に未完成なのでこいつはゴミ箱行き。

ダウンロード(実行時に必要なファイルはff7viewer.lzh::readme.txtをご参照ください)

すっかり忘れていましたが、GLUTとGLUIさえそろえればWindows以外のプラットホームでも実行可能です。 BeOSR4で表示が一部おかしいものの、いちおう動くことを確認しました。

参考文献

  1. A MAGAZINE 1998 April
    C MAGAZINEで昔Borlandが毎年出していたエイプリルフール広告で先着1000名に当たるCDに収録。pdfになっている。 表紙で「究極のアセンブラ」と煽っておきながらアセンブラの記事がちょっと少なめで残念。非売品。

Virtual Payment System100えん10えん1えんヘルプ

第32回拡大 for WonderWitch
はじめに

みなさん、ざわざわ〜。今回は、10000Hit記念プレゼントの発表をかねるのですが、ネタがネタのため時間がかかり、プレゼントの発表が遅れたことをお詫びします。応募していただいた方にはすでにお詫びしていますが、いちおう。例によって、当選者の発表は番組の最後で。

ぎゃるぱにXの通販にあたり、申し込んでくださった方の中には感想を書いてくれる方も多く、興味深く拝見させてもらいました。で、ぎゃるぱにXへの熱い思いのたけ(笑)だけでなく、暁のコーダ部屋の感想をくださる方もいらっしゃるわけで、今後の参考にさせてもらおうと思うのであります。ところが、リクエストの内容によっては最適化とはほとんど縁の無いようなネタもあり、これは暁のコーダ部屋で取り上げるべきかで悩むわけです。

ここで問題になるのが、僕自身は暁のコーダ部屋をどう思っているか、です。基本的には好き勝手書きたいのですが・・・・と思って過去の分を見直してみると、「リンクについて」で、堂々と「最適化の話題について」などと書いてしまってますね。書いた覚えはなかったのですが(笑)

とはいっても、最適化とは直接関係ないこともすでに書いているので、暁のコーダ部屋の扱う範囲を拡大して、できるかぎりフィードバックしたいと思います。やっぱり、読者サービスは必要かと。

最近のWonderWitch

WonderWitchのメーリングリストや掲示板の書き込みが、きつい、きつくない、でイヤ〜な雰囲気です。書き込みがきついかきつくないかは、しょせん、受け手の取り方一つで決まるわけです。そのことについては、みなさん合意しているわけなのですが、そこで話が終わってしまっています。それじゃ意味ないよ〜。受け手の取り方で決まるってことは、ある書き込みを見たときには、ある確率でイヤだと思う人がいるってことです。まず、普通に書き込んだとします。その文章を読んで普通だと思う人は感性の似た人であり、図1のような状態です。

普通に書き込んだ場合
図1. 普通に書き込んだ場合

次に、意識して柔らかく書き込みをしてみます。その文章を読んで、きつくないと思う人は図2のように広がるのではないでしょうか。

柔らかく書き込んだ場合
図2. 柔らかく書き込んだ場合

人によって取り方が違うんですね〜、ということがわかるなら、少しやさしく書くように変えれば、イヤだと思う人も少なくできるということもわかると思うんですが。WonderWitchで楽しくプログラミングする人を拡大するには、「ユーザーのポータルサイト」のメーリングリストぐらい、こーゆーことに気を配ったほうがよろしいかと。ちなみに、このポータルサイト、誰(どういう団体?)が運営しているのか、さっぱりわからないので、僕はそっちのほうが気になってます(笑)。

それはともかく、今、僕がしたいのは、イヤ〜な雰囲気だと感じてやる気のしぼんでいる有能なクリエイターの方々に、こんなこともできるんだよ〜と提案することで創作意欲を拡大することです。それが可能かどうかはともかく、ね。

基本的な拡大

しかし、創作意欲の拡大と言っても簡単なことではありませんで、それはプログラムでの拡大にも言えることです。WonderSwanのプロセッサは低速で、しかも、WonderSwanのハードウェアがビットマップ型でありませんから、ビットマップ型ではさほど難しくもない拡大もラインバッファ型では難題です。手始めに、とりあえず書いてみることにしましょう。WonderWitchで拡大が可能かを模索するのが目的なので、プリプロセッシングにはいくら時間をかけてもよい、という前提に立つことにしましょう。つまり、データ形式は問わず、メモリ効率も問わず、ってことですね。

また、簡単のために、表示領域を固定とします。これで、等倍サイズの表示領域を用意したら、その中のすべてのピクセルについて、描画するだけですみますし、各ピクセルにおける元画像の領域内判定も行わなくてすみます。あと、横方向の拡大に話を限定しましょう。縦方向の拡大は転送元のラインをずらすことでも実現できますし、同じラインなら前のラインをコピーするようにしてもいいですし、ラスタースクロールを使っても実現できそうです。どっちにしろ、横方向に比べれば簡単に実装することが可能です(多分)。

まず真っ先に思い浮かぶのは、各ピクセルを独立に保存することです。その方向性で何も考えずに作ってみました。
アーカイブ:32-wwexpand0.lzh (8617 bytes)
プログラム:32-wwexpand0.c (4619 bytes)
そして、拡大部分のコード。
cnt = 0;
sy = 0;
for(dy = 0; dy < WIN_HEIGHT; dy ++)
 {
    WORD ty;
    /* 左端の位置を求める *
sx = ((WIDTH/2)<<8) - ((WIN_WIDTH/2*8) * ratio); ty = sy; for(dx = 0; dx < WIN_WIDTH; dx ++) { WORD t[8]; WORD tx; tx = sx; sy = ty; for(j = 0; j < 8; j ++) { sx = tx; t[j] = 0; for(i = 0; i < 8; i ++) { t[j] <<= 1; t[j] |= tempBuf[(sy>>8)*WIDTH +(sx>>8)] & 0x0101; sx += ratio; } sy += 0x100; } font_set_colordata(cnt ++, 1, (char far*)t); } }
拡大に限定すれば、ブレゼンハムも使えますが、とりあえず固定小数(整数部8bit、小数部8bit)で書いてます。で、実行してみると、224x40の表示サイズで5.6FPSでした。

お試しの高速化

上のプログラムがどのようなアセンブラにコンパイルされているかを見てみると、かなり無駄な命令がちらほらと見受けられます。これはいけません。試しに、無駄な命令を取り除いたときにどれくらい変わるかを見てみましょう。実際には一番内側のループを展開して、そのたもろもろ、ちょこちょこと書き換えてみました。
アーカイブ:32-wwexpand1.lzh (8848 bytes)
プログラム:32-wwexpand1.c (6244 bytes)
で、一番内側のループはこんなんに。みにくくなるので、ニーモニックは直接書いておきます。
WORD t[8];
WORD tx;
tx = sx;
sy = ty;
for(j = 0; j < 8; j ++)
 {
    sx = tx;
    t[j] = 0;
 
    t[j] <<= 1;
    _asm_expand_first("", sx, sy, ratio);
    /* AX<-sx BX<-sy CX<-ratio *
push dx push di and bx, 0xff00 shl bx, 1 xor dx, dx /* 1dot目 *
mov dl, ah xor ah, ah add bx, dx add bx, dx mov di, [bx+_tempBuf] add ax, cx /* 2dot目 *
shl di, 1 mov dl, ah xor ah, ah add bx, dx add bx, dx or di, [bx+_tempBuf] add ax, cx /* 3dot目 *
/* 4dot目 *
/* 5dot目 *
/* 6dot目 *
/* 7dot目 *
/* 8dot目 *
shl di, 1 mov dl, ah xor ah, ah add bx, dx add bx, dx or di, [bx+_tempBuf] add ax, cx shr bx, 1 /* 終了処理 *
mov ax, di pop di pop dx t[j] |= ax; sx += ratio <<3; sy += 0x100; } font_set_colordata(cnt ++, 1, (char far*)t);
実行してみると、12.8FPSまでになりました。おぉ、すごいぞ〜。

問題の細分化

拡大のプログラムをちまちま高速化していると、問題が2つの小さな問題を含んでいることに気がつきます。

  1. どのピクセルを参照するか
  2. どのようにラインバッファ上に合成するか
1は、簡単に言えば元画像がtempBufに格納されているとして、n=tempBuf[index]として取り出す問題を指しています。2は、nとして1ピクセルごとに取り出した値をどのようにして、画面に反映させるための関数
WORD t[8];
font_set_colordata(cnt ++, 1, (char far*)t);
の各要素へ合成するかを指しています。

1. 参照ピクセルの決定法
この問題は、2つの話題を含んでいます。

  1. 元画像 tempBuf を WORD 配列にするか、BYTE 配列にするか
  2. index をどのように決定するか
1.a 元画像 tempBuf 配列の型
1ピクセルが 1WORD なのか、1BYTE なのか、ということなので、当然のことながら 1BYTE のほうが使用メモリ量的に好ましいわけです。また、WonderSwan の V30MZ には、WORD でのアクセスが簡単になるようなアドレス指定法がありません。たとえば、
WORD temp[2];
 
xor BX, BX
mov AX, [BX + _temp]
inc BX
mov CX, [BX + _temp]
とすると、CX には temp[1] が入っていないので注意です。CX に temp[1] を入れるようなC言語のコード
int bx = 0;
ax = temp[bx];
bx ++;
cx = temp[bx];
は、
xor BX, BX
shl BX, 1
mov AX, [BX + temp]
shr BX, 1
inc BX
shl BX, 1
mov CX, [BX + temp]
shr BX, 1
などとなるのでやっかいです。このあたりの処理を避ける上でも BYTE 配列のほうが有利です。BYTE 配列とした場合に不利となる点は、取り出した BYTE 値からラインバッファ形式の WORD 値へ、どのように変換するかの一点です。この点について議論するのはまだ早いので、アドレッシングの不利な点は目をつぶって、WORD 配列を使うことにします。

1.b index の決定法
大きくわけて、固定小数点を使用する方法とブレゼンハムを使用する方法にわけることができます。プログラム上の違いとしては、分岐があるか否か、ととって構いません。

固定小数点を使用する方法の利点は、転送元画像の横幅を 256 ピクセル固定とすることで、パーシャルレジスタを使って高速に決定することができます。
AX : 転送元画像 X 座標値(8:8固定小数点表現)
BX : tempBuf の index(上位8bit=Y 座標値、下位8bit=X 座標値)
CX : 拡大係数(256で等倍、小さくなると拡大率が大きくなる)
 
add AX, CX
mov BL, AH
要するに、AX の整数部が転送元画像の X 座標を表しているので、同じ BX の下位 8bit にコピーすることで決定できる、ということですね。

ブレゼンハムを使用する方法は任意幅の画像でも扱えます。拡大率が大きい(=同じピクセルを何度も参照する)場合には高速化の恩恵を望むことができますが、等倍に近くなると分岐のジャンプ命令や読み込んだピクセルの値をコピーするなどのオーバーヘッドによって遅くなります。

どちらの方法が有利なのかは実装してみないことには比較できませんが、まず、実装の簡単な固定小数を用いた方法を使うことにしましょう。

2. ラインバッファ上への合成法
こちらは難しい問題です。基本的な方法としては、

  1. 書き込む位置を固定にする
  2. 書き込む位置を可変にする
の 2 つにわけることができる、と思います。

2.a 書き込む位置を固定にする方法
横 8 ピクセルを連続して合成するので、各 BYTE の最下位 bit に合成するようにし、合成した値を毎回左に 1bit シフトしていけば、8 ピクセル分の処理が終わったときにはあら不思議、合成できています(図3)。この方法は、合成後の値を保持するレジスタを毎回シフトしなければならないことが欠点ですが、転送元画像の配列から取り出した値を、そのまま OR すればいいだけなのでかなりおいしいです。

書き込む位置を固定にする方法
図3. 書き込む位置を固定にする方法

2.b 書き込む位置を可変にする方法
合成した値は触らず、OR で合成する際に適切な位置に書き込む方法です。転送元画像は、色を表す値の上位ビットを上位 BYTE に展開、下位ビットを下位 BYTE に展開して配列に保存し、合成時にマスクを通して合成するという方法です(図4)。例えば、00000000 000000AB として表されるピクセルは AAAAAAAA BBBBBBBB として配列に保存しておきます。その上で 2 ピクセル目であれば、01000000 01000000 というマスクと AND を取れば、適切な位置にビットを配置することができます。横 8 ピクセル分の処理はループを展開して記述するため、マスク値は固定値としてコード内に埋め込むことができ、2.aの手法と必要な命令数は等しくなります。

書き込む位置を可変にする方法
図4. 書き込む位置を可変にする方法

どちらを使っても構わないので、2.aを使うことにします。

実装結果

と、書いたところで、実は実装したのが 32-wwexpand1.c (6244 bytes) だったことを発見。いや〜ん、論理展開が破綻してますがな。というわけで、以上のことを考慮して選んだ手法を使うと 12.8FPS を達成できるわけです。 ちなみに、WORD 配列とすると、Index の決定に固定小数点を使う方法を選択した場合に転送元画像の横幅が 128 ピクセルに限定されます(最速の場合)。 32-wwexpand1.c (6244 bytes) では、横幅が 256 ピクセルなためにがんばって処理してる分、不利です。

そりでは、いよいよブレゼンハムを使ってみましょう。実のところ、上の文章はすでに結果を見てから書いていたりするので、賢明なる読者諸君にも結論は見えていることでしょう(笑)。
アーカイブ:32-wwexpand4.lzh (16612 bytes)
プログラム:32-wwexpand4.c (8350 bytes)
で、実行結果ですが、12〜14FPS でした。拡大率によって速度が変わるのでこのような結果になるのですね。ちなみに 12FPS という値は等倍近辺を表示中です。要するに、ある程度以上拡大していれば速いことが確認できた、ただそれだけです(そっけなさすぎ)。

さらに高速化

ここまでがイントロです(笑)。あやうくイントロだけで終わるとこだったぜ〜、ふぅ。というか、書き上げる前日にようやく思いついたという、なんとも崖っぷちな感じなのです。ここまでの話で終わっていると、「はい、作りました」なだけで僕的に面白くないな〜と思っていたのです。やっぱり、暁のコーダ部屋は無駄なところに無駄に労力をかけて、実用性とは違うところで人をうならせたいのです(笑)。

高速化のツボ

この時点ですでに計測するためのプログラムのバージョンは 10 になっており、それぞれのプログラムを比較検討することでネックとなる部分を考察していたのでした。で。

・・・・いけてねぇ〜

重大なことを忘れていました。V30MZ が 1 クロックで取り込めるのは 2byte までだったのです!!。 ということは、
AND reg, imm
などの命令はすべて 4byte なので、命令フェッチに 2 クロックかかっていたのでした。どうりで実行クロック数を減らしてもフレームレートがあがらないわけです。くそぅ。

今ごろ気づくのも遅すぎ〜と思いつつ、それを念頭に今までのコードを見直してみると確かに納得できました。ということで、高速化する場合には長い命令を避ければよいのです。そう思って、今までのコードを再び振り返ると、2byte 即値がこれでもかというほどありますね(笑)。いやはや、まったくもっていけてなさすぎ〜

2byte 即値を禁止するとなると、書き込む位置を可変にする方法は途端に不利になります。マスクをレジスタに保持し、そのレジスタをローテイトで回すことも考えられますが、命令数が増えるので却下です。そういうわけで、たまたま偶然、最初に作ったコードが WORD 配列の場合の最速状態になっていたのでした。

BYTE 配列化

まだ話は続きます。なんとかして BYTE 配列にしたいのです。どうしてかというと、WORD 配列ということは 16bit あるうちの 2bit しか情報が格納されていないわけで、14bit が無駄に使われているのがあまりにもあんまりなので、せめて 6bit の無駄に抑えようよ〜、ということです。メモリも少ないことですしね。

さて、BYTE 値にどのような形で保存しておくにしろ、なにがしかの操作を経て、WORD 値の 0000000A 0000000B の形式にするわけです。どう料理しますか。これまでの僕なら、BYTE 値の形式を A000000B として、迷わず
AL : BYTE 値
AH : 0
 
add AX, 0x0080
and AX, 0x0101
としているところですが、これは 2byte 即値命令が 2 つなので最悪ですね。そうなると、
shl AX, 1
shr AL, 1
こんなところでしょうか。実際のプログラムの流れの中で使うとすると、 このようになります。
AX : 転送元画像 X 座標(8:8 固定小数点表現)
BX : 転送元画像配列インデクス
CX : 合成後のデータ(ラインバッファ形式)
DX : データ読み出し・加工用
DI : 拡大係数
 
mov BL, AH
add AX, DI
xor DX, DX
mov DL, [_tempBuf + BX]
shl DX, 1
shr DL, 1
or  CX, DX
shl CX, 1
データ合成後の DX には値が残っているので、次に使うときにいちいちクリアするのがかなりイヤな感じがプンプンです。それでも、2byte 即値はすべて排除できたので見た目どおりの性能を発揮することでしょう。

ソリューション

後輩の作ったプレゼンテーションを見たら、こんな言葉を使っていて、なんとなくかっちょえぇかなぁという気がしたので使ってみました(笑)。わけわからんね。

さて、実は、データ合成後の DX のクリアは必要なかったりします。上位 BYTE の DH の最下位 bit に移動した値は、次回のシフトで 1bit 上位へ移動してくれます。ということは、ゴミにもなんにもならないのです。驚いたことに、処理を 8 回繰り返した後の DH には合成した値がそのままの形で格納されています。

では、DL の値はどうでしょうか?残念、書き込む位置が悪いのでそのままの形では使えそうにありません。そう思ったあなたはまだ甘い。8bit でローテイトを繰り返せば最終的には図5のような並びになるではありませんか。

8 回処理した後の DL(理想)

図5. 8 回処理した後の DL(理想)

実際には、mov DL,[BX] で書き込んでいますから図 5 のようにはなりません。となると、or DL,[BX] にすればいいでしょうか?ブブー、外れです。そんなことをすると、6 回目の処理で色の上位 bit とぶつかってしまいますね。ということで、別のレジスタに格納することにしましょう。こんな感じです。
AX : 転送元画像 X 座標(8:8 固定小数点表現)
BX : 転送元画像配列インデクス
CL : 合成後のデータ(下位 BYTE)
DL : データ読み出し・加工用
DH : 合成後のデータ(上位 BYTE)
DI : 拡大係数
 
mov BL, AH
add AX, DI
mov DL, [_tempBuf + BX]
shl DX, 1
or  CL, DL
rol CL, 1
かなり短くなりました。さて、このような処理を 8 回繰り返した後は図 6 のようになっています。となれば、CL を逆に回し、 DL にコピーすれば DX に合成後のデータが格納されるって寸法です。で、そのプログラム。
アーカイブ:32-wwexpand9.lzh (8883 bytes)
プログラム:32-wwexpand9.c (5829 bytes)
で、そのコードはこんな感じに。
WORD t[8];
WORD tx;
tx = sx;
sy = ty;
for(j = 0; j < 8; j ++)
 {
    sx = tx;
    t[j] = 0;
 
    _asm_expand_first("", sx, sy, ratio);
    /* AX<-sx BX<-sy CX<-ratio *
push dx push di mov di, cx xor cl, cl add bx, _tempBuf add ah, bl /* 1dot目 *
mov bl, ah add ax, di mov dl, [bx] add dx, dx or cl, dl rol cl, 1 /* 2dot目 *
mov bl, ah add ax, di mov dl, [bx] add dx, dx or cl, dl rol cl, 1 /* 3dot目 *
/* 4dot目 *
/* 5dot目 *
/* 6dot目 *
/* 7dot目 *
/* 8dot目 *
mov bl, ah add ax, di mov dl, [bx] add dx, dx or cl, dl ror cl, 1 /* 終了処理 *
mov ah, dh mov al, cl pop di pop dx t[j] = ax; sx += ratio <<3; sy += 0x100; } font_set_colordata(cnt ++, 1, (char far*)t);
で、実行結果ですが・・・・ 15.6FPS にまで速くなりました。ちなみに、ブレゼンハムを併用すればもっと速くなるかと思いましたが、オーバーヘッドの分で見事に低速化する見通しがたったので実装を途中で止めました(笑)。実行中の画面はこんな感じになってます。See Fig.6.

実行画面
図6. 実行画面

仄香セイバーソースコードプレゼント結果発表

さて、長々とひっぱりましたが、結果発表です。暁のコーダ部屋10000Hit記念プレゼント〜ということで抽選で10名様に仄香セイバーのフルソースをプレゼント、ということでした。それでは、発表します。

厳正なる抽選の結果、当選者は以下の方に決まりました。

史月 望さん
史月 望さん
史月 望さん
史月 望さん
史月 望さん
史月 望さん
史月 望さん
史月 望さん
史月 望さん
史月 望さん

え?コピペしたまんま?いやいや、違います。これでいーんです。応募総数1、当選確率1000%(当選しすぎ)の高確率での抽選になりました(笑)。

ということで、史月さんには10枚のCD-R(焼き込み済み)が贈られます。わ〜パチパチ。

それにしても、この結果はまったく予想してませんでしたね〜。〆切まで半分程度たったところで、このまま誰も応募してこなかったらどうしようと思っていましたけど。当選者がお1人ということで、価値がでてきたような気もしますね(笑)。

さて、そんなこんなですべての企画がうまくいくというわけでもないことがはっきりしたわけですが、読者の方々のリクエストは随時受付中です。すでにいくつかのリクエストを受けて構想を練っていたりもするので、リクエストがいつ表に出てくるかはわかりませんが。読者の拡大にははげみませんとね。

え?それよりも応募者の拡大が先決ですか。あぅ、痛たたた。
それでわ。

参考文献

  1. 記憶の中の果てなき世界 WakuWakuさん
    もはや WonderWitch でプログラム開発をしている人で知らない人はいないはず、の bmpsaver を利用しました。XMODEM での保存が便利。ってーか、なぜか /ram0/ に保存できなかったので、根性なしの僕ちゃんはさくっと XMODEM で保存することに切り替えたのでした。許可してもらえるなら高速化したみたい気はかなりあったりします。ソースを見るといろいろ面白そうなので。

  2. V30MZ Caribbean Seaさん
    WonderSwan における高速化をする上で参考になります。ってゆーか、命令フェッチにかかるバスサイクルの問題は、こちらのページを参照していなければ100年たっても気がつかなかったはず。でも、参照していても忘れていたら意味ないじゃんよ〜(笑)

Virtual Payment System100えん10えん1えんヘルプ

第33回拡大の逆襲 for WonderWitch
戦いの序曲

前回は、有能なWonderWitchのクリエイターの創作意欲を拡大することを目的にしていたのですが、どうやら対象が有能なプログラマーまで拡大してしまったらしく、痛いところをつかれてしまったのでした。なにかというと、匿名感想(一ヶ月に一通ぐらい)なのです。

いつもながらすげぇです。
なにかと使わしてもらいます。m(_ _)m
 
でも、C言語の最適化(?)には目がいってないのでしょうか。(^^;
ちょっと謎な部分があります。(既知かな?)
 
・txはいらない
・jループ先頭の t[j] = 0 は無駄
 
と思うのですがどうでしょうか。
 
・t[j]=0 を削除
・iループ前で ratio << 3 を計算しておき、jループを抜けた後sxに足す
 
と変更した所、17.8fpsくらい出ました。
フルアセンブラもっとイケソウっすね。(☆_-
むむむ。確かにそのとおりです。最初見たときは、あまりの FPS に、LSI-C を使ってないんじゃないの〜?と思いましたが、試してみると・・・・うそ〜。何故だかわかりませんが、やけに ratio << 3 のコストが高くついていたのでした。言い訳してもいいですか、いいですね。じゃぁ、します。えーと・・・・しまった、言い訳できねぇ(笑)

それはともかく、どう考えても挑戦的なこの発言に魂が燃えたのでした(笑)。

作戦

前回の最終コードを書いている時点で、レジスタ効率が非常に高いことには気がついており、事実、CH と SI は使用していませんでした。となると、やることは一つです。もう一つ外側のループまでアセンブラにしましょう。フルアセンブラにすればいいという話もありますが、それは徹夜明けの頭にはつらいです(笑)。とりあえず、びっくらこかせればそれでい〜んです(なんちゅ〜目標だ・・・・)。

とりあえず、CH はループカウンタにします。SI は何に使いましょうか。考えるまでもありません。フォントデータを定義するための一時的な配列、WORD t[8] を指すことにしましょう。

上陸

そういうことで、今度こそ落ち度のないように(笑)、じっくり見つめて無駄を省いてみました。ループ内で push/pop しているのがちょっとイヤですが、レジスタが足りないのでしょうがありませんでした。やっている内容的には以前と変わらないので説明は以下略です、って単にめんどくさく思ったとかいうのは秘密。

で、そのアーカイブ33-wwexpandb.lzh (9003 bytes)とプログラム33-wwexpandb.c (6191 bytes)。

cnt = 0;
sy = 0;
tx = ratio << 3;
basex = ((WIDTH/2)<<8) - ((WIN_WIDTH/2*8) * ratio);        /* 左端の位置を求める *
for(dy = 0; dy < WIN_HEIGHT; dy ++) { sx = basex; for(dx = 0; dx < WIN_WIDTH; dx ++) { WORD t[8]; _asm_expand_first("", sx, sy, ratio, (WORD)t); _asm_expand("push si\npush di\nmov si, dx\n"); _asm_expand("mov di, cx\n"); _asm_expand("mov ch, 8\n"); _asm_expand("add bx, _tempBuf\n"); _asm_expand("add ah, bl\n"); /* ax := x座標 bx := 参照データアドレス cl := 合成用 ch := ループカウンタ dx := 合成用 di := ratio si := 合成データ転送先 *
_asm_expand("loop_point:\n"); /* ループ開始 *
_asm_expand("push ax\n"); /* 1dot目 *
_asm_expand("mov bl, ah\nadd ax, di\nmov dl, [bx]\nadd dx, dx\nmov cl, dl\nrol cl, 1\n"); /* 2dot目 *
_asm_expand("mov bl, ah\nadd ax, di\nmov dl, [bx]\nadd dx, dx\nor cl, dl\nrol cl, 1\n"); /* 3dot目 *
/* 4dot目 *
/* 5dot目 *
/* 6dot目 *
/* 7dot目 *
/* 8dot目 *
_asm_expand("mov bl, ah\nmov dl, [bx]\nadd dx, dx\nor cl, dl\nror cl, 1\n"); /* 書き込む *
_asm_expand("mov dl, cl\nmov SS:[si], dx\ninc si\ninc si\n"); _asm_expand("pop ax\n"); _asm_expand("inc bh\n"); /* sy += 0x100 *
_asm_expand("dec ch\n"); _asm_expand("jnz loop_point\n"); /* 終了 *
_asm_expand("pop di\npop si\n"); sx += tx; font_set_colordata(cnt ++, 1, (char far*)t); } sy += 0x800; }

Mission Complete

で、実行結果。23.5FPS。よっしゃ〜。どうだ、見たか〜。あ〜、よかった、よかった。それにしても、200x40 でこれだけ出ればちょこっとした部分で拡大を使うことが現実的になってきますね。なんか、考えてみよっと。

補足

多少敵意のこもった文章になっていますが、脚色したためであり、実際にはそんなことはありませんので気を悪くしないでください>匿名希望さん。3時間とたたずに更新したのは、面白かったからです(笑)。また感想くださいね。

それでわ。

Virtual Payment System100えん10えん1えんヘルプ

第34回エミュのススメ
はじめに

今日は故あって、一人で考え事をすべくファミレスで夕食でした。結論から言えば、午後7時頃のファミレスは一人で考え事をするにはまったく向かないということが収穫でした(当たり前)。その要因の一つはタバコの煙にあることは言うまでも(いや、言うべきか)ありません。僕はタバコを吸いませんし、タバコの煙にも弱いのです。昔はそんなでもありませんでしたが、ある時期を境にタバコの煙の臭いがキツくなったように思います。でも、誰も同意してくれません。何故だ。

そんなですから、食事しているときに横でタバコを吸われるのは不愉快です。ましてや、カウンター席に座っている人が、今まさに料理されている僕に出されるであろう料理に、煙をフーッなどと吐くのは見ていてロケットパーンチしたい思いです。で、煙を吐いているバカ本人はどうかというと、当然のことながらそんなことは全く気にもしていないわけです。

DirectDraw の幻影

こんなように、人間、自分のしていることがその人の常識なので、その行動が実はあまりよろしくないことであってもそれに気がつくことはそうそうないのです。これは、DirectDraw にも共通することです。ゲームプログラムを作るときに DirectDraw を使って作ることは常識であり、DirectDraw を使ってさえいれば、常に最適なパフォーマンスを得られると思い込んでいる人が少なくありません。しかし、それは幻影です。

ぎゃるぱにXはノートパソコンでも開発をしているわけですが、このノートパソコン、一部の人の間では悪名高い NeoMagic(今は亡き・・・・か)製です。なにが腹立つって、色抜き転送をハードウェアで持っていないくせに DirectX の問い合わせに対して持ってるなどと言いやがる(らしい)のです。その結果、どうなるかというと、正直者がバカを見るわけで、普通に(というか、常識的に)DirectDraw を使ったプログラムを作ると、ノートパソコンでは遊べないほど遅くなるのです。自分で作ったプログラムであれば、サーフェスを強制的にシステムメモリに取ればいいだけなのですが、コンパイル済みの実行ファイルで同じことをするにはバイナリ書き換えが必要となり、試す気にもなりません。

さて、世に出回っている同人ゲームの多くは正直な方が作られているようで、僕のノートパソコンで遊ぼうと思うと重くて動かなくてイヤ〜ンなのです。こんなときにどうするかというと、ハードウェアアクセラレーションのレベルを下げて実行です。そうすると、DirectX は自動的にエミュレーションモードになり、すべての動作は CPU によって実行されます(多分)。実際、2D のゲームであればこの方法で遊べるようになります。この方法の難点は、Windows の動作が目に見えて遅くなることで、ゲームをするときにはいちいち再起動しなおすことになります。

エミュレーションモードの使用

エミュレーションモードは、すべての処理を HEL(Hardware Emulation Layer)で実行しているわけで(多分)、色抜き転送であってもソフトウェアで実行しているはずです。もしノーマルモードでエミュレーションモードと同じ効果を得たいのであれば、ソフトウェアで実行されるような環境を作り出せばよいのです。その答えの一つはサーフェスをシステムメモリ上に取ることなのは簡単に想像できます。ただし、実際にソフトウェアで処理されるかどうかは、ビデオボードのドライバに依存しており保証はされません。まぁ、普通に考えれば転送元と転送先の両方のサーフェスがシステムメモリ上に存在しているのにハードウェアで転送しようと考えるプログラマはいないでしょう。どちらか片方でもビデオメモリにサーフェスをとっていたりすると話はわからなくなりますが。

ここで確認しなければなりませんが、ノーマルモードでシステムメモリにサーフェスを確保することと、エミュレーションモードを使用することが等価であるか、は不明であります。もしかしたら、HEL と HAL の間にオーバーヘッドが存在していたりすると、エミュレーションモードの方が有利になりかねません。というわけで、計測テストは通常プログラムを組んだ場合に相当する、ビデオメモリにサーフェスをとった場合と、エミュレーションモードで起動したときの後ろめたさを避けるべく(笑)ノーマルモードで起動してシステムメモリにサーフェスをとった場合、そして問題のエミュレーションモード、の3つについて行いました。

プログラムとしては別段難しいことをしているわけではありません。DirectDraw オブジェクトの初期化をするときにエミュレーションモードにするだけです。yaneuraoGameSDK ver1.62 では、yaneDirectDraw.cpp 内の CDirectDraw::Initialize メソッド内の
m_lpDirectDraw->Initialize(NULL);
m_lpDirectDraw->Initialize((GUID*)DDCREATE_EMULATIONONLY);
に変更すれば OK です。

実験方法

今回はただのベンチマークにならないよう、ぎゃるぱにXにおけるオブジェクト操作に近いプログラムにしてみました。このプログラムをベースにすればゲームを作ることも夢ではないかもしれないかもしれません(えらく不定形だな〜)。オブジェクトのパターンは実際にぎゃるぱにXで使用しているものを謎さんに許可を得た上で添付しておきます。さらに、都市夫くんの弱みを握ったことで背景(落書き?)もサービスだ。アーカイブはこちら34-dxtest.lzh (220020 bytes)。コンパイルには yaneSDK 1.62 あたりが必要です。

実行画面
図1:実行画面

実験結果

なんか、すべてのハードウェアアクセラレーションレベルに対してテストしたりで、それはもう大変でしたが、いらない結果はゴミ箱にポイ、です。ううう。色深度もすべて試しましたが、ここでは 640x480、8bpp での結果だけを示します。その他の結果は34-result.txt (3542 bytes)に。

表1:実行結果
実行環境Frame Per Second (目盛りは 5,10ごと)
Athlon 1000MHz
G-Force DDR
PentiumII 333MHz
RIVA TNT2Ultra
PentiumII 266MHz
Diamond StelthII G460 (i740)
Let's note CF-S23
モバイルCeleron 300MHz
NeoMagic MagicMedia256AV
VAIO PCG808
モバイルPentiumII 266MHz
NeoMagic MagicMedia256AV
IBM ThinkPad 560E
MMX Pentium 166MHz
Trident Cyber 9382

考察

意外なことに、ビデオメモリにサーフェスをとった場合のパフォーマンスがよろしくありません。今回のテストではオブジェクト数が 4000 程度になっており、矩形転送の数が同数あるのですが、高々 4000 回程度の矩形転送のデータ量が多いと考えるのもツラい気がします。試しに、オブジェクト数を 0 にすると矩形転送がネックではないことが確認できます。また、オブジェクト数が多くなっている状態の結果を比較すると、リフレッシュレートが原因ではないことがわかります。適合パレットの問題でもないようです。

さて、何が原因でノーマルモードが遅いのかはどうでもいいのでした。得られた結果がすべてです。で、その結果はというと、すべての環境において平均的に速度を出せるのはエミュレーションモードです。システムメモリを使った場合でもあまり問題はないように見えますが、実はオブジェクト数が少ない場合にはエミュレーションモードのほうが速かったりするのでした。FPS のブレが激しく、測定できないので結果が示せませんが。

もう一つ面白いことがわかりました。背景を DirectDraw の BltFast で転送した場合と、サーフェスをロックして memcpy で転送した場合の比較です。エミュレーションモードとシステムメモリを使った場合の比較になるわけですが、どちらでも大きなパフォーマンスの違いはありません。

まとめ

なんか、よくわかりませんが、2D のゲームを作るなら DirectDraw を使うことのアドバンテージがほとんどない、ということです。背景の転送のような広い領域であれば DirectDraw にアドバンテージがあるかと思いましたが、それほど有効ではないようです。測定した環境のビデオドライバが最新であることは確認していませんが、実際にゲームをする人が最新にしているという保証もないのでこれは問題ないでしょう。

そういうわけで、2D のゲームであれば、自前でメインメモリ上にサーフェスを構築してソフトウェアで合成をしたほうが、回転などの機能も実装でき、かつ高速であるかもしれない、という可能性が示されたわけです。この方法を取れば、サーフェスのロストも発生しませんからサーフェスをキャッシュのように使うことや、サイズ制限のないサーフェスを利用することも、ドライバの更新なしに可能です(笑)。このあたりをサポートしたかわりに DirectDraw を切り捨てた DirectX8 を使うよりも信頼性は高そうな気が・・・・しませんか?

本当は別の目的のために作ったサンプルでしたが、使いまわしが効くので嬉しいですね。というわけで、そのうちやりたいような気がしなくもないこともない弾幕の作り方にはこのサンプルを使うことにしましょう。それでわ。

補足(2001/04/12)

コンパイルできねぇよ、クソが!というコメントをいただいた(あ、いや、もっとこう、普通な言い回しでしたが)のでちょこっと(ちょびっつではなく)コンパイルのしかたを。

まずは弾幕用プログラムソースをダウンロード34-dxtest.lzh (220020 bytes)。やねさんとこからYaneuraoGameSDKをダウンロード。1.xxはすでに隅に追いやられています(笑)。トップページから Download → yaneuraoGameSDK1st関連のダウンロードへ進み、yaneSDK version1.63をダウンロードしてきます。してきました。

こんな感じにアーカイブを展開。

+dxtest
   +src (dxtest.lzhを展開)
       -emu.cpp
       -nae.bmp
       -spark.bmp
       -util.cpp
       -util.h
   +ygsSDK (yaneSDKを展開)
      +config
      +YTL
      +クラスリファレンス
      +マニュアル
      -stdafx.cpp
      -stdafx.h
      -....

VisualC++6を起動し、新規作成→Win32 Applicationを選択します。プロジェクト名を適当に入力し(dxtest)、ディレクトリも適当に指定(d:\dxtest\src)します。

OKで次に進み、そのまま終了を押します。最後の確認もそのままOKです。

これでプロジェクトが用意されたわけですが、ファイルを追加しなければなりません。画面左の方の FileView タブを選択し、Resource FilesとHeader Filesを選択→Deleteキーで削除してしまいます。その後、dxtestファイルを右クリックしてフォルダを作成します。フォルダ名には yaneSDK、ファイルの拡張子には cpp;h と入力します。

いよいよファイルを追加します。Source Files上で右クリックし、ファイルをフォルダへ追加を選びます。srcの下のemu.cpp、util.cpp、util.hを選択(emu.cppを選択した状態でCtrl+Aで全選択できます)してOKを押します。同様にしてyaneSDKのファイルをyaneSDKフォルダに追加します。

これで準備が整いました。さて、実行・・・・の前に保存しておきましょう。すべて保存を実行後、おもむろに F5 を押します。ビルドするか聞かれますので、そのままRETURNをこぎみよくターンと叩きます。しばらくまてば実行される・・はずです。試してみたところ、1.64/aだとコンパイルエラーが出るので1.63でお願いします。

Virtual Payment System100えん10えん1えんヘルプ

第35回キレイな弾幕は好きですか?
はじめに

みなさん、ざわざわ。う〜ん、段々飽きてきたな・・・・。さて、綺麗なお姉さんは好きですね。さらに言えば、綺麗でやさしいお姉さんはもっと好きです。そんなお姉さんも最近は妹ブームにおされてるようです。僕には妹はいませんのでどうなのかは知りませんが、友達を見ているとそんなに守ってあげたそうにしているようには見えませんねぇ。そうか、それはあくまでも建前なのくぁ!う〜む、奥が深い(笑)

そうそう、友達と言えば、最近、ちまちまとメールで交友している方がいます。僕は友達が少ないので、その人がどう思っていようと勝手に友達の数に入れてしまうのです。そういうわけで、僕にメールを出す人はおともだちになろうと思ってメールを出さねばなりません(笑)

何度必要?

冗談はさておき(どこが冗談なんだか・・・・)、弾幕サンプルのプログラムを見てもらったところ、1周4096度もあるんですね、との感想をいただきました。最初の段階では、確かに1周256度で作ったのですが弾幕を吐かせたところ、模様が崩れてしまうことがあったので4096度に増やしたのでした。しかし、よくよく思い出してみると、256度だったころは固定小数点の小数点以下が6ビットしかありませんでした。で、4096度に増やすときに16ビットに変更したわけです。ってことは・・・・もしかしたら、そっちのほうが原因なのかもしれません。ちょっと計算してみましょう。1周256度において、1度(以降、1[256]度と表記する)ずれた場合にどれだけ誤差がでるのでしょうか。

sin(2.0*PI /256) = 0.0245

う〜ん、どうなのかよくわかりませんねぇ。これが弾幕にどれだけ影響するかは実際に適用することを考えれば簡単です。ゲームでの最大誤差が発生する場合として画面の対角線を仮定します。画面左上から画面右下に弾を一発撃ち、1[256]度だけずらしてもう一発撃ちます。前者が画面右下に到達したときに後者の位置との間には弾が撃てないことになります。角度の解像度が足りませんからね。これが、1ドットよりも小さければ直線移動する弾で構成される弾幕なら絶対に模様が崩れないことが保証されます。たとえば、解像度 640x480 の画面のゲームだとすると、画面の対角線長は 800 ドットになります。1周256度でこれを計算すると・・・・

sin(2.0*PI /256) * 800 = 19.633

全然足りません。なんとなく決めたぎゃるぱにXの1周4096度ではどうなるでしょうか。

sin(2.0*PI /4096) * 800 = 1.227

おぉ、これなら容認できるレベルでしょう。1周8192度にすれば 0.6 程度になりますが、sin/cos のテーブルサイズが大きくなるので注意がひつようだよ。1周4096度では 4096+1024 要素ですから (4096+1024)x sizeof(int) = 20480 bytes = 20KByte でちょっと大きすぎのような気もしますけど。8192度にしたい人はしてもかまいませんけど、8192度は2の13乗ということで不吉な数なので心しておくこと(適当なこと言うなよ・・・・
(2001/04/12) (4096+1024)x4=2560? う〜ん、どうしてそうなったんだろう・・・・

実験

640x480における最大誤差が 19 ドットということはわかりましたが、実際のところどうなのかを試してみましょう。前回のプログラムをああやってこうやって・・・・できた〜。まずは 1 周 256 度で弾幕を吐かせてみます(図1)。

1周256度での攻撃
図1:1周256度での攻撃

かなり乱れてます。で、ちょこちょこっと変更すると 1 周 4096 度にアップグレードです(図2)。もちろん、無料ですよ(笑)

2周4096度での攻撃
図2:2周4096度での攻撃

ばっちりです。これだけ違うと 4096 度にする気になりませんか?ちなみに、弾を飛ばす角度を計算する時点で精度を気にして計算しなければ、いくら角度があっても足りませんよ。要注意です。

まとめ

巷のゲームが 256 度にしているか、4096 度にしているか、そのあたりの情報が全く見当たらないのでわかりませんがぎゃるぱにXでは 256 度では足りてません。多少なりとも参考になりますかね?ちなみに、弾を画面中心から発している分にはあまり違いがわかりませんでした。計算上は 10 ドットぐらいの誤差はあるはずなんですけど・・・・。それはともあれ、弾幕が乱れているようなゲームは売れるわけがない(というよりも、作ってて気になってしょうがないのです)ので、やはり 4096=12bit は必要でしょう。そうです、売れるゲームには 12bit が必須なのです。だから売れる妹ゲームに 12人いるのは必然なのですよ。って、売れてるんでしょうか(笑)

それでわ。

Virtual Payment System100えん10えん1えんヘルプ

第36回Microsoft的コンパイラ実装法
はじめに

みなさん、ざわざわ〜。かなり間が空きましたが、僕は元気・・・なのかなぁ・・・。元気かどうかはともかく置いといて、生きているといろんなことがあるものです。

「さ〜くん、今日、こういう提案をしたいんだけどどうかな?」
「はぁ。その提案でどうなるんですか?」
「それを今日話し合うんじゃないか」
「・・・。」

迂闊なコメントは避けておくことにします(笑)。

Undefined な定義

次のコードは、あるプログラムをデバッグしていて、見つけたコードです。
a = func( ) + func( ) * 2;
別にこのコードを見つけたことがすごいとか言うのではないので、お間違えなきよう。賢明なる読者諸君はご存知だと思いますが、C 言語ではこの場合の結果は undefined、定義されません。要するに、不定ってやつです。結果が何になろうとも文句を言ってはいけません。なので、文句を言うつもりは毛頭ありません(くどいな・・・

このコードを書いたのは僕だったりするので、強く言えないってのもありますが、一様な分布の乱数を二回加えることで正規分布の乱数を得られる(らしいってのをどこかで読んだ)わけで、そのような場合に
a = rand( ) + rand( ) * 2;
と書いてしまうのは仕方がないことです(僕的に)。この二つの rand は並列実行されない限り、順序依存の命令であるにも関わらず、評価順序は結果に影響しません。理想では。 他にも、画面上のランダムな場所に点を打つ場合に
point(rand( ), rand( ));
と書いてしまいます。ちょっと確信が持てなかったので、今 プログラム言語 C 第 2 版を買ってきて確認しましたが、関数の引数に関しても評価順序は undefined でした。 point 関数が実行される前に二つの rand 関数が評価されることは defined ですが、x、y どちらの rand 関数が先に実行されるかは undefined です。もしかしたら(そのようなことが有りうることを規定しているかは知りませんが)常に x==y となるようなコンパイラもあるかもしれません。でも、一般的な処理系において、単一のタスクとして実行する分には、画面内の一様な点として現れるはずです。

Undocumented な undefined

一通り自己弁護および一般知識の共有が終わったところで、次のコードを見てください。
#include 
 
int n = 0;
int func(void)
 {
    n ++;
    return n;
 }
 
void main(void)
 {
    int a = func( ) + func( ) * 2;
    printf("%d\n", a);
 }
見てのとおり、main 関数のアレがソレです。func 関数は、呼び出すごとに 1,2,3,・・・と順番に返しますので、最初の func 関数が先に評価されるのであれば、
a = 1 + 2*2
となり、5 が表示されます。逆に、後ろの func 関数が先に評価されるのであれば
a = 2 + 1*2
となり、4 が表示されるのは言うまでもありません(言ってるって!

Microsoft 流 undefined

Visual C++ で上記のコードをコンパイル実行します。結果がどうなるかというと、4 が表示されました。で、隣の席に転がっている SGI のマシンで試したところ、5 が表示されました。ということで、Microsoft は逆向きなんですよ、評価順序が!

とかいうどうでもいいことは言わなくてもいいのでした。Visual C++ でコンパイルしたときの条件を言うのを忘れていました。release ビルドでコンパイルしました。こーゆーのはコンパイラ依存ということですから、debug ビルドで実行しても結果は変わるはずありません。

実行してみました。
・・・
5

Microsoft は逆向きなんですよ、評価順序が!!。それはもう、倒置法になってしまうぐらいびっくりです。富野さんもびっくりです(違

そんなわけで、ぎゃるぱにXのリプレイデータが再生できないのもしょうがないのです。いや、再生できない直接の原因ではぜんぜんないんですけども。

まとめ

という事情がありますんで、Visual C++ で debug ビルドと release ビルドで同じ挙動を得たい場合には、一行に同じ関数を二度使うこともままなりません。生きにくい世の中ですが、さすがに逆になってしまってはどうしようもありません。そーいえば、冒頭の件、僕には本末転倒、逆も逆、逆が二つで2乗になったらそれこそギャグにしか見えません、とつまらんオチで終わります。あーつまらん。

でわ。

Virtual Payment System100えん10えん1えんヘルプ

第37回お手軽なCSG描画
はじめに

みなさん、バリバリ〜。ここのところ忙しいので更新がおざなりになってますが、日常生活には面白いネタがたくさん転がっているわけでして、そのようなネタを腐らせてしまうのでは、夢に出てきてうなされてしまいます。もったいない、もったいない。そんな勾玉の輝きをもつネタ(そんないいもんか?)を紹介することにしましょう。それは、ストレス発散にボーリングに行ったときのことです。隣のレーンに入ってきたのは男4人、女3人の高校生ぐらいの雰囲気の方々でした。別段、珍しい格好をしているでもなく、まぁいまどきそこらに二束三文で転がっているような(ひどい言いようだな・・・)少年少女です。(うわ)

当然、僕も気にかけていませんでしたが、彼らがゲームを開始した瞬間から僕の意識を引き留めて離さないという強烈なインパクトを与えられてしまいました。なにが起こったかというと、最初の投球をしようとしている二人の女の子が裸足のままレーンにあがったのです。確かに、その光景はなにやら艶めかしい雰囲気をかもしだしてはいるものの、あの室伏選手が雄たけびをあげて投げるハンマーに匹敵するほどの重さを持つボーリングの玉を裸足で投げるなどという危険な行為は見るものを惹き付けて離さない魅力でいっぱいです(なにを言ってるんだか)

ま、当然の事ながら店員が飛んできて靴を履くようにとの教育的指導(文字通り)が発せられたわけです。で、彼らは目出度く、ボーリングには靴を履かなければならないということを学習したわけですが、彼らもバカではなかったようです。

彼らは、僕を始め周りにいた友達の誰も予想だにしなかった解決法をとったのです.それは、男女1足ずつ借りるという方法です。いや、まぁ、確かに1人1足とはどこにも書いてないけど・・・。その驚愕の事実に気がついたとき、僕は自分の迂闊さを激しく呪ったのです。男の1人が「おれ、25.5でもはけるよ」と言ったときに、なぜ気がつかなかったのか、と。

さて、一つのものでどうにかやりくりすると言うと、僕の中ではステンシルバッファがヒットします。そう、ステンシルバッファを使って CSG を描画する方法です。その方法は、ステンシルバッファを通しいくつかの状態でレンダリングすることによって体積素間の演算結果を描画するのですが、ステンシルバッファは一つしかない(少なくとも OpenGL では)ので、それはもう聞くも涙、語るも涙なのです。隣のレーンでどこかの家に上がるがごとく、順番が来るたびに靴をそろえて上履き(ボーリングシューズ)に履きかえる様を横目で観察しながらそんなことを思っていたのでした。

体積素間の演算

最初に CSG ってなんじゃらほいって人のために簡単に説明しておきましょう。正確性には自信がないですが。CSG は Constructive Solid Geometry の略で、ソリッドモデルの物体同士を組み合わせてソリッドを定義しようって魂胆のことです。ソリッドを体積の存在する空間とそうでない空間として考えることで、物体同士の組合せを空間に対する演算として定義することができます。一項演算としては、反転である not があり、二項演算としては空間の包含関係に基づき、図 1 のような or、and、sub、xor などが定義できます。

or演算
(a) or演算
and演算
(b) and演算
sub演算(A-B)
(c) sub演算(A-B)
xor演算
(d) xor演算
図1 二つの領域に対する演算

これを三次元空間の体積素に対して適用すると、図 2 のような結果が得られます。

物体A
(a) 物体A
物体B
(b) 物体B
A or B
(c) A or B
A and B
(d) A and B
A sub B
(e) A sub B
B sub A
(f) B sub A
図2 二つの体積素間の演算例

ステンシルバッファを用いた CSG 描画

CSGの実装法としては、ボリュームレンダリングや律儀に B-reps を求める方法、レイトレーシングちっくに視線との交点を順次求める方法などが利用できます。ボリュームレンダリングはハードウェアで持つものも出てきたようですが、未だリアルタイムレンダリングに用いるには低速・複雑であります。これらの問題を回避する方法として SIGGRAPH で発表されたステンシルバッファを使った方法があります。

まずは、ステンシルバッファを用いた手法について、簡単に述べておきましょう。より詳細な情報を知りたい方は、新坂さんのページなど、参考文献をあたってください。和の演算はステンシルバッファを使うまでもなく、Z バッファを用いて Z 値のテストを行いより手前の面を描画するだけで実現できるので、省略します。

差演算を A - B として表現した場合、体積素 A、B の位置関係によって描画結果は 3 つに分類できます。

(a). 体積素 A の前面より前に体積素 B 全体が存在

この場合、体積素 A は演算の影響を受けません。したがって、描画結果は体積素 A を描画しただけのものと等しくなります(図 3 )。

体積素 B が 体積素 A の前面より前にある場合
図3. 体積素 B が 体積素 A の前面より前にある場合

(b). 体積素 A の前面をはさんで体積素 B が存在

この場合には、体積素 A の前面は見えなくなり、体積素 B によって切り取られた体積素 A の断面が見えることになります(図 4 )。

体積素 B が 体積素 A の前面をはさんでいる場合
図4. 体積素 B が 体積素 A の前面をはさんでいる場合

(c). 体積素 A の前面より後方に体積素 B が存在

この場合、見える面は体積素 A の前面のままです(図 5 )。

体積素 B が 体積素 A の前面の後方にある場合
図5. 体積素 B が 体積素 A の前面の後方にある場合

ステンシルバッファは、描画対象に変更が必要な(b)の状態を検出し、マスクするために使用します。(b)の状態の条件を考慮して、ステンシルバッファにマスクを生成する手順は次のようになります。

  1. ステンシルバッファの各ピクセルに対し、体積素 A の前面より体積素 B の前面が前方にあるなら 1 に、そうでなければ 0 にする
  2. ステンシルバッファの各ピクセルに対し、体積素 A の前面より体積素 B の背面が前方にあるなら 0 にする
この手順は、OpenGL や DirectX の API の組合せで表すことができるため、ハードウェアが対応していれば高速に処理することが可能です。

さて、(a)、(c)の領域に対しては体積素 A を通常のレンダリング方法で描画すればいいとして、(b)の領域には何を描画するかを考えねばなりません。(b)の状態をさらに分類すると、次の二つに分けることができます。

(b.1). 体積素 B の背面が体積素 A の背面より前方に存在

この場合には体積素 A の断面が見えることになります(図 6 )。

断面が見える場合
図6. 断面が見える場合

(b.2). 体積素 B の背面が体積素 A の背面より後方に存在

この場合には体積素 A は見えなく、背景色が見えることになります(図 7 )。

背景色が見える場合
図7. 背景色が見える場合

この分類にしたがい描画するためには、体積素 A と体積素 B の Z バッファの値を比較することで実現できます。OpenGL ならデプスバッファに体積素 A をレンダリング後、depthFunc を切り替えて、体積素 B をレンダリングすればいいわけです。このあたりの詳細には触れません。これ以上触れようとすると、新坂さんのページと同じ内容になってしまいます(笑)

体積素間の積演算(AND)に関しても同様の分類を行うことで実装が可能となります。面倒になってきたので以下割愛。

ステンシルバッファを用いた手法では、物体数が増えた場合には 1 フレームを生成するために複数回のレンダリングを行う必要があり、3 者以上ともなればレンダリング回数の爆発を招くことになります。このことを考えると実用的とも汎用的とも言い難い手法ではあります。また、実行時間を無視するとしても、単一のバッファにおいてレンダリングさせるためにはアルゴリズム的に複雑になることは回避できません。実のところそれが可能かどうかは検証していないのでなんともいえないところですが、僕が実装しようとしたときには三者間の演算の時点で単一のバッファで汎用にレンダリングすることはあきらめました。どうなんでしょうかね?一時的にステンシルバッファと Z バッファの情報をメモリ上へ退避することが許されるなら実装は可能ですが、こちらは実行速度が死ぬほど低速でした(実装法がまずかった可能性はかなり高いです)。

そのほかに、体積素同士の集合演算を行う場合に、体積素に制限が加わります。一般的な表現では「凸立体に限定する」となりますが、これは至って当然なことです。フラグが 1 bit しかないなら、そこに含まれる情報は最大でも 1 bit です。言い方を変えれば、ステンシルバッファを用いた方法では、最前面と最後面の間の体積が連続であるということが重要なのです。

複数の体積素に対応した CSG 描画

ステンシルバッファを用いて描画する方法は、比較を避けるために複数回のレンダリング結果をマスクを通して合成しているだけということがわかったと思います。と、いうことは、マスクを通して合成するのではなく、比較をして合成することも可能です。

そのように演算を行うためには、体積素の前面の Z 値と色、背面の Z 値と色をあらかじめ知っておくことが必要です。これらの情報を用いることで、各演算を CPU で処理することができます。 まず、体積素を凸物体に限定し、各演算の実装を考えてみます。

1. 和演算(or)

Z バッファを単純に用いれば何も考えなくともよさそうな気がするのは気のせいです。表示だけが目的であれば難しいことはなにもありませんが、和演算の後に演算を行うことを考えると話は簡単でなく、演算の結果をきちんと分類しておく必要があります。今はピクセルごとの処理を考えているので、深さ方向(ディスプレイに垂直で、ディスプレイ平面との交点を z=0 とし、最大深度を z=1.0 とします)の数直線を考え(ってゆーか、図が数直線になってねぇよ!)、体積素はこの数直線上の領域として扱います。このとき、二つの領域([As Ae]、[Bs Be])に対する和演算は2つに分類できます。

1.a 二つの領域が共通部を持たない場合

二つの領域が共通部を持たない場合
図8.a 二つの領域が共通部を持たない場合

この場合には、演算結果は二つの領域となります。したがって、演算の途中の状態を保持するためには、それぞれのピクセルにおける体積素の占める領域の開始と終了値が複数存在できなければなりません。開始値と終了値(図 8 の場合、C0sとC1e)だけしか保持しないと、C0eとC1sの間で切断した場合に、体積素が存在しないのにも関わらず中身がつまっているようになってしまいます。

1.b 二つの領域が共通部を持たない場合

二つの領域が共通部を持たない場合
図8.b 二つの領域が共通部を持たない場合

この場合は話が簡単です。見ての通り、で済ませてしまいましょう。

2. 差演算(sub)

実装はとりあえず先送りにして分類だけ進めてしまいましょう。次の演算は差です。二つの領域における差演算は4つに分類できます。

2.a 二つの領域が共通部を持たない場合

二つの領域が共通部を持たない場合
図9.a 二つの領域が共通部を持たない場合

説明するまでもないと思いますが、A-Bの場合ですね。

2.b 引く側の領域が引かれる側に含まれる場合

引く側の領域が引かれる側に含まれる場合
図9.b 引く側の領域が引かれる側に含まれる場合

なんとなく、プログラムするときにはやっかいになりそうな気がしませんか?

2.c 引かれる側の領域が引く側に含まれる場合

引かれる側の領域が引く側に含まれる場合
図9.c 引かれる側の領域が引く側に含まれる場合

2.bとは逆の場合で、すべてがパァです。

2.d 領域の片側の境界だけ削除する場合

領域の片側の境界だけ削除する場合
図9.d 領域の片側の境界だけ削除する場合

図9.d では領域Bが後方に位置していますが、どちらが前方でも同じように処理できます。

3. 積演算(and)

だんだん形になってきた感じです。積演算は、二つの共通部を取り出す演算で、これは2つに分類できます。

3.a 二つの領域が共通部を持たない場合

二つの領域が共通部を持たない場合
図10.a 二つの領域が共通部を持たない場合

ま、当然ですが答えはゼロ集合です。

3.b 二つの領域が共通部を持つ場合

二つの領域が共通部を持つ場合
図10.b 二つの領域が共通部を持つ場合

共通部の計算をすればいいってことですね。

実装

ようやく実装に入れます。各ピクセルに対して体積素の開始 Z 値と終了 Z 値、およびそれぞれの点における色が必要になりますが、体積素の数がいくつになるかは不明です。まじめに実装するのであれば、各ピクセルに対してリストをもたせ、セルに Z 値と色をもたせることになりますが、それをまじめに走査したらと考えると夜も眠れません。安眠するためにも楽することが必要なので、体積素の最大数は決め打ちでいくことにします。間違われると困るのですが、ここでの体積素の最大数とは、あるピクセルに対して Z 軸上に存在する体積素の数のことであり、CSG の演算の対象となる体積素の数ではありません(わかりにくいけど図は省略)。

そんなこんなで体積素の最大数を決めると何がうれしいかというと、配列で済ませることができる点です。何を配列にするかはこれから考えます。

素直に考えれば、
 
 
 struct {
    GLuint rgb; 
    GLfloat z; 
 };
のように Z 値と色を構造体でまとめて、それを配列にするのがわかりやすいのですが、Z 値および色を OpenGL の glReadPixel でとってくることを考えると、入力としてはスクリーンに対する Z 値の二次元配列と RGB の二次元配列を別々に渡されそうです。というわけで、いちいち変換するのは避けて、そのままの状態で演算することにしました。レイヤーっぽいイメージです。

実行結果

本当ならここでそのプログラムの詳細を説明すべきなのかもしれませんが、そろそろ気力も興味も尽きてきましたので、だらだらと文章を書くのはやめることにします。結局のところ、今回のキモはなんだったかというと、三つ以上の体積素に対しての演算をしても Athlon 1GHz ぐらいあれば(笑)ぐりぐり動くのです(図11)。そのほかに何があるかってーと・・・なんもねぇ〜


(a) A or B or C

(b) A and B and C

(c) A and B sub C

(d) A sub B sub C

(e) A or B and C

(f) A sub B and C
図11 三つの体積素間の演算例

まとめ

オブジェクト数が増えると低速なのは相変わらずなので、実用するには程遠い気がしなくもありませんが、お手軽に演算結果を描画するにはお手ごろ価格(っつーか、タダだけど)なんではないでしょうか。ちなみに、サンプルプログラムでは限られたプリミティブしか扱っていませんが、任意のモデルに対しての演算が可能です。プログラムさえ組めば、Gガンダムのようにガンダムの顔モデルの顔だけくり貫いて、人間の顔モデルの顔部分を抽出したモデルをはめ込むことでアレが実現できます。やりたかったんですが、時間的な余裕がありません。う〜ん、残念。プログラムはこちら37-cc-csg100.lzh (258065 bytes)。

そうそう、大事なことを言うのを忘れてました。ボーリングシューズの共有は、一つしかないステンシルバッファを使うのと同様で、一つを使いまわすのに多大な労力を費やすことになるわけで、結果、非常に低速になります。実際、彼らが 1 ゲーム終えるまでにこちらは 2 ゲーム終わってました。ですから、時間に追われる現代の若者はシューズを1人1足ずつ借りるべきです。え?僕?僕は1日2足借りてしまいます。

でわ。

参考文献

  1. 新坂さん:カクカクシカジカ
    プログラミング → Technical Documents → ステンシルバッファによるリアルタイムCSG
    綺麗な実行結果と共に丁寧に解説されています。問題点にも触れており、ステンシルバッファを使った方法は、これ以上に説明することがないような気が。

  2. かげさん:ギリギリ工房
    Delphi + OpenGL → ステンシルバッファを利用したCSG & 手続きポインタ
    SIGGRAPH 97 のプログラムを Delphi で実行しています。

  3. Wiegand, T.F.:Interactive Rendering of CSG Models
    Computer Graphics Forum, vol. 15, no. 4, pp. 249-261, 1996.
    ちょっと見つけなおせなかったのですが、確かこちらがもともとの論文だったはずです。こちらに内容紹介があります(英文)。

  4. Ari Rappoport, Steven Spitz:Interactive Boolean Operations for Conceptual Design of 3D Solids
    SIGGRAPH 97 Conference Proceedings, pp269-278.
    csgで検索かけるとこちらを紹介しているサイトが多いようです。

  5. Demonstration of performing arbitrary CSG operations.
    http://www.sgi.com/software/opengl/advanced97/programs/programs.html
    僕が読んだプログラムはこちらからダウンロードしたはずで、ほかにこれの 96 年度版があったはずなのですが・・・。96 年度版のプログラムはちょっとだけ手直しされて GLUT のアーカイブに含まれてます。

  6. SGI
    http://www.sgi.com/software/opengl/advanced96/node33.html
    http://www.sgi.com/software/opengl/advanced97/notes/node11.html
    http://www.sgi.com/software/opengl/advanced98/notes/node19.html
    毎年更新してるんですかね?

Virtual Payment System100えん10えん1えんヘルプ

第38回多面性による二つのレベル
はじめに

みなさん、ドリドリ〜。ドリドリと言えば・・・そうです、先日までGPXを探していたのでした。GPXと言っても、ただのGPXではありません。真のGPXです。いやいや厳密にはGPXの真でした。あぁ、漢字表記ではありませんな。英文字です。まどろっこしいので正式名称でいきましょう。新世紀サイバーフォーミュラSIN Vol.3 です。DVD の。

もちろん、サイバーフォーミュラは僕の精神構造の原点ですから(やな原点だな)、LD でそろっているんです。そう思って油断していました。あぁ、なんということでしょうか。VAP は僕になんの断りもなくいつのまにやら DVD 化してやがったのです!(そりゃ断らないだろうさ・・・)ヴァップめ、DVD 化なんかできないと甘く見ていりゃいい気になりやがって。そして、あろうことか、初回限定クリアケースパッケージで販売です。さらに、DVD 版では5分間の新作映像付きです。これはもう買うしかありません(笑)

SIN シリーズが発売されていることを僕が知ったのは 5/22 、DVD 化第二弾サイバーフォーミュラ11(ダブルワン)の発売日でした。そして、SIN Vol.1 が発売されたのは 2000 年 11 月です。うひゃぁ、はんとしたってるよ!

こうして僕の秋葉原めぐりの日々が始まったのです。

という振りはともかく、11 を買いに行った日に石丸電器の各店舗をのぞいたところ、店頭在庫で SIN Vol.1/2 の初回版はゲットできてしまいました。いちおう、ここで要望を出しておきましょう。石丸さ〜ん、店頭在庫も在庫管理に含めてくださ〜い。

不思議なことに、最も新しいはずの SIN Vol.3 だけが見つからなかったのでした。忙しい状況に陥っているため、探す時間はとれないことが予想されたため、結局、5分間の新作映像が気になって SIN Vol.3 の通常版を購入してしまったのです。初回版があったら買いなおすつもりで。人はそれを大人買いと言う・・・

で、まぁ、それがいつだったかのD5.のトップに書いてあった状態だったわけです。そんなこんなでヤフオクをチェックしていると、未開封品 SIN Vol.3 が出品されているではありませんか!あからさまに転売目的です(笑)。いや、それはいいんですよ。それだけの価値を見出して買うわけですし、それで初回限定版の新品がゲットできるんですから。

そう自分をだましつつヤフオクに登録し、入札は寸前にしよ〜と思いつつ帰路についたところ、たまたまよったソフマップに初回限定版が中古で出ていたのでこれを購入して一件落着してしまいました。5000円くらい得しました(笑)

こんな感じで、すでにそろっているものの一部を差し替えることによって、違うバージョンを用意することはそれなりに有用です。例えば、初回限定版セットとそうでないセットを用意したほうが売るときに便利なわけですが、両方を最初からそろえるのは現実的に不可能です。Z ガンダムの LD-BOX を購入しようとして、初回版はプレミアがついていて買えないから前半は通常版にしたら、後半は初回分がだぶついている、そんな感じの状態です。こういうときは、とりあえず初回版と通常版のセットにしておき、機会を見て初回版にそろえるのが常套手段なのです(そうか?

複数のレベルの共存

ぎゃるぱにXで、最も多い要望は「EASY レベル作れ」でしょう。リクエストする方は簡単にできると思われているのかもしれませんが、実際の手間は新しい面を作るのと同じくらいかかります。そこで、今回はいかに低コストで複数のレベルを実装するかを考えてみたいと思います。前提として、すでに NORMAL レベルは実装済みとします。だって、作ってあるもん。

諸般の事情と申しましょうか、弾幕および弾のプログラム内で使用している各パラメータはすべて define してあります。ということで、こいつの define 内容を変更することで対処できんかねぇ〜という方針で行きたいと思います。

define した定義は次のような使われ方をしています。
#define BULLIT_SPEED 100

...
mx += BULLIT_SPEED * Cos(dir)
my += BULLIT_SPEED * Sin(dir)
...

複数のレベルの基本的な実装法

一般的な EASY レベルの実装がどうなっているかは知りませんが、多分、一番正攻法となるのは、それぞれのパラメータは対応する変数を参照するようにしておき、難易度に応じた値をその変数に代入する方法でしょう(もうちょっとわかりやすく書く努力をしようよ・・・)。これをプログラムの変更無しに実装するためには、次のように書くことで実現できます。
enum { EASY_LEVEL =0, NORMAL_LEVEL };
enum { PARAM_1, PARAM_2, NUM_OF_PARAM };

int gameLevel = EASY_MODE;
int param[NUM_OF_PARAM][2] = {
{ 10, 20 }, // PARAM_1
{ 11, 22 }, // PARAM_2
};

#define BULLIT_SPEED param[gameLevel][PARAM_1]
この方法の問題点は、変数定義の数が三箇所に分かれてしまうことで、たとえば難易度に依存する変数を一つ増やす場合には、2行目の enum に一つパラメータ名を追加し、param 配列に値を二つ追加し、最後に define を変更することになります。僕は人間のすることに間違いが必ずあると思っており、この方法では必ず別のパラメータを参照するバグが発生するに違いないと確信しております。

多少ましな実装法

それでは人為的なミスが入り込みにくい方法を考えてみます。要するに、変更箇所が 1 箇所で、その変更の有無に関わらず動作するようになっていればいいってことです。ということで、
#define BULLIT_SPEED ((gameLevel == EASY_LEVEL) ? 10 : 20)
となります。ただ、これだと gameLevel が三つ以上になったとき、かなり見苦しいコードが展開されることになります。いちおう、マクロでごまかすことはできて、
#define MODE_3(a, b, c) ((gameLevel == EASY_LEVEL) ? a : ((gameLevel == NORMAL_LEVEL) ? b : c))

#define BULLIT_SPEED MODE_3(10, 20, 30)
とすることはできますが、あまりに分岐が多いのは考え物なので、どうにかしたい気もします。

もし、変数の値が1バイトで済むのであれば、あのいんちきくさいCの構文を使うことで、困ったことにすっきりとかけてしまったりします。いんちきくさいというのは、配列のアクセスで、
b=a[10];
b=10[a];
のどちらでもOKというヤツです。このとき、a[] が char 型の配列であるとすれば、a は char ポインタとなります(厳密には違うけど)。そこで、b="abcdef"[3]; などという破廉恥極まりない記述ができてしまいます。このあたりはCマガで説明されてました。興味のある方はそちらを参照してください。

これを利用すれば、1バイトの値として取り出すことができるわけです。先程のパラメータはすべて1バイトで表現可能な範囲ですから(いや、そう書き換えたんだけどさ)、適用可能です。こう書けます。
#define BULLIT_SPEED "\x00a\x014\x01e"[gameLevel]

これではあまりにもメンテナンス不可能なので、プリプロセッサで処理して上記の文字列を自動生成することを考えます。残念ながらC言語には 10 進値を 16 進表記に変換するプリプロセッサなんてのはありませんので、文字列のコンカチネーション(あってるんだろうな・・・シュミレーションみたいで自信がねぇ〜)を使って生成することを考えます。すなわち、こんな定義を 256 個用意するってことです。
#define BYTE_0 "\x000"
#define BYTE_1 "\x001"
...
#define BYTE_255 "\x0ff"
で、
#define VALUE(n) BYTE_##n
とすることで、n の値に応じた BYTE 表現がゲットできます。となれば、あとはもう一段マクロを用意してあげるのみです。
#define MODE_3(a, b, c) VALUE(a) VALUE(b) VALUE(c) [gameLevel]
このうさんくさいマクロを
#define BULLIT_SPEED MODE_3(10, 20, 30)
と使用することで、さらにうさんくさいコード
#define BULLIT_SPEED "\x00a\x014\x01e"[gameLevel]
が得られます。

実際問題として、char 型限定では使えないにもほどがあるわけで、せめて int 型に適用したいところです。ここで不愉快になるのですが、いつもいつも文字列、つまり char 配列は特別扱いされております。まったくもって不愉快です。もし、int 型でも同様の扱いがなされていれば、UNICODE も怖くなかったのです。しかし、いくら文字列の扱いが特別といっても、メモリ内での表現は int 型だろうが、char 型だろうが、単なる BYTE 配列と同等です。ということは、int 型での表現と同じ表現を文字列表現してあげれば、char 配列だけが特別ではなくなります。

さっそく、キャストを駆使して実現してみましょう。基本形は次のようになります。
int c = *((int*)(&"\x064\x000\x000\x000\x000\x001\x000\x000"[gameLevel *4]));
これで、gameLevel == 0 のときに 100、==1 のときに 256 が c に代入されます。

これを先程のインティキマクロを使用する形に変更すると、
#define TWO_MODE(n, m) \
VALUE(n & 0xff) VALUE((n >> 8) & 0xff) \
VALUE((n >> 16) & 0xff) VALUE((n >> 24) & 0xff) \
VALUE(m & 0xff) VALUE((m >> 8) & 0xff) \
VALUE((m >> 16) & 0xff) VALUE((m >> 24) & 0xff)
となります。これで、キャストを駆使する場合の文字列
"\x064\x000\x000\x000\x000\x001\x000\x000"
が用意できたことになります。ですから、キャスト部分を付け加えて、
#define TWO_MODE(n, m) \
*((int*)(& VALUE(n & 0xff) VALUE((n >> 8) & 0xff) \
VALUE((n >> 16) & 0xff) VALUE((n >> 24) & 0xff) \
VALUE(m & 0xff) VALUE((m >> 8) & 0xff) \
VALUE((m >> 16) & 0xff) VALUE((m >> 24) & 0xff)[gameLevel *4]))
と変更し、
#define BULLIT_SPEED TWO_MODE( 100, 256 )
と書けば、ゲームレベルに応じて、100 もしくは 256 の値を取るのです。

検証

ここまでが寝惚け頭での思考部分で、ネタ完成〜と思ったのです。試してみると・・・いけてねぇ!全然いけてねぇよ!

C言語のプリプロセッサでは、数値の評価を行わないで素のまま展開するのです。ということで、たとえば、n=0x100としてマクロが呼び出されると、例えば
VALUE((n >> 16) & 0xff)
の引数部は評価されずにそのまま展開されます。したがって、予定では
BYTE_1
と展開されるはず(僕的に。)なところが、
BYTE_(n >> 16) & 0xff)
と展開されてしまうのでした。当然、こんなのは文法的に間違っているわけですからエラーです。そういうわけで、この手法をメンテナンス性を確保したまま int 型に適用することはほぼ不可能っぽいようです。

比較

さて、最初にあげた実用に耐えうる二つのコードについて考察を行います。コードAは、
enum { EASY_LEVEL =0, NORMAL_LEVEL };
enum { PARAM_1, PARAM_2, NUM_OF_PARAM };

int gameLevel = EASY_LEVEL;
int param[NUM_OF_PARAM][2] = {
{ 10, 20 }, // PARAM_1
{ 11, 22 }, // PARAM_2
};

#define BULLIT_SPEED param[gameLevel][PARAM_1]
で、コードBは
#define BULLIT_SPEED ((gameLevel == EASY_LEVEL) ? 10 : 20)
を指すことにします。

二者のコードの決定的な違いは、代入すべき値が記憶されている場所にあります。もちろん、コンパイラによって違ってきますが、一般的にはコードAがデータ部、コードBがコード部に記憶されるはずです。コード部のデータは実行中の命令列内に存在するわけですから、キャッシュミスは(ほぼ)ありえません。その代わり、分岐が含まれることになる(2つの値を選択する場合は必ずしもそうはならない)ため、二者の違いは、とりもなおさずキャッシュミスと分岐予測ミスの速度の比較になります。当然ですが、こんなものは実行時の状態に依存するわけで、どちらが高速であるかを論じることができません。実際、二者について速度比較を行ったところ、全く変化が見られませんでした。

速度で優劣が決定できないとなると、次は可読性で判断することになるわけですが、これはコードBに軍配が上がることは言うまでもありません。ありませんけど、説明すると、define 部の定義
#define BULLIT_SPEED ((gameLevel == EASY_LEVEL) ? 10 : ((gameLevel == NORMAL_LEVEL) ? 20 : 30))
をもっとも読みやすい形にするには一般型として次のマクロ表現を用いることができます。
#define BULLIT_SPEED LEVEL_3(10, 20, 30)
どちらのコードを使ってもこのマクロを使っての記述になるというところまでは同じになります。もちろん、LEVEL_3 マクロの定義の中身はそれぞれの手法に応じています。となると、コードBはうにゃっと一回書けばいいのに対し、コードAは別に配列定義が必要です。したがって、コードBに優勢を与えるわけです。

ただし、別の観点から言えば、この優勢は必ずしも絶対ではないことが簡単にわかります。コードAではちょこちょこっと変更するだけで、パラメータ群をファイルから読み込むように対応できます。ここで、コードAに多少手を加えたコードCが提案できます。 コードCでは、変更が必要なパラメータの値を上書きするだけというシンプルな方法です。速度的にはコードAと同等と考えられますが(配列の要素番号が固定なのでその分のアドバンテージはある)、変更するパラメータをどこから持ってくるか、という問題は先送りになっています。

結論

どちらも一長一短なので結論とか言ったところで、ぎゃるぱにXではこっちを使うよ〜程度で心苦しい限りです。で、どちらを使うのかというと、コードBです。理由は簡単、コードAにしたところで、僕以外の誰かが調整するとは思えないからです(笑)。いや、すでにそうではないんですが、まぁ、少なくとも Visual C++ でビルドできる人以外(っつーか、僕の周りには VC でのビルドができない人はいないですが)が触ることはありませんのでねぇ。

とはいえ、任意のパラメータをファイルから読み出したデータで指定することに魅力があるのも事実で、その魅力に取り込まれた方々から批判を受けるのは必至です。その矛先を受け流すべくもうひと頑張りです。ファイルからデータを読み出す場合には、どのパラメータにどんな値を代入するかが問題で、さて、どう指定しましょう、と。どのパラメータ、というのは番号指定が一番簡単ですが、プログラムできない人にそのような方法での指定を求めるのは無理無茶無謀です。define と同じ名前で、というのが順当でしょう。ということは、指定ファイルは次のような記述になるはずです。
PARAM_1=100
PARAM_2=200
...
したがって、プログラム的には、PARAM_1 という文字列からパラメータ配列の要素番号への対応を取ることが要求されます。これを解決するために、PARAM_1 を enum 値に使い、プリプロセッサの文字列化機能(@Visual C++)を併用することで以下の記述が可能です。
enum { PARAM_1, PARAM_2, ..., NUM_OF_PARAM };

struct {int id, char *name }
conv[] = {
{ PARAM_1, ##PARAM_1 },
{ PARAM_2, ##PARAM_2 },
...
};

#define PARAM_1 param[PARAM_1]

int param[NUM_OF_PARAM];
なにがなんだかわかりません(笑)

まぁ、多少プログラムがわかる人なら、そこかしこにある PARAM_x がそれぞれ何を意味しているかがわかると思います。もし、分かったら、あなたは違いの分かる人、ダバダ〜

さて、違いがわかると言えば、初回限定版と通常版の違いもそんなもので、マニアには大違いですが、そうでない人にとってみれば別に大差ないのです。違いがわかるほうがいいのかというと、実はそんなこともなくて、知らなきゃいいこともあります。たとえば、LD で出ているアニメが DVD で出しなおされたのを見ているときに、微妙に違っていた場合、瞬間的に「あ、違う」と気がついてしまうのは非常にやな気分です。サイバーフォーミュラ11 Vol.3 を見ていて、「あ、テロップがない」と気が付き、英語が間違っていたんかな〜と思い、LD 版を見直したら・・・(笑)。今まで気がつかなかったよ!

せっかくサイバーフォーミュラのネタを引っ張り出してきたので、ついでに。DVD 版サイバーフォーミュラ SIN Vol.3 通常版(笑)を1名様にプレゼント!こら、そこ!不用品の処分とか言わない!希望者は sanami@aya.or.jp までタイトルを「GPX SIN開発希望」としてメールをください。厳正なる抽選を行いたいです(だって、2人以上いないと抽選できないし。)。〆切は 2001 年 8 月 3 日付け有効ということで。

そうそう、上のコードを使用するときは、ファイルから読み出した文字列を、conv 配列の文字列と順番に比較し、マッチしたときの id をインデクスに param 配列へ書き込みます。完璧ダ!

いやはやなんというか、バカっぽいですな。さらにマクロでラッピングすると、今度はアホっぽくなるような気がします。でわ。

Virtual Payment System100えん10えん1えんヘルプ

第39回テーブル枠の作り方
はじめに

みなさん、シトシト〜。東京近郊では久しぶりに雨でした(だいぶ以前のことです)。多少は涼しくなるかと思いきや、湿度が上がってベトベトになってしまい、困ったものです。その日はたまたま雨の予報が出ていることを聞いたので、日が照っているのにも関わらず 65cm 傘を仕事場に持っていったところ、仕事が終わったころには、おぉ、雨が降っている〜。

こんなときにはささやかな優越感に浸ることができます。「おまえら、天気予報見てねぇのかよ」と(笑)。そんな風に自分は安全なところからかわいそうな方々を眺めたりするのは心のリフレッシュになります(おおげさな・・・)。他には、自分は部屋から出ない状態で、外のどしゃ降りや大雪を見ているのも楽しいものです。ちなみに、大雪のときはその後、車がツルツルで楽しかったです。

そうそう、出かける間際には稲妻も光っていて、都心方面には落雷の様子が眺めることもできました。その窓枠越しに見る稲光は、それはそれは見てて飽きないものです。

テーブルによる枠のコーディング

ところで、ここのところ、あるサイトの HTML の面倒を見ています。厳密には表現が間違いなのですが、問題のある HTML がよく僕のところに回ってくるのです。「さ〜くん、これ、レイアウトが崩れるんだけど」、と。そんななので僕の気分としては「面倒を見ている」なのです。それはともかく、そこでは HTML でページを書くことをコーディングと呼んでいます。無目的コンピュータ用語辞典http://www.nurs.or.jp/~kneo/dic.htmlによれば(え?そういうものを参照するなって?)
コーディング (coding)
1.コーダーに成り下がって、 プログラムのコードを 手で書くこと。
コード (code、cord)
1. code: プログラムの ソースファイルのうち、実行ファイルに変換される部分のこと。
ということのようですから、使い方が間違っています。HTML なのですから、マーキングとかマーキングアップとか言うのが正しいのではないでしょうか(また適当なことを・・・)。いやまぁ、業界用語と言ってしまえばそれでいいという気はかなりするんですけどね。

そゆことで今回は HTML における( CSS なしでの)テーブルのコーディングについてつらつらと考えてみたいと思います。たまにはこういうネタもいいでしょ?あ、Mozilla のソースコードを読んだりはしないので注意が必要だ。

非準拠によるコーディング

さて、HTML のバージョンは知らないうちにこっそりと上がっていたりして、さらにその解釈は完全上位互換なわけでもなく、ということで、実際のところ自分で書いている HTML が W3C のどのバージョンに相当するのかもさっぱりわからないのであります。とりあえず、手元においていつも参照している本は HTML 3.2 なのですが、僕の書き方は HTML 3.2 に準拠していないというのはいくつかの点で明らかです。

意図的に HTML に準拠しない場所が実はあったりしまして、それはどこかというと、コードを示す部分です。コードを示す場合には、コード全体をテーブルで囲み、セルの背景色を変えることでコード部を強調しているわけですが、困ったことに PRE タグがそれはそれは使えねぇ〜なのです。何が使えないって、なんで閉じたときに改行一個つけるですか!下の例では見やすいように改行を入れていますが、改行をなくしても同じ結果が得られます。
<TABLE BORDER=0><TD BGCOLOR="#000000"><FONT COLOR="#FFFFFF">
<PRE>
HTMLにおける美麗コーディング
</PRE>
</FONT></TD></TABLE>

図1. セルと PRE タグの関係(左ネスケ4.7、右IE5)

ところが、面白いことにネスケと IE の両方でセルを閉じると勝手に PRE も終了してくれるという挙動をしめしてくれるのです。そして、そのときには余計な改行がつかなかったりします。というわけで、セルの中で PRE を開始して閉じないという破廉恥極まりない書き方をしていたのです。それでちゃんと見えるからい〜や、と。
<TABLE BORDER=0><TD BGCOLOR="#000000"><FONT COLOR="#FFFFFF">
<PRE>
HTMLにおける美麗コーディング
</FONT></TD></TABLE>

図2. PRE タグを閉じない場合(左ネスケ4.7、右IE5)

先日、BeOS をつっこんでデュアルブートにして起動して自分のページを見ると・・・わはは。一行が長ぇ! おそらく PRE タグを閉じていないのが原因で改行してくれなくなってしまうのでしょう。そんななので、どうにかすべく試行錯誤を開始したのでした。

さて、PRE で開始した次の行を空行にすることで一応のバランスはとれますが、今度は左右方向の空白が少なくなってしまいます。そんな日々とお別れすべくいろいろ研究してみましたが、CODE タグが意外にも有効に使えそうです。ただし、表示文字は固定幅になるのですが、タブはすべて無視されてしまうし、BR も必要ですが、改行が余計につかないこと、ただそれだけに価値があります(笑)。タブがないのは見にくいので結局、泣きながらイメージでスペースを空けることにしました(負け)。

おかげで、< > をいちいち &lt; &gt; と置換せねばならんし、タブは一々画像を読み込まねばならんし、毎行 <BR> を書かねばならんしとめんどくさくなりましたが(PRE の中でもそうすべきなのですね・・・)。実際の HTML での記述がどのようになるかはこのページのソースを見てください、と流しておきます。だって、見にくいんだもん。

テーブルによる枠

テーブルを使って枠を描くというのは誰しもが考えることで、まぁたいていの人がやってるんではないでしょうか。僕のページでも MEMORIAL のページで使っています。実はこの枠、厳密に作ろうとすると結構やっかいだったりします。なにが困るって、両側のセルの幅を指定してもそのとおりに組んでくれないんです。IE5 は問題ありませんが、ネスケや某ブラウザ(秘密情報なんかなー?)ではいけません。こんなんになります。
<TABLE BORDER=1 CELLPADDING=0 CELLSPACING=0 WIDTH=400>
<TD WIDTH=10 BGCOLOR="#0000FF"><IMG SRC="img/trans.gif" width=1 height=1></TD>
<TD BGCOLOR="#FF0000" ALIGN="center">超美麗コーディング</TD>
<TD WIDTH=10 BGCOLOR="#0000FF"><IMG SRC="img/trans.gif" width=1 height=1></TD>
</TABLE>



図3. セルの分割例(上ネスケ4.7、下IE5)

こんなですから、たとえば、2ドットの枠を描くときに 3x3 にセル分割とかすると結構きっついです。
<TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=400>
<TD WIDTH=2 HEIGHT=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD>
<TD HEIGHT=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD>
<TD WIDTH=2 HEIGHT=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD><TR>

<TD WIDTH=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD>
<TD BGCOLOR="#FFFFFF" ALIGN="center">超美麗コーディング</TD>
<TD WIDTH=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD><TR>

<TD WIDTH=2 HEIGHT=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD>
<TD HEIGHT=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD>
<TD WIDTH=2 HEIGHT=2 BGCOLOR="#FF0000"><IMG SRC="img/trans.gif" width=2 height=2></TD><TR>
</TABLE>



図4. 3x3 分割による枠の描画(上ネスケ4.7、下IE5)

この場合の正解は、二重テーブルです。
<TABLE BORDER=0 CELLPADDING=2 CELLSPACING=0 WIDTH=400><TD BGCOLOR="#FF0000">
<TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=100%><TD BGCOLOR="#FFFFFF" ALIGN="center">
超美麗コーディング
</TD></TABLE>
</TD></TABLE>



図5. 二重テーブルによる枠の描画(上ネスケ4.7、下IE5)

高度なテーブル枠

さて、そんなこんなで苦労して枠が作れるのですが、先日、ちょっと違うバージョンの枠に問題が発生しました(図6)。赤い領域にテキストを流し込みたいわけですな。


図6. テーブル組みのお題その2

これのどこが問題かというと、それは問題に直面した人しか知らない、知る人ぞ知る問題があるのです。簡単に言えば、3x3 のセル分割できないのが一番の原因です。テーブル組みの方法としては、横と横、どちらを先に組むかという話がありますが、根本的な問題は変わらないので、ここでは先に縦組することにしましょう。予定としては、次の図のようになるはずです。


図7. テーブル組みの予定図

あ、そうそう、TD〜/TDの間に余計な改行が入ると余計なスペースが発生するので、気をつけてください。で、これを実際にコーディングするわけですが、上下の部分は問題の本質には関わってこないので、中段の部分についてだけ論じることにしましょう。予定通りにテーブルを組んだソースを示します。見易いように適度に改行が入っているので要注意。
<table border=0 cellpadding=0 cellspacing=0 width=200>
<td width=32 height=100%>
<table border=0 cellpadding=0 cellspacing=0 width=32 height=100%>
<td height=16><img src="left-upper.png" width=32 height=16></td><tr>
<td height=100%><img src="left-middle.png" width=32 height=100%></td><tr>
<td height=16><img src="left-bottom.png" width=32 height=16></td>
</table>
</td>
<td>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
</td>
<td width=32 height=100%>
<table border=0 cellpadding=0 cellspacing=0 width=32 height=100%>
<td height=16><img src="right-upper.png" width=32 height=16></td><tr>
<td height=100% width=32><img src="right-middle.png" width=32 height=100%></td><tr>
<td height=16><img src="right-bottom.png" width=32 height=16></td>
</table>
</td>
</table>
で、こいつの表示がどうなるかというと、図8のようになります。

図8. 実行例(左ネスケ4.7、右IE5)

IE5 では意図したとおりにテーブル組みしてくれるかと思いきや、テーブルの border を有効にすると図9のように崩れます。なんでやねん!


図9. border をつけた実行結果(IE5)

いくつかのパターンでテーブル組みの結果を試してみるとわかりますが、横方向のテーブル組みのほうが縦方向より幾分ましになっているようです。まぁ、横方向のサイズは縦方向のサイズよりも決定しやすいからと思われますが。とはいえ、横方向に限っても満足できるレベルではありません。けれどもこれは別の物語、いつかまた、別のときにはなすことにしよう。

結論

興味のある人は自分で試行錯誤を繰り返すとテーブル組みのくせがわかると思います。今回の場合の正解は「二分割する」が正解です。テキストを流し込むセルは ROWSPAN で縦二つのセルを結合します。コードはこんなんに。
<TABLE BORDER=0 CELLPADDING=0 CELLSPACING=0 WIDTH=200>
<TD WIDTH=32 BACKGROUND="left-middle.png" VALIGN="top">
<IMG SRC="left-upper.png" WIDTH=32 HEIGHT=16>
</TD>
<TD ROWSPAN=2 BACKGROUND="" WIDTH=100%>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
超美麗コーディング<BR>
</TD>
<TD WIDTH=32 BACKGROUND="right-middle.png" VALIGN="top">
<IMG SRC="right-upper.png" WIDTH=32 HEIGHT=16>
</TD>
<TR>
<TD WIDTH=32 BACKGROUND="left-middle.png" VALIGN="bottom">
<IMG SRC="left-bottom.png" WIDTH=32 HEIGHT=16>
</TD>
<TD WIDTH=32 BACKGROUND="right-middle.png" VALIGN="bottom">
<IMG SRC="right-bottom.png" WIDTH=32 HEIGHT=16>
</TD>
</TABLE>

図10. 正しいテーブル組み

まとめ

結果を見てみると無駄に分割するよりもすっきりとかっちょえぇ〜テーブル組みになったわけで、僕もご満悦。もともとのコードを書いた人に対して優越感に浸っていると・・・いや〜ん、停電です。先ほどの雷がどこぞに落ちたようです。窓の外の世界は別世界ではなく、ちゃんとつながっているのでした。ささやかな優越感にも浸れないとは世は無情なものですなぁ。

さて、前回告知したプレゼント当選者の発表です。

・・・

応募者がいねぇ!

無情すぎ。でわ。

Virtual Payment System100えん10えん1えんヘルプ

第40回弾幕の作り方−序章編−
はじめに

みなさん、シオシオ〜。前回の話題に関して匿名感想があったのですが、えらく否定的で凹まされたのでした。発言自体の書き方にくせはなく、匿名性に問題ないので公開したいところですが、その感想の主張点を簡単に言うと、

の 2 点です。おそらく、こんなことをのたまわれる方はご自分でサイトを運営していないか、IE ユーザかのどちらかではないかと偏見混じりに分析するのでした。そんなことはともかく、ブラウザ依存の結果をチェックするのが古いというのは、同じ古いでも traditional 、伝統的な古さと言って欲しいところです。仮に、すべてのブラウザが HTML 4.0 に準拠したとしても表示結果を確認してちゃんと表示されないなら表示されるように書き直すということは絶対なくならない、そう僕は思います。

などと言葉で言いくるめようとしても無駄なことは百も承知なので、見てびっくりのあるサイトの表示結果を示すことにします。そのサイトは http://www.lycos.com/ です。それなりに知名度は高いと思いますが、検索サイトです。

なんで英語サイトかというと、まぁ、割と英語サイトの検索をかけることもある、ということだけ言っておくことにします。googleでもひっかからないものもありますし。

そんなことはどうでもいいのです。ある日、検索しようとしてページを見て、アレ?と思ってチェックしたら、うは、いけてねぇ〜。そんないけてない表示結果を図に示します。

Windows2000 + IE5.0による表示
図1:Windows 2000 + IE5.0による表示(画面写真40-ie-lycos-full.png (29040 bytes))

NN4.7による表示
図2:NN4.7による表示(画面写真40-nn-lycos-full.png (24594 bytes))

そうです、検索キーワードを入力するフォームがおかしくなっているのです。これでは検索キーワードを入力することですら困難です。ということで、ブラウザごとの表示確認が必要なことが伝わったかと思います。無駄に。それにしても、ユーザ数的に言って、圧倒的に多い IE ユーザを切り捨てるとは豪気なことですな。

とかなんとか適当なことを言ってしまうとアレかと思い、確認してみたところ環境によって不具合が出る、ということのようです。同じ Win2000+IE5.0 でも不具合が出るかどうかは不定です。フォントが足りないのか?ちなみに、原因となるのは charset に windows-1252 を指定しているからで、このフォント、過去にも指定すると無限リロードを引き起こしたりと印象悪いですな。

伝統的な弾幕作成

で、匿名くんに言われっぱなしなのも腹立たしいので、嫌がらせを兼ねて古いことでないことを話題にするのでした。

などという、本気と取られかねない冗談は置いといて、アクセス解析の結果を眺めていると、わはは。なんと、「弾幕の作り方」で検索している人がいるではありませんか。実は、弾幕の作り方に関して文章は書いてみたものの、まったく面白みに欠けていたのでアップしていなかったのです。伝統的な、ということであれば別段新しい提案がなくてもお茶が濁せそうです。ということで、ファイルを引っ張り出してきたのでした。ちなみに、 Google (google) で「弾幕の作り方」で検索をかけるとコーダ部屋だけしかひっかかりません。ムフー。(画面写真 40-google.png (15101 bytes))

それでは、弾などのオブジェクトの管理は第 34 回のプログラムを参照してもらうとして、ぎゃるぱにXにおける弾幕をどのように作ることができるか、少しだけ紹介しましょう。

最初に

わかりにくいという批判があることを承知であえて固定小数点で実装します。まぁ、半分趣味なので大目に見てください。初めて見る人が混乱しないように固定小数点での値は Fint 型としておきます。実際には

typedef int Fint;


と、名前を付け直しているだけなので int 型と変わりませんが、少なくともどの変数が固定小数点で表現されているかぐらいはわかると思います。心の中では Fint 型は、整数部 16 ビット+小数部 16 ビットであると思い込みます。

で、xy 座標に関しては固定小数点で表現していますが、角度に関しては int 型になっています。あまり深い意味はありませんが、角度は1周を 4096 分割しており、ぎゃるぱにXに関してはそれで十分なので小数点以下は切り捨てってことです。そんなんなので、sin/cos 関数のプロトタイプは

Fint Sin(int theta);
Fint Cos(int theta);


となります。

他に最低限必要な関数としては、rnd と arctan があります。rnd は何かのために線形合同法を利用した実装を用いておきます。それにしても、何かって、何なんでしょう?

arctan は、敵から自機の方向を得るような場合に必須です。math.h には atan と atan2 がありますが、ほとんどすべての入力に対して正しい値を得られる atan2 を使います。atan2 は戻り値の単位が Radian なので、これを 4096 分割の角度に直さねばなりません。Radian は1周を 2πと定めていますから、atan2 の戻り値を input とすると対応する出力 output は比例式

input:output = 2π:4096


の関係にあります。これを解けば

int ArcTan(Fint x, Fint y)
{
float at = atan2(((float)y)/65536, ((float)x)/65536);
return (int)(at * 4096 / (2* PI));
}


と書けますが、実は x と y を 65536 で割る必要はなく、

int ArcTan(Fint x, Fint y)
{
float at = atan2((float)y, (float)x);
return (int)(at * 2048 / PI);
}


です。拡大縮小では角度は保存されるのです。それはともかく、atan2 の引数は y-x の順なのがイヤ〜ンですなぁ。

あと、角度は 4096 になると 0 と等しくなりますが、4096 のままにしておくとときおり鬱陶しいことになりかねません。このために、角度を正規化するマクロを用意しておきましょう。

そうそう、重要なことを忘れてました。座標系をどのように定義するかです。これは基本的なことですが、忘れると後で困ったことになります。出たとこで調整することもできますが、いざ問題になったときには手遅れになりかねません(笑)。ということで、Windows の座標系との兼ね合いを考えて、左上原点、角度は時計回りとしましょう。

#define Normalize(theta) (theta & 4095)


試してみれば分かりますが、引数の theta は負の角度でも正しい値が帰ってきます。

最後に int と Fint の変換マクロを定義しておきます。これを定義しないといちいちベタに書くことになって可読性・保守性が著しく低下します。定義の中身は難しいものではなく、単に 16 ビットシフトを行うだけです。

#define FintTo(n) ((n) << 16)
#define FintTrunc(n)((n) >> 16)


ビットシフト演算子はみょ〜に優先順位が低いので括弧をいやってほどつけて評価順序を確定させておくことを忘れないように気をつけましょう。マクロ定義することで括弧の対応が少し見やすくなるという利点もあるかもしれません。

オブジェクトの定義法

もちろん、C++ のクラスを使っても問題ありませんが、そんなことは全くもってどうでもいいことです。とりあえず、WonderWitch にも転用できるように C で書いてみました。


/==============================================

/ オブジェクト構造体
typedef struct tagSObject {
struct tagSObject *next;// リストのリンク用
bool (*early)(struct tagSObject *);
void (*later)(struct tagSObject *);
void (*destructor)(struct tagSObject *);
DWORD mem[12];// メンバ数12まで。
}SObject;



/==============================================
/ 弾その1 typedef union { SObject object; struct { void *func[4]; // 関数ポインタ領域 int x, y; // 座標 int vx, vy; // 速度成分 }; } SBullit1;

・・・・が、union-struct の書き方が MS-C の機能を使っているので駄目だ〜(笑)。普通に(ANSI-Cに準拠、なのかどうかは知りません) union を使うと、その中の struct にアクセスするのが面倒〜なので、ここは単なるキャストにしてしまいましょう。要は、関数ポインタ領域が先頭に確保できていればいいので、


/==============================================

/ オブジェクト構造体
typedef struct tagSObject {
struct tagSObject *next;// リストのリンク用
bool (*early)(struct tagSObject *);
void (*later)(struct tagSObject *);
void (*destructor)(struct tagSObject *);
DWORDmem[12];// メンバ数12まで。
}SObject;

#define OBJECT_METHOD\
struct tagSObject *next; \
bool (*early)(struct tagSObject *); \
void (*later)(struct tagSObject *); \
void (*destructor)(struct tagSObject *)


/==============================================

/ 弾その1
struct {
OBJECT_METHOD;
int x, y;// 座標
int vx, vy;// 速度成分
} SBullit1;


これでいーやー。オブジェクト構造体はリスト管理するために必要です。

メモリ領域が足りない場合は、関数を一つにまとめておき、呼び出す際の引数によって機能を分けるということも可能です。その分の処理は必要なので一長一短であります。これも本質的な問題ではありませんね。

ぎゃるぱにXでは、オブジェクト自身が描画を行いますが、その描画を含めて処理の機会が1フレームに2度あり、一回目を early 、二回目を later と呼ぶことにしています。スプライト登録型にしていないのは、その方が無理が利くためです。一部のオブジェクトはスプライト以外のモノを描画することもありますし、スプライトを描画した後に当たり判定を描画することもできます。どちらがいいということではなく、ただ単に、こう実装してますよ、というだけの話ですね。

early での処理でオブジェクトを廃棄することになったら、false を返すことにします。later での廃棄はありません。廃棄の理由としては、ボムで弾が爆発とか、アニメパターンが終了したとか、画面外に出たとか、そんなんです。early 関数は必須です。なぜなら、破棄されないオブジェクトはないのです。これに対し、later 関数および destructor 関数は必要でなければ要りません。描画するタイミングが速く、early で描画してしまうオブジェクトや、画面に何も表示しないオブジェクト(便宜的にコントロールオブジェクトと呼ぶことにします)などは later 関数を必要としません。destructor 関数を必要としないのは、メモリ領域を追加で必要としなかったり、そのオブジェクトが廃棄されても他に影響を及ぼさない場合がそうです。オブジェクトの廃棄は early 関数でのみではなく、ステージが終了したときなど、外部から強制的に廃棄する場合があるので desturctor 関数が必要です。そうでないとメモリリークしてしまいますもんね。このあたりの実装の仕様も考えてみると結構面白いです。

弾の実装法

それでは実際に弾を作ってみます。一番簡単な弾を作ります。パターン(図3)が指定した座標から指定した方向に指定した速度で飛んでいき、画面外に出たら削除します。

弾のパターン
図3:弾のパターン

必要な関数は、

void Bullit1_New(Fint x, Fint y, Fint mv, int th);
bool Bullit1_Early(SObject *ptr);
void Bullit1_Later(SObject *ptr);


の三つです。諸般の事情でメモリを別途確保するような場合は destructor もあったほうが楽かも、です。

new 関数ではセルの確保およびメンバの初期化をします。

void Bullit1_New(Fint x, Fint y, Fint mv, int th)
{
SObject *ptr = newObject( );(1)
if(ptr == NULL)return;// 生成失敗
SBullit1 *my = (SBullit1*)ptr;(2)
my->x = x;
my->y = y;
FintMul(my->vx, Cos(th), mv);(3)
FintMul(my->vy, Sin(th), mv);
my->early = Bullit1_Early;(4)
my->later = Bullit1_Later;
my->destructor = NULL;
}


最初にセルをゲットします(1)。このとき、空きセルがなければ弾の生成は残念ですが失敗です。どうがんばっても作れません(笑)。ゲットできたら、弾の構造体だと思い込みます(2)。思い込めたら、あとはメンバを初期化しましょう。この弾は速度一定なので毎フレームにおける座標値の増分を先に計算してしまいます(3)。FintMul は Fint 型の値(第 2、3 引数)を掛けた結果を第 1 引数に代入するマクロです。

最後に関数テーブルをセットします(4)。必要ない関数には NULL を入れておきます。リストのリンク用メンバ next はオブジェクト管理モジュールでセットするので触れてはいけません。

early 関数では、弾の移動および弾の廃棄を処理します。

bool Bullit1_Early(SObject *ptr)
{
SBullit1 *my = (SBullit1*)ptr;(1)
my->x += my->vx;(2)
my->y += my->vy;
if((my->x < FintTo(-8)) || (my->x > FintTo(648)) ||
(my->y < FintTo(-8)) || (my->y > FintTo(488)))
return false;(3)
return true;(4)
}


最初に弾の構造体だと思い込みましょう(1)。そうしないとメンバがどこにあるか、見えてきません。その次は移動です(2)。各座標値に計算しておいた増分を加えるだけです。おぉ簡単。移動したら唯一の廃棄条件、画面内の判定を行います(3)。パターン全部が画面外に出てから削除しないとおかしなことになるので注意です。廃棄しないなら生きている証拠に true を返します(4)。

later 関数では弾の描画を行います。

RECT bullit1Rect = { 0, 0, 16, 16 };
void Bullit1_Later(SObject *ptr)
{
SBullit1 *my = (SBullit1*)ptr;
charaPlane->Blt(FintTrunc(my->x) -8, FintTrunc(my->y) -8, bullit1Rect);
}


パターンの中心の座標を移動して表示するだけです。

とりあえず、これで弾の表示はできるようになりました。試しにスペースキーを押すと画面中心からランダムな方向に弾が飛ぶようにしてみました。実行するとこんな感じになります(図 4 )。実行ファイルとソースコードはこちら40-b-web1.lzh (82902 bytes)。

ランダム方向に弾を発射
図4:第一段階


自機の追加

ちょっとした弾幕を吐くためには目標方向が必要でしょう。簡単にですが自機をつけてみましょう。いちいちオブジェクトを作る気にならないので SCENE 内部に書いてしまいます。ついでなので、横に移動しつづけると自機が傾くようにしてみました(笑)。で、カーソルキーで移動します。ArcTan 関数を使うと自機の方向が分かりますから、自機に向かって飛ぶようにしてみましょう(図 5 )。実行ファイルとソースコードはこちら40-b-web2.lzh (83754 bytes)。

自機に向かって弾を発射
図5:第二段階

そうそう、突っ込まれる前に予防線をはっておきます。斜め移動で速度が変わるのはそういうふうになっているからです(笑)。シューティングゲームを作る人はそう作らないように工夫してくださいね。僕?ちゃんと工夫してますよ、ぎゃるぱにXで。

敵の追加

弾幕を作るにも、弾幕を吐く敵がいないと話になりません。敵も追加しておきましょう。あああ、キャラパターンが転がってないかなぁ〜。あぁ、ロクなパターンがないよぅ…。

弾幕の作り方

ようやく準備が整ったので弾幕を作ってみることにしましょう。とりあえず、一定時間ごとに扇状に弾を吐かせてみます。扇の中心が自機の方向です。敵のオブジェクトに毎フレーム増加するカウンタを用意し、一定数毎に弾を吐く処理をします。

if(my->count % ENEMY_ATTACK_INTERVAL == 0)
{
int theta = ArcTan(myX - my->x, myY - my->y);
theta -= 64*2;
for(int i = 0 ; i < 5; i ++)
{
Bullit1_New(my->x, my->y, FintTo(1), theta);
theta += 64;
}
}


で、実行すると(図6)。実行ファイルとソースコードはこちら40-b-web3.lzh (84349 bytes)。

扇状に弾を発射
図6:扇タイプの弾幕

幾何的な模様を作るタイプは、扇の中心をカウンタに依存させれば OK です(図5)。初期値をカウンタから決定させてみます。

int theta = Normalize(my->count *8);


で、その実行結果(図7)。実行ファイルとソースコードはこちら40-b-web4.lzh (84298 bytes)。

ちょっと弾幕っぽく。
図7:幾何タイプの弾幕

こんなところで基本的な弾幕は簡単に作成することができます。一般に弾幕と呼ばれるようなものは、弾自体は等速で直進するので、発射のタイミングと、弾の移動速度を変更することで再現できてしまいます。

まとめ

…っと、まぁ、あんまり面白いというネタでもなくハードディスクの肥やしになっていましたが日の目を見ることができたんでもったいないお化けも出てこないでしょう。それぞれのソースをコンパイルするにはいつものごとく、やねさんとこからyaneuraoGameSDKをゲットしてきてください。詳しいコンパイル手順については第34回の最後を参照してください。

さて、件の匿名くんの話を やまp に愚痴ったところ…。
「でも、それをネタに更新するんでしょ」
あぁ、そうだよ、更新するさ!無駄に。

それでわ。

Virtual Payment System100えん10えん1えんヘルプ


バーチャル支払いシステム
暁のコーダ部屋のそれぞれの記事が面白い、有用だと思われた場合、対価として適当と思った金額をクリックします。これによって、あなたはバーチャルにお金を支払ったことになり(つまり、支払ってない)、そのバーチャルお金はバーチャルに僕の口座へ振り込まれるという、誰のふところも痛まない、いいシステムなのです。


sanami@aya.or.jp