feature image

2016年12月20日 | ブログ記事

状態遷移と状態の排除

phi16です。traP Advent Calend a r 20日目です。技術系の話をします。
このへんにコードが諸々置いてあるので並行して読むとよいとおもいます。
完成品はこれです。

はじめに

プログラムを書いてて起きるバグの多くは状態に起因するものである。勿論状態という概念を持たないチューリング完全なモデルは存在するが、現実として、特にゲームを作る上で状態を持たないことは不可能と言える。そこで、素直に書いた手続き型のコードから「如何に状態を削減するか」、「状態というものを隠蔽するか」、ということを考えたい。

今回はJavaScriptとHTML5 Canvasを使ってアクションゲームのモデルを作る。内容としては"キャラが動くだけ"、である。しかしその中にも多くの状態が隠れているのである。

手続き型のコード

状況設定[c152383]


画面はある範囲の矩形、そのなかでキャラクタ(青色の矩形)がプレイヤーの操作によって動き回るもの、とする。この時点ではプレイヤーに対して動きの定義などは何もないので勿論「状態」は存在しない。
プレイヤーの動作は次の2つの関数によって定義される。


function execute(draw){
  draw(width/2-25,height-100,50,100);
}
function input(e,pressing){
  console.log(pressing,e);
}

executeは毎フレーム呼び出される関数、inputはイベントとdown/upのbooleanを受け取る、キーボード入力のハンドラである。現在は見ての通り固定位置に矩形を描画するのみ、入力はログとして流すだけ、となっている。

慣性モデル[445c333]

ここでよくある速度と加速度、摩擦によるモデルを導入する。


const cw = 50, ch = 100;
var x = width/2-cw/2, y = height/2, vx = 0, vy = 0;
function execute(draw){
  draw(x,y,cw,ch);
  if(key.left)vx-=3;
  if(key.right)vx+=3;
  vx *= 0.8;
  vy += 0.4;
  x += vx;
  y += vy;
  if(y > height-ch){
    vy = 0;
    y = height-ch;
  }
}

キーを押すことで加速度を直接与え、摩擦によってx軸方向は減衰し、重力によってy軸方向は加速する。ついでに地面にめり込まないようにチェックする。だいたい一般的なコードだと思われる。
キーチェックは次の機構を採用した :


var key = {left:false,down:false,up:false,right:false};
function input(e,pressing){
  if(e.keyCode==37)key.left = pressing;
  if(e.keyCode==38)key.up = pressing;
  if(e.keyCode==39)key.right = pressing;
  if(e.keyCode==40)key.down = pressing;
}

イベントが飛んでくるたびにkeyのメンバが書き換わる。今のところ問題は無いのでこれで進めていく。ここまでが基礎である。

ジャンプ[a103364]

平面を動いているだけでは面白くない。上キーによるジャンプを導入しよう。地面に居ないとジャンプできないはずなので、「地面に居るならジャンプできる」という条件を与えたい。地面に居るかの判定は例えばy > height-chでできるかもしれないが、この式が「地面に居ること」を表していることは明らかではない。そこでjumpingという、「ジャンプ中」であることを表す状態を用意しよう。


var jumping = false;
function execute(draw){
  //...
  if(!jumping){
    if(key.left)vx-=3;
    if(key.right)vx+=3;
    vx *= 0.8;
  }else vx *= 0.99;
  //...
  if(y > height-ch){
    //...
    jumping = false;
  }
  //...
  if(key.up && !jumping){
    vy = -15;
    jumping = true;
  }
  if(x < 0)x = 0, vx = 0;
  if(x > width-cw)x = width-cw, vx = 0;
}

上キーを押したときにジャンプしていなければ上方向の速度を与える = 事実上のジャンプである。このとき同時にジャンプ中であるフラグを立てる。また、飛んでいる間は左右操作ができないようにし、摩擦も極小とした。
またキャラが左右範囲外に出ないようにチェックを追加した。地面に到着したらジャンプ中のフラグを下ろす。これで一応ジャンプはできるようになったことになる。

壁キック[7187373]

こんどは壁に接しているときに上キーを押したら壁キックができるようにしてみよう。方針としては、「壁に接している」ことを表す状態onwallを用意し、「壁に接しているとき」にジャンプの動作をさせる。


var onwall = false;
function execute(draw){
  //...
  if(y > height-ch){
    //...
    onwall = false;
  }
  //...
  if(key.up){
    //...
    if(onwall){
      vy = -15;
      jumping = true;
      if(x < width/2)vx = 10;
      else vx = -10;
      onwall = false;
    }
  }
  if(x < 0)x = 0, vx = 0, onwall = jumping;
  if(x > width-cw)x = width-cw, vx = 0, onwall = jumping;
}

壁に接しているとき、かつ、ジャンプ中のときのみに「壁に接している」と解釈することにした。これで地面を移動していって壁に接して上キーを押したら壁キックになる、などの奇妙な動作にはならないはずである。
しかしこのバージョンでは少し問題がある : 上キーを押したままジャンプ→壁に接地すると、その場で壁キックしてしまう。もう一度ちゃんと上キーを押させるために修正しよう。

壁キックの修正とスライディング[0a85aed]

そこでまた状態として、「壁キック可能」であることを表現するwallkickableを導入しよう。「ジャンプした後にまた指を離せばOK」である。コードは省略するが確かに望んだ動作が得られる。
ついでに壁につかまったようなエフェクトとして、壁に接している且つ壁の方向にキーを押しているなら落下速度を制限する、ということにしてみた。


if(onwall){
  if(x < width/2 && key.left || x > width/2 && key.right){
    vy = Math.min(vy,3.0);
  }
}

なるほど動作しそうである。まだ状態を管理しきれているだろうか?

二段ジャンプ[3276d0b]

やはり二段ジャンプはやってみたい。どうすればいいかというと、1度目のジャンプと2度目のジャンプを区別できれば良い。doublejumpという状態を導入しよう。また、このままだと壁キック時と同様に上キーを押したままのとき(これは常である)に反応してしまうので、wallkickableを一般のjumpableに改名し、二段ジャンプ時にも使えるようにしてみよう。


if(key.up){
  if(!jumping){
    vy = -15;
    jumping = true;
    doublejump = true;
    jumpable = false;
  }
  if(onwall && jumpable){
    vy = -15;
    if(x < width/2)vx = 10;
    else vx = -10;
    onwall = false;
    jumping = true;
    doublejump = true;
    jumpable = false;
  }
  if(doublejump && jumpable){
    vy = -15;
    jumping = true;
    doublejump = false;
    jumpable = false;
  }
}
if(!key.up)jumpable = true;

なるほど動作する。

さて、ここまでが舞台設定である。これは読みやすいコードだろうか。

状態と挙動の立場

現在キャラの状態として陽に管理する必要のあるものはBoolean値を持つjumping,onwall,jumpable,doublejumpの4つである。全部で16通り。ちなみにこのコードは私がリファクタリングを考えずに勘とノリで組んだものなので割りとありうるものだと思う。
jumpableは完全にキーに依存した状態なのであとにすると、少し考えればキャラに必要なのは4通りの状態のみであることがわかる : 地面、ジャンプ1段目、ジャンプ2段目、壁接地時。
とりあえずまとめてみることにしてみようか。

switch[52b9a29]


if(key.up){
  switch(state){
  case 0:
    vy = -15;
    state = 1;
    jumpable = false;
    break;
  case 1:
    if(jumpable){
      vy = -15;
      state = 2;
      jumpable = false;
    }
    break;
  case 2:
    break;
  case 3:
    if(jumpable){
      vy = -15;
      if(x < width/2)vx = 10;
      else vx = -10;
      state = 1;
      jumpable = false;
    }
    break;
  }
}

こうなったのではないか?成程状態を管理する変数はstate1つだけになった。しかしソースコードは逆にわかりにくくなった部分もあるように見える。状態の本質は別にintではない。
文字列にしたら解決する問題だろうか?確かにソースコードの見た目はよくなるかもしれないが明らかに無駄な処理が走ることになる。状態割当を変数に代入しておいたところで結局「状態に数値を割り当てる必要がある」のは変わらない。

結局状態とはなんなのだろうか?状態によって挙動が変化する。状態とそれに伴う挙動はほぼ一対一対応する。ならば、「状態とは挙動ではないか」?

Function as State[8b85540]


if(key.up){
  current();
}

シンプルである。勿論currentが問題なのであるが。


var current;
function ground(){
  vy = -15;
  current = jump1;
  jumpable = false;
}
function jump1(){
  if(jumpable){
    vy = -15;
    current = jump2;
    jumpable = false;
  }
}
function jump2(){
}
function wall(){
  if(jumpable){
    vy = -15;
    if(x < width/2)vx = 10;
    else vx = -10;
    current = jump1;
    jumpable = false;
  }
}
current = ground;

このように、「挙動」そのものとして状態を管理することは何も問題が無い。むしろ余分なswitchが消え、各状態における挙動を本筋から分離でき、またあとから状態を追加することも容易と、良いことが多いように見える。
ラムダ式の使い所が無いという人は多分値の管理が旧型なだけである。今まで疑問を持たずに書いていた状態のコードを見直せば何か思いつくことでもあるのではないか。とはいえ勿論これは私個人の考えであるので、各々自分が最高だと思った状態管理をしていけば良いとは思う。

全ての挙動を状態に[af3a960]

先程のコードでは上キーを押した部分の挙動のみを分離した。しかし他にも状態に依存する処理は複数ある。また、今回はJavaScriptだからよかったもののcurrent == groundのようなコードは他の言語では正常に作動しない可能性が高い。そこで、「挙動全て」を分離してみよう。共通部分が多いので、差分を指定することで挙動を構成できると良いだろう。


function basis(isGround,isWall,jump){
  return function(){
    if(key.left)vx -= isGround ? 3 : 0.001;
    if(key.right)vx += isGround ? 3 : 0.001;
    vx *= isGround ? 0.8 : 0.99;
    vy += 0.8;
    if(isWall){
      if(x < width/2 && key.left || x > width/2 && key.right){
        vy = Math.min(vy,3.0);
      }
    }
    x += vx;
    y += vy;
    if(y > height-ch){
      vy = 0;
      y = height-ch;
      current = ground;
    }
    if(key.up){
      jump();
    }
    if(x < 0 && vx < 0){
      x = 0, vx = 0;
      if(!isGround)current = wall;
    }
    if(x > width-cw && vx > 0){
      x = width-cw, vx = 0;
      if(!isGround)current = wall;
    }
  };
}

こんな感じでテンプレを作っておく。Boolean2つと、jumpの挙動を指定すれば挙動ができる。



ground = basis(true,false,function(){
  vy = -15;
  current = jump1;
  jumpable = false;
});
jump1 = basis(false,false,function(){
  if(jumpable){
    vy = -15;
    current = jump2;
    jumpable = false;
  }
});
jump2 = basis(false,false,function(){
});
wall = basis(false,true,function(){
  if(jumpable){
    vy = -15;
    if(x < width/2)vx = 10;
    else vx = -10;
    current = jump1;
    jumpable = false;
  }
});

current = ground;

function execute(draw){
  draw(x,y,cw,ch);
  current();
  if(!key.up)jumpable = true;
}

これで状態管理の重要な部分は完全に分離できた。basisに従って状態を構築するもよし、最初から全く違う動作を生み出すような挙動・状態を組むもよし、である。basis側では「地面に接地したとき」「壁に接地したとき」に強制的に状態が書き換わる処理が入っているが、これはいわば外部イベントだと解釈すれば違和感は無いだろう。
メインの状態部分を読んでみれば、「groundのときはジャンプするとjump1に」「jump1のときはジャンプするとjump2に」「jump2ではジャンプできない」「wallのときはジャンプするとjump1に」という、まるで状態遷移系そのもののような記述になっている。
これはこれで1つの完成形だろうか。状態遷移が発生するのは避けられないわけだが、逆に言えば状態遷移だけを書いたようなコードになっているという点でほぼ十分とも言える。
前はこれに似た仕組みをシーン管理に用いていた。使いやすいとは言えなかったがシーン間の分離と状態遷移アニメーションの実装が容易だったのでその頃は満足していた。

連続した状態

現在の状態遷移図は次のような感じである。

青矢印がメインの状態遷移、緑が「地面に着地」、橙が「壁に接地」を表現している。
さて、私達にとって、状態遷移というのはこのように離散的なものだろうか?二段ジャンプに至るまでには必ず地面→ジャンプ→二段ジャンプという流れが存在する。アクションゲーム以外でも、例えばストーリーの流れはただ離散的なグラフなわけではなく連続した状況のまとまりとなるだろうし、ボードゲームの処理は人それぞれごとに順番を持って進んでいく。つまり、状態遷移には「流れ」があるのである。この流れをソースコードで表現できないだろうか。

そこで、ECMAScript6 Generatorを使う。Generatorとはとりあえず「中断可能な関数」である。これを「連続した状態」として扱ってみようということを考えるのである。
まず今の状況を整理しよう。

そこで次のモデルを考える。

これに加え、「inputで受け取った入力は直接触るのではなくkeyHandlerを通して受理させる」ということを行う。
順番に見ていく。

Generator[23b3d61+α]


var isGround = true, isWall = false;
function step(){
  if(key.left)vx -= isGround ? 3 : 0.001;
  if(key.right)vx += isGround ? 3 : 0.001;
  vx *= isGround ? 0.8 : 0.99;
  vy += 0.8;
  if(isWall){
    if(x < width/2 && key.left || x > width/2 && key.right){
      vy = Math.min(vy,3.0);
    }
  }
  x += vx;
  y += vy;
  if(y > height-ch){
    vy = 0;
    y = height-ch;
    setState(ground);
  }
  if(x < 0 && vx < 0){
    x = 0, vx = 0;
    if(!isGround)setState(wall);
  }
  if(x > width-cw && vx > 0){
    x = width-cw, vx = 0;
    if(!isGround)setState(wall);
  }
}

function execute(draw){
  draw(x,y,cw,ch);
  step();
}

ジャンプ以外の処理はここで行われる。今までは状態変更をcurrent変数への代入で行っていたが、今回はsetState関数を介すこととする。


var current;
function setState(g){
  current = g();
  current.next();
}

function* ground(){
  isGround = true;
  isWall = false;
  resetJumps();
  yield;
  vy = -15;
  setState(jumping);
}
function* jumping(){
  isGround = false;
  isWall = false;
  yield;
  vy = -15;
}
function* wall(){
  isGround = false;
  isWall = true;
  yield;
  vy = -15;
  if(x < width/2)vx = 10;
  else vx = -10;
  setState(jumping);
}

setState(ground);

分離された状態としては、この通りground,jumping,wallの3つとなった。ground/wall共にjumpingの先頭に飛ぶ可能性があるため最低この3つに分離する必要がある。それぞれの状態は最初にisGround/isWallの設定をし、適宜ジャンプの動作を定義するといったところである。
groundでは最初にresetJumps関数を呼ぶ。これは地面に着いているときのジャンプは上キーを押しっぱなしでも受理するようにするため、キー入力側の状態を戻すという都合による。
yieldはその関数を中断する命令である。次に実行されるのは(後に出てくる)current.next()の呼び出しのときであり、これは上キーを押したときに呼ばれることになる。つまりはyieldの箇所で上キーが押されるまで待機し、そのあとジャンプして状態遷移する、というコードがそのまま書いてあるわけである。うれしい。
jumpingでもほぼ同様である。yieldしたあとジャンプしてGenerator関数を抜ける。これによって上キーを押しても反応できなくなるため、ジャンプが最大2回に制限される。例えばここでwhile(1)yield,vy=-15;などと書けば無限回ジャンプが実現できる。


function* upKeyHandler(){
  var x;
  while(1){
    while(x = yield, !x);
    current.next();
    while(x = yield, x);
  }
}
var upKey;
function resetJumps(){
  upKey = upKeyHandler();
  upKey.next();
}
resetJumps();

function input(e,pressing){
  //...
  if(e.keyCode==38){
    upKey.next(pressing);
  }
}

ちょっとおもしろいのがこのキー入力機構である。上キー入力が来るたびにupKeyHandlerでyieldに値が入る。while(x = yield, !x);はx = true、つまり上キーが押されるまで無限ループする命令である。結果、最初に上キーが押されたらcurrent.next()が呼び出され、先程までのジャンプの動作が実現される。ちなみに地面で上キー押しっぱなしで動くのはキー長押しをするとinput関数がほぼ毎フレーム呼ばれるからである。
その後while(x = yield, x);によってキーが離れるまで待機され、またループに突入する。結果として期待された動作をする。

これでGeneratorを使った状態遷移機構を実現できた。最終的に状態遷移に関わるのはground/jumping/wallの3つの関数であり、それぞれまとまった記述が出来ているように見える。全体として残った状態はisGround, isWall, currentの3つとupKeyだが、前者2つはcurrentのみによって操作され、またupKeyは一度作れば今後関わることはない。実質currentに状態の機能を殆ど押し込めたことになったわけである。
以上、「状態の削減と隠蔽」ということで手続き型コードから見える状態を減らしていく話であった。

終わり

というわけでGeneratorの宣伝でした。最近rogyでもどこでもGeneratorの宣伝ばかりしていますね・・・ 理由は単純で私が最近ようやく有用性を理解したからということなんですけど。アニメーションにも使ったしゲームの挙動全てをGeneratorで管理するみたいなこともやってみました。結構昔からあるはずの概念なのに今まで使ってこなかったのが悔やまれるという感じです。

勿論コードの書き方は人それぞれです。私は今はGeneratorたのしい!って言ってますけどそのうちなんか別の概念に手を出すかもしれません。とりあえず今の知見として手続き型から準関数型、そしてGeneratorベースへの流れをまとめた次第でした。

まぁプログラミングの概念はめっちゃいっぱいあるので、まだまだ勉強することはあるんだろうなぁという感じ。当分はMonadで済みそうですけど。

ちなみに今回の記事のコードはそこまでGeneratorの構造に適した例ではないとは思います。ボードゲームみたいなのだと本当に連続した状態が多いので綺麗にまとまるんですけどね・・・ アクションゲームだとどうなるかなぁという考えもあって適当なコードを書いた次第です。まぁ妥当な結果という感じですね、どうしてもわかりにくい部分は出てくるとは思います。

あ、そういえば最初に貼ったリンク先では青四角がすごいぽよぽよっとしてるとおもうんですけど。特に解説はしないのでソースでも読んでください。なんかゲームっぽくなってるけどただの適当な思いつきです。

これもこれで思うところなんですけどね。私はキャラの絵を描けないのでアクションするキャラは四角にするしかないのです。でも、だとしても、こうやって大きさを制御するだけでも生気を感じられる気がしませんか?むしろこのテクニックは絵に対して有効なのかもしれないですけど。
ゲームの動きというのはrefineできる場所はいくらでもあるんだなぁと。今回のは普通の四角だと明らかにinteractionがなくて寂しいのでさすがに気づきますが、もっと気づかないようなところで何らかの動きを導入したほうが自然に見える事例はあるだろうなとおもいます、アクション系は特に。既存のゲームって本当に参考になるんですよね。
ゲームの改善点ってほんといっぱいあるので その点でも早く完成させることが大事なんでしょうけど まぁ むずかしいですね・・・ がんばっていきましょう。

長いあとがきになってしまいましたが終わりです。明日はcrotkazさん、naosanさん、parumaさんの記事です。

phi16 icon
この記事を書いた人
phi16

Haskellとかレンダリングとか数学とか。

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】 feature image
2018年11月3日
ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】
Azon icon Azon
2021年5月19日
CPCTF2021を実現させたスコアサーバー
xxpoxx icon xxpoxx
2019年4月22日
アセンブリを読んでみよう【新歓ブログリレー2019 45日目】
eiya icon eiya
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2017年11月17日
そばやのワク☆ワク流体シミュレーション~MPS編~
sobaya007 icon sobaya007
2021年4月26日
CPCTF2021 作問者writeup by zassou
zassou icon zassou
記事一覧 タグ一覧 Google アナリティクスについて