WIZ-CODE.blog

JavaScriptやAjaxをテーマとしたブログです。

*

ステートマシンの仕組みのおさらい

      2017/08/29

サーバーでもブラウザでも動くJavaScript ステートマシン・ライブラリ Async-FSMのソースコードをGitHubで公開しました。導入方法や使い方の説明も記載しています。
Async-FSM – Finite StateMachine JavaScript Library

ステートマシン図は状態と振る舞い、そして状態の移行を表す遷移などを用いて処理の手続きを図式化したものです。プログラミングの分野ではアプリケーションやゲームの設計に用いられることがあります。当サイトで数年前にJavascriptでステートマシンを実装する記事を書きましたが、あれからライブラリに非同期な要素を取り入れるなど大幅な改良を加えまして、それがようやく一応の完成を見ました。今回はその紹介に先んじてステートマシンの周知のため再度、簡単ながら解説していきたいと思います。ライブラリ(Async FSM)の公開と使い方については次回する予定です。

ステートマシン図の定義について様々な方法論が存在しますが、ここでは統一モデリング言語(UML)の定義を扱います。自分が参考にした入門書やサイトは複数あるので、用語の使用法に統一性がない可能性がありますがそこはご了承ください。それでは具体的なステートマシン図を見ていきましょう。下の図式はRPGの一部の過程を抜き出して作成したものです。図式の簡略化のためタイトル画面から急に戦闘場面に移行するプロセスになっています。図式の状態名を矢印にそって目を通すだけで、何となく処理の流れが分かるかと思います。このようにステートマシン図はそのビジュアル性と理解しやすさから、アプリやゲームのデザイン・設計に有効な手法となっています。

ここでは、ステートマシン図の基本的な見方と、各種状態の働きについて説明していきたいと思います。

ステートマシンの開始と終了

上の図はステートマシン図を最小の構成要素で示したものです。ステートマシン(Machine)の枠内に3つの状態と、2つの遷移(矢印)が配置されています。黒く塗りつぶされた丸が開始疑似状態(Initial PseudoState)、角丸の矩形が単純状態(Simple State)、二重の丸印が終了状態(Final State)です。ステートマシンの開始はすなわちシステムの起動を表します。この図の一番外側の枠(Machineとある)はステートマシン図自体を指しています。通常、ステートマシン図を描くとき、この外側の枠が書かれることはありません。しかし、ステートマシンは状態の一種であり、後述するサブマシン状態として再利用の対象になることがあるので、それを明示するためにあえてマシンの枠も図式に記述するようにしています。さて、ステートマシン図の主役である「状態」には入場(Entry)/退場(Exit)という要素があります。ステートマシン自体はある瞬間において、常に何らかの状態にあると考えられています。ステートマシンの状態が別の状態に変化することを「遷移」と呼び、複数あるうちのある状態がステートマシンの「現在の状態」になることを「入場する」と呼びます。反対に遷移によって「現在の状態」でなくなることを「退場する」と言います。これら入場と退場の動作を「アクティブになる/非アクティブになる」と言い換えることもできるでしょう。

ステートマシンの開始は、図式に記述された「開始疑似状態(Initial PseudoState)」がアクティブになることに始まります。マシンがまだ動作していないとき、マシン内部のすべての状態は非アクティブな状態です。通常、状態から他の状態へ遷移するとき、「トリガ(イベント)」の発生がきっかけになりますが、開始疑似状態は自動的に次の状態へ遷移します。英語ではInitialとありますがここで何らかの初期化が実行されるわけではなく、ただ次の状態につなぐための橋渡しの役割しかありません。また、後述しますが疑似状態および終了状態は振る舞い(メソッド)を持つことができません。

遷移が完了すると遷移前の状態は非アクティブな状態に戻り、遷移後の状態が今度はアクティブになります。ステートマシン直下の状態が複数存在していても、アクティブな状態は常にひとつだけとなります(複数の領域がある場合を除く)。なお、上の図には載ってませんが、この後説明する「トリガ」はこの遷移を表す矢印に沿ってその名称が記述されます。上の図では開始疑似状態から「何かをする」状態に遷移した後、さらに終了状態への遷移が書かれています。この最後の遷移もまた開始疑似状態から「何かをする」状態への遷移と同様、トリガ名が記述されていません。これは、この状態が振る舞いを終えた際に自動的に次の状態に遷移することを意味し、これを完了遷移と言います。終了状態がアクティブになるとき、それは終了状態を含むステートマシンの終了を意味します。後述するコンポジット状態や領域もまた終了状態を持つことができます。ただし、こちらは終了するのが終了状態を含む自身(コンポジット状態あるいは領域)になります。その他、終了状態は自身を起点とした遷移を持つことができません。同様に開始疑似状態は自身を終点とする遷移を持つことができません。

遷移とトリガ

次の図は単純状態から単純状態への遷移を表しています。こちらの遷移には「○○○駅に到着」というトリガが記されています。このような場合、トリガが発生するまで遷移が行われることはありません。また、トリガ名に続いてブラケット([])内に「寝ていない」と書かれていますが、これはガードと呼ばれる条件判定で任意に指定することができます。ガード条件が指定されると、トリガが発生してもその条件が満たされないかぎり遷移が実行されることはありません。このケースでは、「寝ていない」が真であれば遷移が実行され、偽であれば遷移は実行されません(駅を乗り過ごします)。なお、遷移は状態と同じように振る舞いを持つことができます。この遷移中の振る舞いのことをエフェクトと呼び、図式上ではスラッシュ(/)に続いて記述されます。遷移前の状態(ここでは「電車に乗る」)が終了した直後に行われ、エフェクトは遷移後の状態がアクティブになる前に終了します。

遷移前と遷移後が同じ、つまり同一の状態で退場と入場を連続して行うことを自己遷移と呼びます。またこれと似たものに内部遷移というものがあります。この2つの違いは自己遷移が退場・入場時の振る舞いを再度実行するのに対し、内部遷移では自身の振る舞いは実行せず、遷移中のエフェクトのみ実行するという点です。

状態の振る舞い

単純状態およびコンポジット状態はアクティブ(入場)、または非アクティブ(退場)になるタイミングで、いくつか固有の振る舞いを実行します。プログラミングで実装される「状態」はオブジェクトの形が多いので、振る舞い=メソッドと考えてもいいでしょう。なお、前述とおり疑似状態と終了状態は振る舞いを持つことができません。振る舞いは入場時の入場アクション、アクティブ中に実行するDoアクティビティ、退場時に行う退場アクションの3つです。アクションとあるものは、即時実行して終了する振る舞いであるのに対し、Doアクティビティは継続して実行するもので処理中の割り込みや中断が認められています。これらの振る舞いを実行するかは任意であり、特にDoアクティビティは設計において省略されることが多いです。また、これらの振る舞いの実行タイミングですが細かく見ると、まず入場アクションはその状態がアクティブになった直後に実行され、退場アクションは状態が非アクティブになる直前に実行されます。プログラミングにおいては、入場アクションで処理の初期化や準備(たとえばコンポーネントの作成やイベントハンドラの登録)を行い、アクティビティ中にメインの処理を実行し、退場アクションでデータの破棄や後片付けの処理(タイマーやイベントハンドラの解除など)を行うパターンがよく見られます。

コンポジット状態

疑似状態と終了状態を除いて、状態はその内部に子の状態を持つことができます。入れ子の外側の状態をコンポジット(複合)状態と呼び、内側の状態をサブ状態と呼びます。コンポジット状態は複数のサブ状態を持つことができ、さらにサブ状態をコンポジット状態とすることもできます。単純状態とは内部にサブ要素をいっさい持たない(階層が存在しない)状態のことです。コンポジット状態の内部はステートマシンの基本構成と同じく開始疑似状態と終了状態(省略されることもある)が配置され、コンポジット状態がアクティブのときサブ状態は多くてもひとつだけがアクティブになります。コンポジット状態を利用するメリットは、状態を階層的に構成できる点です。もしマシン直下にあらゆる状態や遷移を詰め込もうとするならば、状態の数が少ないうちは問題ないですが、設計が大規模化してくると同じ階層に無数の状態や遷移がひしめき合うことになり、ステートマシン図全体のフローが分かりにくくなってしまいます。コンポジット状態はそうした問題を解決します。たとえば、ある電気機器のステートマシン図が具体的な単純状態「保温中」と「加熱中」を持つとします。また、その他に同じ階層に「電源OFF」の単純状態があるとします。そして、「保温中」と「加熱中」はそれぞれ別々に「電源OFF」への遷移を持つとします。ここで、仮に「動作中」というコンポジット状態を作成し、この2つの状態をそのサブ状態に再配置してみるとどうなるでしょうか。「電源OFF」からの遷移は「動作中」への一本のみとなり、マシン直下の状態数もひとつ減少しました。これがより大規模の設計であれば、その効果はもっと大きくなるはずです。このようにコンポジット状態を使うことで、複雑で規模の大きい図の設計にも耐えうるようになるのです。

コンポジット状態には単純状態と異なる特殊な遷移がいくつかあります。使用頻度が高いと思われるのは遷移先のコンポジット状態のサブ状態へ直接遷移するタイプです。

コンポジット状態への遷移は、上の図の上側のように開始疑似状態を経ずにサブ状態への直接遷移が認められます。しかし、下側の図式のようにサブ状態のさらにサブ状態への遷移、つまり2レベル以上下位の状態への直接遷移はできません。反対に、コンポジット状態内部からの外部遷移については、下の図の上側のようにサブ状態から1階層上の状態への直接遷移が描けそうな気がしますが、こちらはUMLの定義では認められないそうです。代わりに遷移がひとつ増えますが、図の下側にあるように「退場点」を経由した遷移に書き換えることで解決できます。

一方でコンポジット状態のように階層化された状態同士では、振る舞いや遷移のタイミングが単純状態同士のそれと異なるので注意が必要です。コンポジット状態がアクティブになるとき、まず自身の入場アクションが子状態のそれより先んじて実行されます。子状態は上位のものから順に入場アクションを実行し、最下位の状態が最後に入場アクションを実行します。反対に、コンポジット状態の退場アクションはすべてのサブ状態より後になります。コンポジット状態が終了あるいはトリガが発生すると、もっとも下位にある状態が最初に退場アクションを実行して非アクティブ化します。その処理がバブルアップしていき、最後にコンポジット状態が退場アクションを実行して非アクティブ化します。入場と退場のときでタイミングが正反対になるのです。また、親状態の遷移は下位の状態への影響力が大きく、下位の状態が何かを実行中であっても上位の状態が遷移に映ると、処理が飛ばされたり中断されることがあります。階層化された状態を設計する際は、そうした特性を把握しておく必要があるでしょう。

領域と直交状態

コンポジット状態に比べると使われることが少ないですが、ひとつの状態内で複数の処理を並列して行いたいとき、直交状態というのを利用できます。上の図はCDプレイヤーの基本的な機能をステートマシン図で表現したものです。点線で区切られた3つのエリアは領域と呼び、それぞれ他と独立した処理を行う仕組みになっています。「電源オン」のコンポジット状態に入ると、それぞれの領域で同時に開始疑似状態がアクティブになり、一番上の領域から「停止中」、「シングル」、「リピートしない」状態へと遷移します。それぞれの領域はあくまで独立し分離されたエリアなので、点線をまたいだ(ここでは上下の)遷移は認められません。そのため、それぞれの領域での遷移が他の領域に影響を与えることがないように設計する必要があります。ここで、一番上の領域を「停止中」状態に固定したままにすると、下2段の状態の組み合わせが「シングル/リピートしない」「シングル/リピートする」「シャッフル/リピートしない」「シャッフル/リピートしない」の4つになるのが分かると思います。「再生中」のパターンを考えると合計8通りの組み合わせができます。実はこの例は直交状態を使わなくてもコンポジット状態に置き換えが可能なのです。ただし、その場合「停止中/シングル/リピートしない」のように機能のミックスされた名前の状態が8つ必要になり、さらにその分の遷移が必要になることからかえって図式が煩雑になってしまいます。このように、直交状態を使用することでシンプルで直感的に把握しやすくなるケースがあるので、条件が合うならば積極的に使っていくべきでしょう。

なお、直交状態は各領域で同時並行して処理を行う仕組みなので、厳密に考えるとプログラミング言語やCPUが並行処理に対応している必要があるのですが、そうした厳密性を求めないかぎりJavaScriptのようなシングルスレッドの言語でも疑似的に直交状態を表現することが可能です。実際に自分が作成したJavaScriptライブラリにも直交状態が用意されています。このライブラリでは直交状態内の領域は配列に追加され、ループ処理で順番に実行される仕組みになっています。

領域は状態とは異なり振る舞いを持ちませんが、入場と退場(アクティブ/非アクティブ)の要素を持ちます。直交状態が入場すると、属する領域が入場(アクティブ化)し、その後に領域内の開始疑似状態ないしサブ状態の入場となります。直交状態が退場するタイミングでは、コンポジット状態のときと同様に正反対の動作をします。また、直交状態の終了について注意する点があります。外部のトリガなどで直交状態を起点とする遷移が起きると、内部のアクティブな領域とサブ状態は状況にかかわらずすべて強制的に完了となります。次に内部から終了するパターンについてです。複数あるうちのひとつの領域が終了状態に達するか完了したとしても、その他にまだアクティブな領域が残っていると、親状態の直交状態は完了しません。直下の領域がすべて完了したとき、ようやく親状態が完了したと見なされ直交状態は完了遷移に移ります。前述のコンポジット状態もまたひとつの領域を含む直交状態とみなすことができるでしょう。ただし、こちらは領域をせいぜいひとつしか持たないので、領域内でサブ状態が終了状態に遷移すると即座にコンポジット状態は完了となります。

サブマシンと入場点・退場点

ステートマシンの設計が大規模になると、図式自体が比例して大規模になり見通しが悪くなります。その対策として、ステートマシンをひとまとまりのコンポーネントとして扱い、別のステートマシンの設計に組み込む方法があります。この再利用可能なものとして定義されたステートマシンをサブマシン状態と呼びます。コンポジット状態も考え方としては同じなのですが、サブマシン状態は文字通りマシンであり、ひとつの完結したシステムである点で異なります。サブマシン状態はコンポジット状態と同じ図形に、メガネのようなアイコンを加えた形で表されます。これを通常の状態と同じように扱うことで、見通しを損なうことなく大規模なステートマシン図を描けるようになります。

ところで、サブマシン状態に遷移させるとき、条件によっては開始疑似状態ではなく、内部の別のサブ状態へ直接遷移させたいときがあると思います。このとき、サブマシン状態の図形は上図のように内部の仕組みが隠蔽された状態になっているため、サブ状態への直接遷移をうまく記述できません。そういうときは、次の図のように入場点(Entry point)を明示して記述します。入場点は後述の退場点と共にサブマシン状態やコンポジット状態との接続点(疑似状態)として機能します。これらの接続点を扱う場合、当然ながらサブマシン状態の詳細が記述されている図面に別途、接続点に対応する入場点や退場点を記述する必要があります。入場点は白い丸として表され、下の図では「マップを歩く」状態からの遷移先に指定されています。この入場点がアクティブになると、「戦闘する」サブマシン状態が起動してこのサブマシン状態下の処理が始まります。サブマシン状態内部では、外側の入場点に対応する入場点がアクティブになり、開始疑似状態とは別ルートの遷移を開始します。元のステートマシン図の処理に戻るのは、サブマシン状態が内部で終了するか完了したときです。サブマシン状態からの遷移は、通常の(完了)遷移の他に退場点(Exit point)を記述するケースがあります。退場点は×印の書かれた丸で描かれ、サブマシン状態から複数の遷移を記述する必要がある際に用いられます。

その他、サブマシン状態を使用するメリットに、オブジェクト指向におけるカプセル化の役割を果たしている点があります。ステートマシンにサブマシン状態を組み込むとき、その接続点のみ参照すればよいのでコンポーネントとしての独立性が保たれ、保守運用が容易になります。

ちなみにここで解説した入場点と退場点は、サブマシン状態の記述に限定したものではなく、コンポジット状態や直交状態に対しても適用できます。ある状態に対して複数の入場・退場箇所を設定する必要があるときこれらの疑似状態を使用して記述します。

ステートマシン図にはその他に説明するべき重要な疑似状態がありますが、記事が長くなったこともあって次回以降にできればと思います。Webの日本語サイトを見ているとステートマシン図に関する記事は、情報量が多くはなく認知度もまだ高いとはいえないので、ぜひプログラミングでアプリやゲームを制作する際に参考にしていただきたいです。ステートマシンをWebアプリケーションないしゲームのシステムに組み込むことで、設計の幅や可能性が広がると思います。

 - JavaScript/Ajax, ゲーム , ,