1. はじめに
2018年にインベーダーゲーム生誕40周年記念として、FPGAを用いてVerilog HDLでスペースインベーダーをフルハードウェアにより設計しました。本記事はその続きで、初めて高位合成を用いてフルハードウェアでスペースインベーダーを設計したものです。
2020年1月に、Bluespecがbsc (Bluespec SystemVerilog Compiler)をオープンソース化しました。そこで、早速bscをインストールしてみました。bscはBSV(Bluespec SystemVerilog)言語で書かれたデザインを高位合成するコンパイラです。BSV言語の習得は他の言語と同様、いくらマニュアルを読んでも身につかないので、実際に設計するしかないと思い、前回作成したインベーダーゲームの、BSVを用いた再設計にトライしました。
 |
|---|
| 図1 FPGAボード(Avnet Ultra96)+作成したPMODインタフェースボード |
図1はUltra96 FPGAボードと2018年に開発したUltra96toPMODボードです。最新版のUltra96toPMODV10ボードデータの場所等はこの記事で示しています。
1.1 BSVとは
本来ならBSVの解説が始まるところですが、解説できるほど知らないので、他の資料に譲ります。最も詳しいのはBSVリファレンスガイドです。
簡単に言えば、Verilog HDLがIEEE 1364として標準化されているハードウェア設計言語(HDL)であるのに対して、SystemVerilogはそれを拡張したIEEE 1800として標準化されているHDLです。BSVはさらにそれを拡張したHDLとなります。
1.2 bscのインストール
私の使用しているLinuxディストリビューションはFedoraなので、やや苦労しましたが、基本的には、この記事の手順で実施しました。ただ、
$ stack install regex-compat syb old-time split
とする必要があったり、以下のように、各種ライブラリのインストールが必要でした。
# dnf install -y libX11-devel libXft-devel gperf bison flex itk-devel tk-devel itcl-devel tcl-devel g++ iverilog autoconf
1.3 他の実装はショボい
2018年にVerilog RTLで設計した、FPGAによるインベーダですが、開発当初は、こんな(不自由なHDLで設計するなんて)馬鹿なことをするのは自分くらいだろう、世界で初めてではないかと思っていました。ところが、完成してからYoutube等で検索すると、世界で10例くらい見つかりました。
 |
|---|
| 図2 他の実装例 |
しかし、HDLという不自由な言語で実装するのでやむを得ない面があるとはいえ、ほとんどのものがシールド(バリケード)がなかったり、インベーダが撃ってこなかったり、単純なものが多いのです。それだけでなく、40年前に感動した、オリジナルに有ったピクセル毎の衝突判定がありません。それではつまらないので、限りなくオリジナルに近い動作を目指しました。名古屋打ち、レインボー等の裏ワザも使用できます。
 |
|---|
| 図3 ピクセル毎の衝突判定処理 |
2. スペースインベーダーの仕様
上記のようにショボいインベーダーを作らないよう、必要最低限の仕様をまとめます。逆にこれらを実装すれば、インベーダゲームとしては、かなり良い完成度のものができるのではないでしょうか。
- 図形パターンは、これを使用する。ただし移動量(下記参照)に合わせた黒バックを含む大きさを持つ。
- インベーダーは横11匹、縦5匹の55匹、得点は上記wikipediaのとおり。
- オブジェクトの移動速度：1tick=1/60secの間に、インベーダ1匹=左又は右に2ピクセル、自機=左又は右に1ピクセル、敵弾=
下方1ピクセル下方4ピクセル/3tick(ただしインベーダが8匹未満の時は5ピクセル/3tick)(ソースコードの解析を参照し変更)、自弾=上方4ピクセル、UFO=左又は右に0.5ピクセルの速度で動かす。ただし、インベーダの最後の一匹は右に3ピクセル。 - インベーダ隊列は右端(又は左端)のインベーダが右端(又は左端)に到達すると全体に下方へ8ピクセル移動、最下段まで到達すると侵略によりゲームオーバー。
- 敵弾はインベーダの16ピクセル下方から出現する。
- 衝突判定はピクセル毎。自弾は上方縦4ピクセル、敵弾は下方横3ピクセルを判定。
- 爆発マークは弾は8tick、自機は(2パタンを交互に)60tickの間表示する。
- UFOは2048tick後から現れ、1536tick毎に左又は右側にランダムに出現。インベーダが8匹未満では出現しない。得点は自弾発射数により、UFOのスコア法則の表から得点を決定する。
- サウンドデータはここにあります。しかしながら、歩行音等が歪んでいて汚いのと歩行音に対して自弾の発射音や爆発音が大きいため、音量バランスを調整する必要があります。
- 歩行音はA, B, C, Dの4種類あり、順番に出力する。インベーダの数によってサウンドを出す間隔を変える。その表は以下のとおり。
https://fs-micro.com/post/show/id/318
3. 使用機材
基本的には過去記事に書いたとおり、中心はUltra96 FPGAボードだったのですが、これには図1のUltra96toPMODボードが必要となります。今回、新たにArtyボードに移植し、基本的にはArtyボードと各インタフェースボードのみで済むようになりました。ArtyボードはPMODインタフェースを4個持つため、(新規開発の)Ultra96toPMODボードが不要です。その上、FPGAボードの価格もUltra96ボードの半額以下の1万3千円くらいです。
 |
|---|
| 図4 Artyボードと各種インタフェースボード |
4. First step - サウンドFSMの設計
初めてBSVを適用するにあたり、サウンドステートマシンは規模が比較的小さいため、まずそれを設計対象としました。合わせて仕様もグレードアップしようと思います。Verilog版では、サウンドチャネルは1個としたので、サウンド間の優先度判定が必要でした。今回はサウンドチャネルを複数持たせ、サウンドの重ね合わせを行います。従って、物量は増えるものの、サウンドの優先度判定を行わずに単純に加算するだけなので、制御はシンプルになります。
4.1 サウンドチャネルの決定
ゲームに使用されているサウンドは表1に示す10種類です。10種類のうち、同時発声数数＝サウンドチャネル数を決める必要があります。ゲームシナリオでの同時発生条件を考え、自機音、インベーダ音1, 2、UFO音の4チャネルとします。1チャネルは、時間的に重ならない複数のサウンドデータ(例:自機弾発射音、自機爆発音、自機増加音)から構成されます。サウンドデータはWaveフォーマットです。
以下に、サウンドの説明、ゲームFSMからサウンドFSMに送出されるコード番号、チャネル、Waveファイルのバイト数、チャネル内のオフセットを示します。オフセットはFSMが解析する先頭アドレスです。+16はwaveヘッダ等を読み飛ばすためです。
表1 サウンドデータとサウンドチャネルの関係
| 説明 | コード番号 | チャネル | バイト数 | 先頭オフセット+16 |
|---|---|---|---|---|
| 自機弾発射音 | 1 | 自機音チャネル(#0) | 4,318 | 0 + 16 |
| 自機爆発音 | 2 | 自機音チャネル(#0) | 8,776 | 4,318 + 16 |
| 自機増加音 | 9 | 自機音チャネル(#0) | 5,500 | 13,094 + 16 |
| インベーダ爆発音 | 3 | インベーダ音チャネル(#1) | 4,622 | 0 + 16 |
| インベーダ歩行音1 | 4 | インベーダ音チャネル(#2) | 1,266 | 0 + 16 |
| インベーダ歩行音2 | 5 | インベーダ音チャネル(#2) | 1,570 | 1,266 + 16 |
| インベーダ歩行音3 | 6 | インベーダ音チャネル(#2) | 1,570 | 2,836 + 16 |
| インベーダ歩行音4 | 7 | インベーダ音チャネル(#2) | 2,180 | 4,406 + 16 |
| UFO爆発音 | 8 | UFO音チャネル(#3) | 25,968 | 0 + 16 |
| UFO飛行音 | 10 | UFO音チャネル(#3) | 1,846 | 25,968 + 16 |
4.2 サウンドシステムのブロック図
以前のVerilog版のサウンドシステム1チャネルのブロック図を、図5に示します。基本的にはゲームFSMからサウンドコードを受け、シリアルDACに音声データをシリアルで送出します。
図5中の上のサウンドROMには、Wave形式でPCMデータが格納されています。図5中の左のサウンド(wave)FSMはwaveデータの構造を解析し、データを読み出し、パラシリモジュールに送出します。図5中の右のパラシリモジュールは文字通りパラレルデータをシリアルデータに変換してシリアルDACに送出するだけでなく、シリアルDACやシステムが必要とするタイミングを生成します。
 |
|---|
| 図5 旧サウンドシステムブロック図 |
一方、新仕様のブロック図は図6のようになります。色付けの部分が増設モジュールです。サウンドFSMを4チャネルに拡張し、同時発声可能なようにミキサーを新設します。
 |
|---|
| 図6 新サウンドシステムブロック図 |
4.3 BSVによるROMの作成
サウンドROMをBSVで作成します。ROMは合成には使用しませんが、bsimシミュレーションのために必要です。ROMは書き込まないRAMとして実装します。RAMはBSVではRegFileライブラリを使用します。RegFileは実際には5R1WのマルチポートRAMであり、その1ポートのみを使用します。
最初にライブラリRegFileを導入します。
import RegFile::*;
インスタンスは以下のように行います。同時にROMファイルの内容をロードします。
typedef Bit#(15) Addr;
typedef Bit#(8) Data;
RegFile#(Addr, Data) rom <- mkRegFileLoad("sound_data/ch00.hex", 0, 18593);
以下にROMファイルの内容を示します。チャネル0のファイルは3つのサウンドを持つ、18,594バイトのWave形式のファイルです。
52
49
46
46
d6
10
:
4.4 設計上の注意点
4.4.1 映像とサウンドの同期
映像とサウンドを一致させるには、一種の難しさがあります。
- ワンショット --- 映像のほうがサウンドよりも長いため、ひとつの映像事象で複数のサウンドが鳴ってしまう。例えば自弾がどこにも当たらずに飛行して壁で爆発するまでに、発射音が複数回鳴ってしまう。
 |
|---|
| 図7 ワンショットNGの例 |
- プリエンプション --- 映像よりもサウンドのほうが長いため、2度目の映像事象でサウンドが鳴らない。例えばインベーダが非常に短い間隔で消滅した場合、2度目の消滅音が無視されてしまう。
 |
|---|
| 図8 プリエンプションNGの例 |
これらは一見矛盾するため、解決法を考える必要があります。状態ではなくエッジでサウンドを起動すれば解決できそうです。ただし、サウンド再生中に中断及び再実行可能にする必要があります。
 |
|---|
| 図9 ワンショットOKの例 |
 |
|---|
| 図10 プリエンプションOKの例 |
4.4.2 ゲームとサウンドの連携
ゲーム制御とサウンドのFSMでは動作周波数が30倍も異なり(後に3倍に修正)、ゲーム制御FSMからのサウンド指示間隔が短いと取りこぼす可能性があることから、最初の試行ではゲームFSMとサウンドFSMの間に図11のように、サウンドキュー(FIFO)を設けました。しかしながら実験の結果、FIFOを用いるとサウンドレコーダーのように、取りこぼしは無いもののサウンドが遅れて演奏されてしまいました。そのため、リアルタイム性を考慮し、1段のバッファに変更しました。
うまく行ったかに見えたのですが、たまに取りこぼすため、ILAを接続し、実行時に波形を観測したところ、取りこぼしの原因は周波数差ではなく、ハンドシェイクの不足でした。バッファにはemptyフラグを設け、ゲームFSMからコードを書き込むと!emptyとなり、それをサウンドFSMが読み、!emptyの時にのみ動作し、読み出すとemptyとなるように制御していました。ところがサウンドFSMが受け取らないうちにコードが上書きされてしまう事象がILAにより観測されたので、emptyの時に限りコードを書き込むように修正したところ(図11のマゼンタ色矢印を追加)、問題が解消されました。
 |
|---|
| 図11 ゲーム制御FSMとサウンドFSMの連携 |
以下に出力側(Game Control FSM)のサウンド出力関数のソースを示します。
// サウンド出力
function Stmt sound(UInt#(4) code);
return (seq
if (fempty) seq
action
inscode <= code;
fwen <= False;
endaction
action
fwen <= True;
endaction
action
fwen <= False;
endaction
endseq
endseq);
endfunction
ハンドシェーク用にemptyとenbleを明示的に書いていますが、BSVには自動的にそれらを生成する機能があるようで、それを用いるとcodeを出力するだけでよくなるはずです。 FIFOにはそれらのハンドシェークがあるので、FITOを1段にしても良かったのかもしれません。BSVでは1段のFIFOは設計できないようです。ですが、4段くらいのFIFOであれば遅延は目立たないと思われるため、BSVにより最小レイテンシーのFIFOを生成して実験する予定です。
4.5 コール/リターン/スタック
シーケンス(ステートの遷移)を共通化し、いろいろな場所から共有することを共通シーケンスと呼んでいますが、ソフトウエアと同じようにサブルーチンとも呼びます。これは、戻りステートを記憶するスタック(rs)、そのトップを示すスタックポインタ(sp)、サブルーチンを呼び出す命令をcall、元のシーケンスに戻ることをreturnというような、ソフトウエアの概念を導入するためです。
4.5.1 レジスタ配列によるリターンスタック
まずリターンスタックrsを配列宣言します。
// return stack
Reg#(State_t) rs[3];
次に、リターンスタックrsを3段、レジスタによりインスタンシエートします。Verilogでは宣言しただけで使用できますが、BSVでは宣言した後、インスタンシエートが必要です。
for (int i = 0; i < 3; i = i + 1)
rs[i] <- mkRegU;
スタックポインタspを宣言及びインスタンシエートします。スタックが3段なので、2bitのレジスタで初期値を0としてインスタンシエートします。
// stack pointer
Reg#(UInt#(2)) sp <- mkReg(0);
4.5.2 マクロ命令の定義
以下は、サブルーチンコール、リターン等のマクロ命令です。ソフトウエアではPCは暗黙的に進むので必要ないのですが、ハードウエアのFSMなのでnext命令が必要です。
`define call(SUB) `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext rs[sp] <= State_t {func:state.func, step:nextStep()}; sp <= sp + 1
`define return state <= rs[sp-1]; sp <= sp - 1
`define next state.step <= nextStep()
4.6 サウンドFSMの作成
Waveフォーマット解析とデータ供給を実行するFSMの設計を行います。このような小さいFSMであっても階層設計を行います。その理由はソフトウェアと同じで、構造化のためです。
4.6.1 最上位階層
最上位階層は図12のようにINIT, SOUNDの2ステートとします。基本的にINITでは外部からサウンドコードが送信されてくるのを待ち、自分のコードであればSOUNDに遷移します。サウンド出力が終了すると、またINITに戻ります。
 |
|---|
| 図12 最上位階層 |
フラットなFSMではステート変数を整数で持ちますが、階層FSMでは、ステートを構造体で持つことにします。階層は3階層で、上位2階層が意味のある機能を示し、最下層はステップとします。次に構造体の記述を示します
typedef struct {
Category_t cat;
Function_t func;
Step_t step;
} State_t deriving(Bits,Eq);
上位からカテゴリー、ファンクション、ステップと名付けました。最上位のカテゴリーは先の図12のように、 INIT, SOUNDの2ステートからなります。
typedef enum { INIT, SOUND } Category_t deriving(Bits,Eq);
4.6.2 INIT階層
INITでは中間階層である機能は特になく、2ステートを持ち、LRCLKと同期させます。これはFSMクロックがLRCLKよりも速いため、LRCLKと確率的に位相が合わなくなるためです。
4.6.3 SOUND階層
SOUNDでは機能としてFORMAT, DATA, PLAY, READCOUNT, READMEMの5種を持ちます。それぞれの機能は、フォーマット解析、データ長取得、演奏です。さらにそこから呼ばれる共通シーケンス(サブルーチン)として、データ長読み出し、データ1バイト読み出しが存在します。
 |
|---|
| 図13 SOUND階層内ステート |
第2階層であるファンクション変数の定義です。
typedef enum { FORMAT, DATA, PLAY, READCOUNT, READMEM } Function_t deriving(Bits,Eq);
同階層内にコール関係があり、DATAからREADCOUNTをコールします。さらにREADCOUNTからREADMEMをコールするので、リターンスタックは2段必要です。
最下層のステップの名前には特に意味が無く、シーケンシャルにステートを進めるだけです。シーケンシャルになる理由は、フォーマット解析やROMのデータ読み出しレイテンシ待ちなど様々です。
typedef enum { S0, S1, S2, S3, S4, S5, S6 } Step_t deriving(Bits,Eq);
以上は宣言であり、実際のインスタンシエーションは以下のようにモジュール内部で行います。
Reg#(State_t) state <- mkReg(State_t{cat:INIT,func:?,step:S0});
ステート構造体stateと、さらに同じ構造を持つ2本のリターンレジスタret, ret2をインスタンスしています。
4.6.3.1 SOUND-FORMAT階層
基本的にBluespecにおいてはrule文のガードによりステートに入る条件を定義し、rule文の内部でステートの処理を定義します。そこで、ruleを構造化することで、ステートの構造化を実現します。具体的には以下のような構造となります。
rule ruleSOUND (state.cat == SOUND);
rule ruleFORMAT (state.func == FORMAT);
rule ruleS0 (state.step == S0);
case (code)
'h1: romaddr <= 0 + 16;
'h2: romaddr <= 4318 + 16;
'h9: romaddr <= 13094 + 16;
endcase
`call(READCOUNT);
endrule
rule ruleS1 (state.step == S1);
romaddr <= romaddr + extend(dcount);
`nextFunc;
endrule
endrule // FORMAT
ruleS0ではcodeによりROMアドレス先頭を決定します。Waveフォーマットの16バイト目からフォーマット長取得を行います。readcount()をコールしており、そのリターンはruleS1ステートです。readcount()ではdcount変数に4バイトの数値が得られます。
 |
|---|
| 図14 FORMAT機能ステート遷移図 |
4.6.3.2 SOUND-DATA階層
dcountにフォーマット長が得られたので、次にデータ長を取得します。
rule ruleDATA (state.func == DATA);
rule ruleS0 (state.step == S0);
romaddr <= romaddr + 4; // skip "data"
`call(READCOUNT);
endrule
rule ruleS1 (state.step == S1);
romaddr <= romaddr - 1;
`pushCall(PLAY, WAIT);
endrule
endrule // DATA
dcountにデータ長が得られたので、実際のサウンドデータを出力するため、PLAYに移行します。
 |
|---|
| 図15 DATA機能ステート遷移図 |
4.6.3.3 SOUND-PLAY階層
PLAYにおいては4倍のインターポレーションを行うため、4回同じデータを出力します。さらにROMアドレスを+1します。これをdcountに格納されているデータ長だけ繰り返します。また、プリエンプションのために、コードが有効かどうかをチェックし、有効であれば最初のステートに戻ってサウンド演奏を新規に始めます。
4.6.3.4 READCOUNT
FORMAT機能、DATA機能からコールされるREADCOUNT共通シーケンス及び、そこからコールされるREADMEM共通シーケンスを解説します。
// input: romaddr
// output: (romaddr,...,romaddr+3) => dcount;
// romaddr + 4 => romaddr;
rule ruleREADCOUNT (state.func == READCOUNT);
rule ruleS0 (state.step == S0);
i <= 3;
workd <= 0;
`next;
endrule
rule ruleS1 (state.step == S1);
worka <= romaddr + i;
`call(READMEM);
endrule
rule ruleS2 (state.step == S2);
if (i == 0) begin
dcount <= truncate(workd<<8) | extend(romdata);
romaddr <= romaddr + 4;
`return;
end else begin
workd <= workd<<8 | extend(romdata);
i <= i - 1;
state.step <= S1;
end
endrule
endrule // READCOUNT
図示すると、図16のようなステート遷移となり、リトルエンディアンで格納されている4バイトの数値を1バイトずつ4回取り出し、dcountにまとめる機能を持ちます。
 |
|---|
| 図16 READCOUNT共通シーケンスステート遷移図 |
4.6.3.5 READMEM
次にREADMEMはROMから1バイト読み出す共通シーケンスです。当初はwireを用いても階層の上り下りでレイテンシがかかり、7サイクルもかかっていました。その後、mkConnectionを用いたことにより、RTLと同様の3サイクルの設計とすることができました。
上記のREADCOUNTから呼ばれる際はサイクル数は、フォーマット解析中のため無関係です。一方、サウンド再生中は正しいスループットで読み出す必要があります。Waveデータ中のスループットに合わせるためです。サウンド演奏中のサイクルを計算すると、コール元であるPLAYの1サイクルと、コール先であるREADMEMの3サイクルの、計4サイクルで1バイトを読み出す前提で、FSMのクロック周波数=176.4KHzを決めています。
// READ MEM
// input: worka
// output: romdata;
rule ruleREADMEM (state.func == READMEM);
rule ruleS0 (state.step == S0);
addr <= worka;
`next;
endrule
rule ruleS1 (state.step == S1); // ROM address phase
`next;
endrule
rule ruleS2 (state.step == S2); // ROM data phase
data <= romdata;
`return;
endrule
endrule // READMEM
4.7 サウンドFSMの完成
ミキサーは4chある音源のミキシングを行います。ミキシングは符号無し8bit整数を16bitに符号拡張し、加算することで行います。念のためにクリッピング処理を入れています。
完成したsound階層を図17に示します。
 |
|---|
| 図17 Vivado IP Integrator sound階層ブロック図 |
従来回路図5と比べてサウンドチャネルが4倍になっただけでなく、ミキサー回路を新設したため、かなり大きくなっています。表2に結果の数値を示します。サウンドFSMはBSVで448行でしたが、bscにより生成されたVerilogは約950行で2倍程度になっています。
表2 サウンドFSM結果
| BSV行数 | 生成Verilog行数 | FPGA LUT数 |
|---|---|---|
| 448 | 922~957 | 184~197 |
幅があるのは、サウンドFSMは4種あり、機能が若干異なるためです。また、ここまでのインベーダゲーム全体のLUTの使用個数は4,216個であり、FPGA全容量70,560個中の5.98%でした。またBRAMは使用個数は39.5であり、全容量216中の18.3%でした。
BSVの勉強から初めて約1週間でサウンドFSMが完成しました。
4.7.1 サウンドの修正
インベーダの歩行音は、隊列に同期して出力されます。インベーダ一匹の歩行処理は60Hzで実施されるため、初期状態では55/60secに一度、最後の一匹では1/60secに一度歩行音が出力されます。
ところが、最後の一匹の時に歩行音が速すぎると思っていたら、インベーダの数に応じた間隔で歩行音が出力され、必ずしも隊列の動作とは同期していないことが判明しました。
表4 歩行間隔データ配列
| インベーダ数[匹] | 歩行音間隔[tick] |
|---|---|
| 55～50 | 52 |
| 49～43 | 46 |
| 42～36 | 39 |
| 35～28 | 34 |
| 27～22 | 28 |
| 21～17 | 24 |
| 16～13 | 21 |
| 12～10 | 19 |
| 9, 8 | 16 |
| 7 | 14 |
| 6 | 13 |
| 5 | 12 |
| 4 | 11 |
| 3 | 9 |
| 2 | 7 |
| 1 | 5 |
この表をBSVにより実装します。タイマ初期値の最大値は52なので6bitのレジスタが55個必要です。1から55までを使用しており、0を含めた56個を定義しています。
UInt#(6) inv_init_stimer[56] = {5, 5, 7, 9,11,12,13,14,16,16,19,19,19,21,21,21,21,24,24,24,
24,24,28,28,28,28,28,28,34,34,34,34,34,34,34,34,39,39,39,39,
39,39,39,46,46,46,46,46,46,46,52,52,52,52,52,52};
この表は次のタイマがタイムアウトした際に、インベーダ数で引き、初期化するための表です。ここで、タイマ本体を実装します。
Reg#(UInt#(6)) inv_stimer <- mkRegU;
次に、サウンドパターンは表1で示すように、4から7を繰り返すため、2bitのパターンレジスタを用意します。
Reg#(UInt#(2)) inv_spattern <- mkRegU;
初期化部分です。タイマの初期値は52とします。パターンの初期値は0とします。
inv_stimer <= 52;
inv_spattern <= 0;
隊の先頭で実施していた次のサウンド出力処理を削除します。
// if (inv_ido != END_STATE) seq
// sound(extend(inv_pattern) + 4); // from 4 to 7
// endseq
その代わり、 全てのインベーダについて次の処理を追加します。
// 全てのインベーダについて処理
if (inv_stimer == 0) seq
sound(extend(inv_spattern) + 4); // from 4 to 7
inv_spattern <= inv_spattern + 1;
inv_stimer <= inv_init_stimer[inv_no];
endseq else seq
inv_stimer <= inv_stimer - 1;
endseq
5. Second step - ゲームFSMの設計
引き続き、ゲームFSMのステートマシン設計を行います。
サウンドFSMの設計では、ステートベースの設計手法によりFSMを設計しました。ステートベースのFSM設計手法とは、本稿では、シーケンスを人手でステートに分解し、一つ一つのステートに対してルールを書く手法を指します。この手法だと、基本的にはVerilogと同程度の工数がかかります。つまり、高級言語を使ったご利益があまりありません。一方、BSVにはステートマシンを効率的に設計できる、StmtFSMというライブラリが存在します。今回のゲームFSMではこれをフル活用して、人手によるステート分解をせずに設計します。この手法を本稿では、ステートベースに対応して、シーケンスベースと呼ぶことにします。
5.1 ゲームFSMのアルゴリズム
基本的にはCで記述するようにゲームが記述できることが分かりました。例えば、弾の移動及び衝突判定、衝突処理(爆発マーク)、爆発マーク消去等のアルゴリズムを考えると、自弾、敵弾共にアルゴリズムは共通です。それを疑似コードで書けば、
if (弾爆発タイマ >= 1) { // 弾爆発中
弾爆発タイマ++;
if (弾爆発タイマ == MAX) {
弾削除; // 論理的な消去
弾爆発マーク消去;
弾爆発タイマ停止;
}
} else {
if (弾が出ていない and 弾生成条件) {
弾生成処理;
弾発射音; // 自弾のみ、敵弾は発射音無し
}
if (弾存在) {
衝突判定;
if (対象物に衝突) { // 自弾の場合はインベーダ及びUFO、敵弾の場合は自機
弾削除; // 論理的な消去
弾マーク消去; // 物理的な消去
対象物ステート <= 爆発;
対象物爆発タイマ <= 0;
} else if (上下ハズレ || ベース || 弾) { // 弾:自弾の場合は敵弾、敵弾の場合は自弾
弾マーク消去; // 物理的な消去
弾爆発マーク;
弾爆発タイマ <= 1;
} else { // 衝突していない場合
弾を進める;
}
}
}
のようになります。このコードは1tick毎に実行されます。対象物(自弾の場合はインベーダ及びUFO、敵弾の場合は自機)の場合は、衝突時に対象物が爆発し、弾が爆発しないので、いきなり弾の論理的・物理的消去を行います。一方、上下の壁、ベース、何か(普通は相手の弾)に衝突した場合は、弾の爆発処理を行ってから弾の論理的な消去を行います。
一方、対象物の処理は、
if (対象物ステート == 爆発) {
if (対象物爆発タイマ==0) {
対象物爆発タイマ <= 1;
対象物爆発音;
対象物爆発マーク;
} else {
対象物爆発タイマ++;
if (対象物爆発タイマ == MAX) {
対象物削除; // 論理的な消去
対象物爆発マーク消去; // 物理的な消去
}
}
}
のように専用処理が必要です。このコードも1tick毎に実行されます。自機、インベーダは上記のように2ステップ(爆発、消去)で爆発しますが、UFOはさらに得点表示が加わり、3ステップ(爆発、得点、消去)で爆発します。
StmtFSMを適用すれば、このようなシーケンスをクロック毎のステートに分解せずに、アルゴリズムのまま記述できます。この疑似コードはC-likeで書いていますが、BSVでは'{'をseqに、'}'をendseqにするだけです。if、while、forなどの制御構文はbscにより動作合成され、ステートマシンに変換されます。
Verilog版の設計では、ステート遷移は全ステップがgoto文であり、構造化できなかったため、デバッグに苦労しました。一方BSVでは構造化でしか書けないため、デバッグは比較的楽でした。
5.2 ゲームのタイミング
以前、FPGAエクストリーム・コンピューティングでVerilog版を発表した際に、タイミングについて質問があったので解説します。基本の1 tickは1/60秒で、その中で、インベーダ1匹、敵弾全弾、自機、自弾、UFO、スコア等の処理を行います。以下は実際のBSVのメインループのコードです
while (game_flag) seq // メインループ
for (noy <= 0; noy < `Inv_TateS; noy <= noy + 1) seq // インベーダの行処理
for (nox <= 0; nox < `Inv_YokoS; nox <= nox + 1) seq // インベーダの列処理
if (inv_s[nox][noy]) seq // インベーダが生きてれば
ivader; // インベーダ処理
gun; // 自機処理
bullet; // 自弾処理
for (idx <= 0; idx < extend(max); idx <= idx + 1) seq
invBullet(idx); // 敵弾全弾処理
endseq
ufo; // UFO処理
scores; // スコア表示
endJudge; // 終了判定
counter <= counter + 1; // tickカウンタ++
wait_timer; // インナーループを1/60secにするウエイト
endseq
endseq
endseq
endseq
gameOver; // ゲームオーバー表示
1tick=1/60secの間に、生きているインベーダ1匹(2ピクセル)の処理に対して、自機(1ピクセル)、敵弾(1ピクセル4ピクセル/3tick(インベーダが8匹未満の時は5ピクセル/3tick))、自弾(4ピクセル)の処理が行われます。ちなみにUFOは0.5ピクセル移動です。インベーダは初期に55匹存在するので、インベーダ全体の速度としては1/55倍の遅さで始まりますが、数が減るにつれて速くなり、最終的に1倍のスピードになります。従って、インベーダを倒すたびにインベーダ全体は速くなり、一方その他の速度は変わらないわけです。
【追記begin】
上記のように、敵弾の移動速度をソースコードの解析を参照し、1ピクセル/tickから4ピクセル/3tickと変更しました。具体的には、敵弾は3tick毎に処理します。0番目、1番目のタイムフレームでは何もしません。2番目のタイムフレームで一挙に4ピクセル動かすのではなく、1ピクセルずつ下方に(仮想的に)動かします。実際には移動表示は行なわず、衝突判定のみを行います。1ピクセルずつ下にずらし衝突判定を行い、もしオブジェクトが存在すれば、そこで爆発マークを表示し、検索を中止します。これにより所望の動作が行われます。
【追記end】
FPGAでの実装では1 tick内にインベーダ全体を移動することは可能ですし、そのような実装も見ますが、ゲーム性が変わってしまいます。具体的には、インベーダ全体の速度が次第に速くならなかったり、後ろのインベーダを撃つことができなくなります。
ちなみに、FPGAでの実装では、10MHz(後に1MHzに修正)のステートマシンによるコード中のインナーループ周期16.7msecの実行時間の96.4%をウエイト処理が占めています。
 |
|---|
| 図18 "H"がウエイト中を示す(FSMが10MHz動作時) |
5.3 裏ワザ
5.3.1 レインボー
レインボーは、後ろのインベーダを撃つことにより、移動の跡が消えずに残るバグ(開発者が想定していなかったようなので)です。インベーダは残りが一匹になると左へは2ピクセルずつ右には3ピクセルずつ移動します。下2段のインベーダは、左右2ピクセルまでの移動では跡が残らない図形になっていますが、3ピクセルだと跡が消えずに残ります。もちろん今回の実装でもレインボーを体験できます。図19はレインボーの原理図で、右に3ピクセルずつ移動していく様子を表しています。
 |
|---|
| 図19 レインボー原理図 |
5.3.2 名古屋打ち
名古屋打ちも実装しています。これはインベーダの弾が16ピクセル下から出現するため、その間に自機が入ると敵弾に当たらないという「振る舞い」を利用するものです。
5.4 ゲームFSMの完成
5.4.1 ゲーム画面
図20は、恐らく世界初の、BSVで設計したインベーダーゲームが実際に動いている映像です。過去記事で設計したものと比べて、サウンドが4ch同時発声と高品質になりました。ただし、画面は開発中のため得点をカットしているのと、敵弾の揃い打ちが気になったので、現在は修正済みです。
 |
|---|
| 図20 ゲームFSMの完成 |
基本的なアルゴリズムは2018年に完成しており、調整は不要でした。そのため、言語の習得から始めサウンドFSMに1週間、ゲームFSMに1週間の約2週間でインベーダゲームがおおかた完成しました。その他、例えばUFOの表示等の追加はその後1週間ほどで完了しました。
完成したinvader階層を図21に示します。button_0は単にボード上のスイッチと、外付けのスイッチのORを取る回路です。invader_move_0がBSVで設計したゲームFSMです。blk_mem_gen_0はゲームFSMに接続されるROMで、インベーダー等のパターンを記憶するROMです。
 |
|---|
| 図21 Vivado IP Integrator invader階層ブロック図 |
5.4.2 敵の強さ
敵弾の発射アルゴリズムは思ったより難しく、揃い打ち防止、連射時の追突防止等のトライアルを幾度も実施しました。追突防止は、ソースコードの解析を見ると、リロードタイムとなっているようです。
本物のインベーダーゲームでは敵が同時に複数の弾を打たないようです。一方、本プログラムでは図1のUltra96ボード上、もしくは図4のArtyボード上のDIP SWで、インベーダの強さを設定できます。具体的には、敵弾の連射の有無、及び敵弾同時発射個数(1~11個)を選択可能になっています。連射無しの場合は、敵弾が消えるまで次の敵弾は発射されません。連射有りの場合は、同時発射数だけ発射します。
表3 ArtyボードのDIP SW値と敵弾の強さ
| DIP SW値 | 連射有無 | 同時発射数 |
|---|---|---|
| 0 | 無し | 1発 |
| 1 | 無し | 2発 |
| 2 | 無し | 3発 |
| 3 | 無し | 4発 |
| 4 | 無し | 5発 |
| 5 | 無し | 6発 |
| 6 | 有り | 2発 |
| 7 | 有り | 3発 |
| 8 | 有り | 4発 |
| 9 | 有り | 5発 |
| 10 | 有り | 6発 |
| 11 | 有り | 7発 |
| 12 | 有り | 8発 |
| 13 | 有り | 9発 |
| 14 | 有り | 10発 |
| 15 | 有り | 11発 |
インベーダの同時発射数が多いと、弾幕的になるので格段に難しくなります。さらに連射が加わると、敵弾を避けてから敵の正面に入ることが難しくなるため、一層難しくなります。そのため、DIP SW=15だと激ムズになります。
5.4.3 敵弾貫通度の修正
当初は敵弾のシールド貫通度は一定でしたが、オリジナルゲーム動画を良く観察すると、敵弾の種類により貫通度が異なることを発見しました。
 |
|---|
| 図22 敵弾による貫通度の違い |
最も左のシールドに敵弾が2度当たっていますが、敵弾の種類によって左側のほうが深く潜り、右側のほうが浅く潜って爆発しています。
敵弾名はインベーダゲームソースの研究から引用しています。図23の左から、Squiggly (抵抗器のようなジグザグ)、Rolling、Plunger (パイプつまり直し)と名前がついています。
 |
|---|
| 図23 敵弾の違い |
図23において、敵弾の貫通度は左からそれぞれ3, 3, 7としています。
元々敵弾をランダム(風)に出現させるため、カウンタの値により敵弾タイプを決めていますが、同じように貫通度を決めるテーブルです。
UInt#(3) invBullet_pdval[8] = { 7, 3, 3, 7, 3, 3, 7, 3}; // pd = penetrating depth
次は貫通度を記憶するためのレジスタであり、敵弾数だけ持つ必要があります。
Reg#(UInt#(3)) invBullet_pd[`INV_BULLET_MAX];
このレジスタを各敵弾にひとつ持たせるために敵弾の同時最大数だけインスタンシエートします。
for (int ii = 0; ii < `INV_BULLET_MAX; ii = ii + 1) begin
:
invBullet_pd[ii] <- mkRegU;
:
end
敵弾発生部において、上の行が元々のタイプを決定するロジックでしたが、同じロジックにより、上記の貫通度の表を引いてpdを記録します。
invBullet_type[idx] <= invBullet_rand[truncate(counter) & 3'h7];
invBullet_pd[idx] <= invBullet_pdval[truncate(counter) & 3'h7];
敵弾衝突の一部です。この2つのseq - endseqブロックは元は一つでしたが、base(バリケード)の時だけこの貫通度を使用するように分離します。他の場合は最深(貫通度=7)固定とします。
endseq else if (fbase) seq
eraseInvBullet(invBullet_x[idx], invBullet_y[idx]); // 現敵弾消去
explodeInvBullet(invBullet_x[idx], invBullet_y[idx], invBullet_pd[idx]); // 次敵弾爆発
invBullet_expTimer[idx] <= 1; // 敵弾爆発タイマスタート
voff <= 5; // break 'for'
endseq else if (fobj || invBullet_y[idx] >= 225) seq
eraseInvBullet(invBullet_x[idx], invBullet_y[idx]); // 現敵弾消去
invBullet_pd[idx] <= 7; // 最深
explodeInvBullet(invBullet_x[idx], invBullet_y[idx], 7); // 次敵弾爆発
invBullet_expTimer[idx] <= 1; // 敵弾爆発タイマスタート
voff <= 5; // break 'for'
コール先の爆発ルーチンです。爆発は、爆発マークを表示することで開始します。
// 敵弾爆発
function Stmt explodeInvBullet(
UInt#(8) destx,
UInt#(8) desty,
UInt#(3) pd);
return (seq
orArea(43, 16, destx - 3, desty + extend(pd), 8, 8);
endseq);
endfunction
爆発マーク消去コール部分です。爆発開始から一定時間後に、保存してある貫通度を使用して爆発マークを消去します。
expEraseInvBullet(invBullet_x[idx], invBullet_y[idx], invBullet_pd[idx]); // 敵弾爆発マーク消去
コール先の爆発マーク消去ルーチンです。
// 敵弾爆発マーク消去
function Stmt expEraseInvBullet(
UInt#(8) destx,
UInt#(8) desty,
UInt#(3) pd);
return (seq
eraseAreaSP(43, 16, destx - 3, desty + extend(pd), 8, 8);
endseq);
endfunction
6. 終わりに
最後にまとめます。
6.1 BSVの優位性
表5に前回のVerilog版の結果を、表6に今回BSVで作成したゲームFSMの結果の数値を示します。これだけ見るとBSVは効率が良さそうなものの、bscのコンパイル時間が新たに加わり、大規模なデザインではそれが1時間以上にもなります。従って、そのようなデザインでは、修正、モデル作成、シミュレーションのTATが非常に長くなり、却ってVerilogよりも効率が悪くなるかもしれません。ただ、シミュレーションはBluesimのほうがiverilogよりも約3,000倍高速でした。
BSVではパッケージが名前空間に相当するので、外部関数毎に別々にコンパイルできれば効率が良くなりそうです。
表5 Verilog版ゲームFSM結果
| Verilog行数 | FPGA LUT数 |
|---|---|
| 2,129 | 3,239 |
表6 新BSV版ゲームFSM結果
| BSV行数 | 生成Verilog行数 | FPGA LUT数 |
|---|---|---|
| 1,205 | 361,687 | 6,570 |
結果として、図らずも、サウンドFSMがステート(ルール)ベースによる設計、ゲームFSMがシーケンスベースの設計という、異なった2つの設計手法によりFSMが設計できました。表2と表6に関してBSVとVerilogの行数の比を見ると、ルールベース(表2)では2.1倍であるのに対して、シーケンスベース(表6)では300倍と激増していることが分かります。ただデザインの規模が数十倍も違うのでそれを考慮する必要があります。激増する原因は、ステートマシンの自動生成と関数のインライン展開のためと推測されるので、これらを軽減する手法が望まれます。
6.2 改良点
本プログラムには、以下のような改良点があります。
- グローバル変数のローカル化
関数内でのみ使用している変数は、通常関数スコープ内で定義されるローカル変数とすべきですが、現在はグローバル変数になっている。 - 関数内シーケンシャル構文のローカル化
メインループでは関数を多数呼び出していますが、それぞれがインライン展開されているようです。これはBSCコンパイル時間も1時間以上と莫大になり、また資源も再利用できないので、サブルーチンのように呼び出したい。
BSC開発者にも問い合わせていますが、今のところ思わしい解答が得られていません。
6.3 ゲーム自体について
当時も100円玉を積み上げてましたし、今度もデバッグのためにゲームを何十回も行いましたが、つくづく、インベーダの形状、1/60secを基準とした移動タイミング、次第に速くなる動作、ピクセル毎の衝突判定、時々出現するUFO、サウンド等の全てが天才的に素晴らしく、40年経っても古く感じないのは、オリジナルゲーム開発者に対してリスペクト以外にありません。
追記1：
YouTube：https://youtu.be/MiLI1Gk0IlI
これはVerilogで設計したものですが、外見や動作等は現在も変わりません。ただしサウンドはBSVでの再設計時に4声同時発生に変更したことで、現在はこの時よりも良くなっています。
追記2：
この記事でverilogソースを公開しました。このソースをVivadoで合成し、FPGAにダウンロードすることでインベーダーゲームを動作させることができます。