Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
10
Help us understand the problem. What is going on with this article?
@mocapapa

BSV (Bluespec SystemVerilog)によるスペースインベーダーの再設計

1. はじめに

2018年に、インベーダーゲーム生誕40周年記念として、Verilog HDLでスペースインベーダーを設計しましたが、これはその続きで、同じくフルハードウェアによりスペースインベーダーを設計したものです。

2020年1月に、Bluespecがbsc (Bluespec SystemVerilog Compiler)をオープンソース化しました。そこで、早速bscをインストールしてみました。bscはBSV(Bluespec SytemVerilog)言語で書かれたデザインを高位合成するコンパイラです。BSV言語の習得は、他の言語と同様、いくらマニュアルを読んでも身につかないので、設計するしかないと思い、前回作成したインベーダーゲームの、BSVを用いた再設計にトライしました。

image.png
図1 FPGAボード(Avnet Ultra96)+作成したPMODインタフェースボード

図1はUltra96 FPGAボードと2018年に開発したUltra96toPMODボードです。

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例くらい見つかりました。

image.png
図2 他の実装例

しかし、HDLという不自由な言語で実装するのでやむを得ない面があるとはいえ、ほとんどのものがシールド(バリケード)がなかったり、インベーダが撃ってこなかったり、単純なものが多いのです。それだけでなく、40年前に感動した、オリジナルに有ったピクセル毎の衝突判定がありません。それではつまらないので、限りなくオリジナルに近い動作を目指しました。名古屋打ちレインボー等の裏ワザも使用できます。

image.gif
図3 ピクセル毎の衝突判定処理

1.4 スペースインベーダーの要件

上記のようにショボいインベーダーを作らないよう、必要最低限の要件をまとめます。逆にこれらを実装すれば、インベーダゲームとしては、かなり良い完成度のものができるのではないでしょうか。

  • 図形パターンは、これを使用する。ただし移動量(下記参照)に合わせた黒バックを含む大きさを持つ。
  • インベーダーは横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のスコア法則の表から得点を決定する。
  • サウンドは雰囲気を出すためにぜひ欲しい。サウンドデータはここにあります。が、歩行音等が歪んでいて汚いのと、歩行音に対して自弾の発射音や爆発音が大きいので音量バランスが悪いです。Audacity等のオーディオ編集ソフトで音量バランスを整える必要があります。
  • 歩行音はA, B, C, Dの4種類あり、順番に出力する。インベーダの数によってサウンドを出す間隔を変える。その表は以下のとおり。 https://fs-micro.com/post/show/id/318

1.5 使用機材

基本的には過去記事に書いたとおり、中心はUltra96 FPGAボードだったのですが、これには図1のUltra96toPMODボードが必要となります。今回、新たにArtyボードに移植し、基本的にはArtyボードと各インタフェースボードのみで済むようになりました。ArtyボードはPMODインタフェースを4個持つため、(新規開発の)Ultra96toPMODボードが不要です。その上、FPGAボードの価格も半額以下の1万3千円くらいです。

image.png
図4 Artyボードと各種インタフェースボード

2. First step - サウンドFSMの設計

初めてBSVを適用するにあたり、サウンドステートマシンは規模が比較的小さいため、まずそれを設計対象としました。合わせて仕様もグレードアップしようと思います。Verilog版では、サウンドチャネルは1個としたので、サウンド間の優先度判定が必要でした。今回はサウンドチャネルを複数持たせ、サウンドの重ね合わせを行います。

2.1 サウンドチャネルの決定

ゲームに使用されているサウンドは表1に示す10種類です。10種類のうち、同時発声数数=サウンドチャネル数を決める必要があります。ゲームシナリオでの同時発生条件を考え、自機音、インベーダ音1, 2、UFO音の4チャネルとします。1チャネルは複数のサウンドデータから構成されます。サウンドデータはWaveフォーマットです。

以下に、サウンドの説明とゲーム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

2.2 サウンドシステムのブロック図

Verilog版のサウンドシステム1チャネルのブロック図を、図5に示します。基本的にはゲームFSMからサウンドコードを受け、シリアルDACに音声データをシリアルで送出します。

図5中の上のサウンドROMには、Wave形式でPCMデータが格納されています。図5中の左のサウンド(wave)FSMはwaveデータの構造を解析し、データを読み出し、パラシリモジュールに送出します。図5中の右のパラシリモジュールは文字通りパラレルデータをシリアルデータに変換してシリアルDACに送出するだけでなく、シリアルDACやシステムが必要とするタイミングを生成します。

image.png
図5 旧サウンドシステムブロック図

新仕様のブロック図は図6のようになります。色付けの部分が増設モジュールです。サウンドFSMを4チャネルに拡張し、同時発声可能なようにミキサーを新設します。

image.png
図6 新サウンドシステムブロック図

2.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
:

2.4 設計上の注意点

2.4.1 映像とサウンドの同期

映像とサウンドを一致させるには、一種の難しさがあります。

  • ワンショット --- 映像のほうがサウンドよりも長いため、ひとつの映像事象において複数のサウンドが鳴ってしまう。例えば自弾がどこにも当たらずに飛行して壁で爆発するまでに、発射音が複数回鳴ってしまう。
image.png
図7 ワンショットNGの例
  • プリエンプション --- 映像よりもサウンドのほうが長いため、2度目の映像事象にサウンドが鳴らない。例えばインベーダが非常に短い間隔で消滅した場合、2度目の消滅音が無視されてしまう。
image.png
図8 プリエンプションNGの例

これらは一見矛盾するため、解決法を考える必要があります。状態ではなくエッジでサウンドを起動すれば解決できそうです。ただし、サウンド再生中に中断及び再実行可能にする必要があります。

image.png
図9 ワンショットOKの例
image.png
図10 プリエンプションOKの例

2.4.2 ゲームとサウンドの連携

ゲーム制御とサウンドのFSMでは動作周波数が30倍も異なり(後に3倍に修正)、ゲーム制御FSMからのサウンド指示間隔が短いと取りこぼす可能性があることから、最初の試行ではゲームFSMとサウンドFSMの間に図11のように、サウンドキュー(FIFO)を設けました。しかしながら実験の結果、FIFOを用いるとサウンドレコーダーのように、遅れてサウンドが演奏されてしまいました。そのため、リアルタイム性を考慮し、1段のバッファに変更しました。

うまく行ったかに見えたのですが、たまに取りこぼすため、ILAを接続し、実行時に波形を観測したところ、取りこぼしの原因は周波数差ではなく、ハンドシェイクの不足でした。バッファにはemptyフラグを設け、ゲームFSMからコードを書き込むと!emptyとなり、それをサウンドFSMが読み、!emptyの時にのみ動作し、読み出すとemptyとなるように制御していました。ところがサウンドFSMが受け取らないうちにコードが上書きされてしまう事象がILAにより観測されたので、emptyの時に限りコードを書き込むように修正したところ(図11のマゼンタ色矢印を追加)、問題が解消されました。

image.png
図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段にしても良かったのかもしれません。

2.5 コール/リターン/スタック

シーケンス(ステートの遷移)を共通化し、いろいろな場所から共有することを共通シーケンスと呼んでいますが、ソフトウエアと同じようにサブルーチンとも呼びます。これは、戻りステートを記憶するスタック(rs)、そのトップを示すスタックポインタ(sp)、サブルーチンを呼び出す命令をcall、元のシーケンスに戻ることをreturnというような、ソフトウエアの概念を導入するためです。

2.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);

2.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()

2.6 サウンドFSMの作成

Waveフォーマット解析とデータ供給を実行するFSMの設計を行います。このような小さいFSMであっても階層設計を行います。その理由はソフトウェアと同じで、構造化のためです。

2.6.1 最上位階層

最上位階層は図12のようにINIT, SOUNDの2ステートとします。基本的にINITでは外部からサウンドコードが送信されてくるのを待ち、自分のコードであればSOUNDに遷移します。サウンド出力が終了すると、またINITに戻ります。

image.png
図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);

2.6.2 INIT階層

INITでは中間階層である機能は特になく、2ステートを持ち、LRCLKと同期させます。これはFSMクロックがLRCLKよりも速いため、LRCLKと確率的に位相が合わなくなるためです。

2.6.3 SOUND階層

SOUNDでは機能としてFORMAT, DATA, PLAY, READCOUNT, READMEMの5種を持ちます。それぞれの機能は、フォーマット解析、データ長取得、演奏です。さらにそこから呼ばれる共通シーケンス(サブルーチン)として、データ長読み出し、データ1バイト読み出しが存在します。

image.png
図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をインスタンスしています。

2.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バイトの数値が得られます。

image.png
図14 FORMAT機能ステート遷移図

2.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に移行します。

image.png
図15 DATA機能ステート遷移図

2.6.3.3 SOUND-PLAY階層

PLAYにおいては4倍のインターポレーションを行うため、4回同じデータを出力します。さらにROMアドレスを+1します。これをdcountに格納されているデータ長だけ繰り返します。また、プリエンプションのために、コードが有効かどうかをチェックし、有効であれば最初のステートに戻ってサウンド演奏を新規に始めます。

2.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にまとめる機能を持ちます。

image.png
図16 READCOUNT共通シーケンスステート遷移図

2.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

2.7 サウンドFSMの完成

ミキサーは4chある音源のミキシングを行います。ミキシングは符号無し8bit整数を16bitに符号拡張し、加算することで行います。念のためにクリッピング処理を入れています。

完成したsound階層を図17に示します。

image.png
図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が完成しました。

3. Second step - ゲームFSMの設計

引き続き、ゲームFSMのステートマシン設計を行います。

サウンドFSMの設計では、ステートベースの設計手法によりFSMを設計しました。ステートベースのFSM設計手法とは、本稿では、シーケンスを人手でステートに分解し、一つ一つのステートに対してルールを書く手法を指します。この手法だと、基本的にはVerilogと同程度の工数がかかります。つまり、高級言語を使ったご利益があまりありません。一方、BSVにはステートマシンを効率的に設計できる、StmtFSMというライブラリが存在します。今回のゲームFSMではこれをフル活用して、人手によるステート分解をせずに設計します。この手法を本稿では、ステートベースに対応して、シーケンスベースと呼ぶことにします。

3.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では構造化でしか書けないため、デバッグは比較的楽でした。

3.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ピクセル動かすのではなく、一ピクセルずつ下方に(仮想的に)動かします。実際には移動表示は行なわず、衝突判定のみを行います。一ピクセルずつ下にずらし衝突判定を行い、もしオブジェクトが存在すれば、そこで爆発マークを表示し、検索を中止します。これにより所望の動作が行われます。
【追記end】

FPGAでの実装では1 tick内にインベーダ全体を移動することは可能ですし、そのような実装も見ますが、ゲーム性が変わってしまいます。具体的には、インベーダ全体の速度が次第に速くならなかったり、後ろのインベーダを撃つことができなくなります。

ちなみに、FPGAでの実装では、10MHz(後に1MHzに修正)のステートマシンによるコード中のインナーループ周期16.7msecの実行時間の96.4%をウエイト処理が占めています。

image.png
図18 "H"がウエイト中を示す

3.3 裏ワザ

3.3.1 レインボー

レインボーは、後ろのインベーダを撃つことにより、移動の跡が消えずに残る「振る舞い」(バグとは言えない)です。インベーダは残りが一匹になると左へは2ピクセルずつ右には3ピクセルずつ移動します。下2段のインベーダは、左右2ピクセルまでの移動では跡が残らない図形になっていますが、3ピクセルだと跡が消えずに残ります。もちろん今回の実装でもレインボーを体験できます。図19はレインボーの原理図で、右に3ピクセルずつ移動していく様子を表しています。

image.png
図19 レインボー原理図

3.3.2 名古屋打ち

名古屋打ちも実装しています。これはインベーダの弾が16ピクセル下から出現するため、その間に自機が入ると敵弾に当たらないという「振る舞い」を利用するものです。

3.3.3 自弾と敵弾の強さ

裏ワザではないですが、

1. 自弾と敵弾の相打ち(両方が消滅)が起こる場合、
2. 自弾だけが爆発し敵弾が生き残る場合、

の2とおりの場合があります。この勝ち負けは自弾と敵弾の距離に依存します。衝突判定アルゴリズム上、自弾と敵弾の距離が4ピクセル以上離れていると衝突しません。1から3ピクセルだと敵弾は当たらず、自弾のみが爆発します。つまり敵弾が勝ちます。最後に0ピクセルだと両方が爆発します。つまり相打ちです。従って確率的に、敵弾のほうがだいぶ強いことになります。

敵弾の移動アルゴリズムを1ピクセル/tickから4ピクセル/3tickに変更したので、相対的な強さが変わりました。メインループ内の順番的には自弾処理、敵弾処理の順であるため、必ず自弾のほうが勝ちます。

3.4 ゲームFSMの完成

3.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です。

image.png
図21 Vivado IP Integrator invader階層ブロック図

3.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だと激ムズになります。

3.4.3 サウンドの修正

インベーダの歩行音は、隊列に同期して出力されます。インベーダ一匹の歩行処理は60Hzで実施されるため、初期状態では55/60secに一度、最後の一匹では1/60secに一度歩行音が出力されます。

ところが、最後の一匹の時に歩行音が速すぎると思っていたら、インベーダの数に応じた間隔で歩行音が出力され、必ずしも隊列の動作とは同期していないことが判明しました。

表4 歩行間隔データ配列

インベーダ数[匹] 歩行音間隔[tick]
55 52
: :
50 52
49 46
: :
43 46
42 39
: :
36 39
35 34
: :
28 34
27 28
: :
22 28
21 24
: :
17 24
16 21
: :
13 21
12 19
: :
10 19
9 16
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

4. 終わりに

最後にまとめます。

4.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と表4に関してBSVとVerilogの行数の比を見ると、ルールベース(表2)では2.1倍であるのに対して、シーケンスベース(表4)では300倍と激増していることが分かります。ただデザインの規模が数十倍も違うのでそれを考慮する必要があります。激増する原因は、ステートマシンの自動生成と関数のインライン展開のためと推測されるので、これらを軽減する手法が望まれます。

4.2 改良点

本プログラムには、以下のような改良点があります。

  • グローバル変数のローカル化
    関数内でのみ使用している変数は、通常関数スコープ内で定義されるローカル変数とすべきですが、現在はグローバル変数になっている。
  • 関数内シーケンシャル構文のローカル化
    メインループでは関数を多数呼び出していますが、それぞれがインライン展開されているようです。これはBSCコンパイル時間も1時間以上と莫大になり、また資源も再利用できないので、サブルーチンのように呼び出したい。

BSC開発者にも問い合わせていますが、思うような解答が得られていません。

4.3 ゲーム自体について

当時も100円玉を積み上げてましたし、今度もデバッグのためにゲームを何十回も行いましたが、つくづく、インベーダの形状、1/60secを基準とした移動タイミング、次第に速くなる動作、ピクセル毎の衝突判定、時々出現するUFO、サウンド全てが天才的に素晴らしく、40年経っても古く感じないのは、オリジナルゲーム開発者に対してリスペクト以外にありません。

10
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
mocapapa
昔FM-7 Z80カード、77ディスプレイサブシステム、77AVのアーキテクチャを設計しました。その後はプロセッサ設計を31年。現在はISO 26262機能安全エキスパートです。趣味は黒パグと車と数学の論文を英語で書くこと。2017年の最優秀論文賞を皮切りにIEEE国際学会に論文3本が採択。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
10
Help us understand the problem. What is going on with this article?