☃️

Celeste and TowerFall Physics 抄訳と考察

2022/06/18に公開

この記事は Celeste の制作者 Maddy Thorson 氏が公開している、ゲームにおける物理エンジンの実装について述べた記事の抄訳です（元記事）。
自身の勉強のために訳して考察を付記しましたが、折角ですので共有させて頂くことにしました。

TowerFall および Celeste における当たり判定の仕組みについて、今も多くの質問が寄せられています。実は非常にシンプルな実装であり、これは私がおよそ10年間、タイルベースのゲームを作り続けて来て、ようやくたどり着いたものです。以前私は、 GameMaker 向けにこの当たり判定の仕組みと基本的に同じコンセプトを扱うエンジンを実装しています。そしてその後、実装をシンプルにし、少しだけ改善しました。また、Celeste や TowerFall のエンジンは C# で書かれており、デリゲートやデータ構造などのような、素敵な仕組みを扱うことができます。画期的ではありませんが、誰かの参考になればと思い、書き留めることにしました。

なおこの投稿は元々 Celeste 制作以前に、 TowerFall に関して書いていたものです。Celeste にも同様に当てはまるので、Celeste しか分からない人にも読めるようテキストを刷新しました。

私たちのゲームにおける物理エンジンは、 Solid （固体）と Actor （演者、行為者）という2つのクラスで制御されます。 Solid は、そのマップにおいて当たり判定をとる地形です。Actor は、プレイヤーや矢、モンスター、宝箱などのような物理オブジェクトです。マップ上の地形と当たり判定を取る必要がある可動物体は全て Actor です。このシステムには、以下のような簡単な制約があります。

全ての当たり判定は、軸並行バウンディングボックス（axis-aligned bounding boxes; AABB）
全ての当たり判定の座標、幅、高さは整数値
Actor と Solid は重ならない（例外あり）
Solid は他の Solid と当たり判定を取らない

Celesteでの例（正確なものでは無い）

赤：Solid
緑：Actor

Actor の基本

Solid は動かないと仮定します。このとき、Actor はどのようにして動き、Solid と重ならないようにしているのでしょうか。Actor は以下のような、非常にシンプルなAPIを持ちます。

public void MoveX(float, Action); 
public void MoveY(float, Action);

この2つのメソッドは、2つの引数を取ります。float 値で動く距離を定め、C# のデリゲートのような Action 型のコールバック関数で Solid と衝突した際の処理を担います。Actor は自身に速度、加速度、重力の概念を一切持ちませんので、全ての Actor を継承するクラスはこれを考慮し、自身の速度を追跡し続け、適切にこの関数へ値を渡します。

ではMoveX関数の中身を見てみましょう。

public void MoveX(float amount, Action onCollide) 
{ 
  xRemainder += amount; 
  int move = Round(xRemainder); // 四捨五入

  // 指定された移動距離が ±0.5 以上
  if (move != 0) 
  { 
    // 今回移動出来ない端数は次回処理に引き継ぐ
    xRemainder -= move; 
    int sign = Sign(move); // 移動方向（ 1 or -1 ）

    // ループ処理で 1px ずつ動かしていく
    while (move != 0) 
    { 
      if (!collideAt(solids, Position + new Vector2(sign, 0)) 
      { 
        // 任意の Solid と衝突しない場合
        Position.X += sign; 
        move -= sign; 
      }
      else
      {
        // 衝突する場合
        if (onCollide != null) 
          onCollide(); 
        break; 
      } 
    } 
  } 
}

最初に、カウンターである remainder へ動く距離を加えます。座標は整数値なので、remainder が 0 でない時のみ動くことができます。

remainder は、いわゆるサブピクセルのようなものだと捉えて良い。

これより動くべき距離が分かったので、1px ずつ移動距離をチェックしていきます。各チェックごとに全ての Solid を検知し、何も無ければ Actor は動きます。衝突した場合は衝突時の処理を呼び出し、ループ処理を中断します。

毎ループで全ての Solid をチェックしているが、これでは最悪 $O(N^m)$ （ $N$ ：Solidの個数、 $m$ ：移動距離）の計算量がかかってしまう。
$m>1$ の際は予め近傍の Solid のみに絞れないだろうか。Solid を保持するデータ構造やアルゴリズム次第では余計な Solid を予め検証対象から外せるのではなかろうか。

他にも、例えば一度の移動距離が長い場合に、段差のような場所は着地場所が本来の想定とはズレてしまいかねない。
移動の速くないゲームでは、このケースは稀であるか、一種の近似として捉えて差し支えなく、横方向に動きたいプレイヤーにとっては都合の良い結果になっているが、果たしてどちらの方が良いか。

では何故、わざわざ衝突時の処理をメソッドに渡すのでしょうか。詳しくは後述しますが、この実装により Actor を継承したクラスでは、衝突時の処理を MoveX と MoveY のそれぞれ異なる挙動をさせることができます。

こうして、（絶対に動かない Solid を想定した場合は） Actor は Solid を貫通せずに動けるのです。

動く Solid への準備

少し厄介になってきました。私は何年も、動く Solid に関する、大量の欠点を持つ実装を見たり書いたりしてきました。私が10代のころのゲームでは、移動するプラットフォームに対する当たり判定は本当にひどいものでした。
最終的には下記の形で解決しました。

public void Move(float, float);

Solid に必要なメソッドはただ一つです。Solid は他の Collider との当たり判定を取らないので衝突時の処理は不要です。
Solid に右へ 30px 動けと命じれば、その先に他の Solid があろうとも構わず動きます。ただし、移動経路にある Actor は Solid と重なってはいけません。

Solid の Move メソッドを見ていく前に、Actor に API をいくらか追加しましょう。

public virtual bool IsRiding(Solid solid); 
public virtual void Squish();

IsRiding は、Solid に特定の Actor が乗っているかをチェックするメソッドです。通常 Actor は Solid の上に接する時に「乗っている」と表現します。virtual 属性を付けているのは、 Actor に応じて「乗っている」という状態を変更する為です。
例（Celeste）：マデリンが Solid に「乗っている」という状態 = マデリンが Solid の上に立つ時 or 側面にしがみついている時

Squish は Actor が2つの Solid に潰された時の振る舞いを決めるメソッドです。デフォルトではそのActorを消滅させます。

超厄介な移動リフト

Solid と Actor が接触すると、 Solid は Actor に対してある2通りの振る舞いをします。運搬と押し出しです。
Actor は Solid に「乗っている」ときは運搬されます。対して、Solid が移動した結果 Actor と重なる、あるいは貫通する場合は、 Solid は Actor を押し出します。注意するべきは、押し出しは運搬より優先されるということです。 Solid が Actor に対して、運搬と押し出しのどちらも実行した場合（斜め上に移動するプラットフォームに乗っている状況など）、その事象は「押し出し」と考えます。

以下が Solid の Move メソッドです。

public void Move(float x, float y) 
{ 
  xRemainder += x; 
  yRemainder += y; 
  int moveX = Round(xRemainder); 
  int moveY = Round(yRemainder); 

  // 移動が発生するか
  if (moveX != 0 || moveY != 0) 
  { 
    // マップ中の全てのActorに対して処理
    // 返り値はactor.IsRiding(this)でtrueなActor
    List riding = GetAllRidingActors(); 
    
    // 自身をActorと衝突しないように設定し、
    // 運搬されるActorがスタックしないよう設定
    Collidable = false;
    
    if (moveX != 0) 
    { 
      // X軸方向への移動をする場合
      xRemainder -= moveX; 
      Position.X += moveX; 
      
      if (moveX > 0) 
      { 
        // 正の方向への移動
        foreach (Actor actor in Level.AllActors) 
        { 
          if (overlapCheck(actor)) 
          { 
            // 重なっていれば右へ押し出す
            actor.MoveX(this.Right - actor.Left, actor.Squish); 
          } 
          else if (riding.Contains(actor)) 
          { 
            // 右へ運搬
            actor.MoveX(moveX, null); 
          } 
        } 
      } 
      else 
      { 
        foreach (Actor actor in Level.AllActors) 
        { 
          if (overlapCheck(actor)) 
          { 
            //Push left 
            actor.MoveX(this.Left — actor.Right, actor.Squish); 
          } 
          else if (riding.Contains(actor)) 
          { 
            //Carry left 
            actor.MoveX(moveX, null); 
          } 
        } 
      } 
    } 
    if (moveY != 0) 
    { 
      //Do y-axis movement 
      … 
    } 
    // 当たり判定を再度有効化
    Collidable = true; 
  } 
}

一度に載せる行数が多いので、いくらかメモを残します。

まずはいつも通り remainder に移動距離を加えます。Solid は Actor と整数値の座標を共有するので、同じ移動システムを共有しなければなりません。

要は引数で渡された float 値をそのまま Actor に使うなよという話です。多分。

次に、その Solid に「乗っている」Actor のリストを作成します。当然そのリストにある Actor は全て運ばれなければなりません。このリストの作成は、マップ上にある全ての Actor を actor.IsRiding( this ) でチェックすれば済みます。なお、これらの点検処理は実際に Solid を動かす前にしなければなりません。先に動かしてしまうと、「乗っている」ことの判定に不整合が生じてしまうからです。

ここも Actor を保持しておくデータ構造を工夫すれば Actor 全てに対して判定をとる必要はないと思われる。

さらに、一時的に Solid の当たり判定をオフにします。Actor を運搬する、あるいは押し出す際に、Actor の Move メソッドを呼び出すことで解決します。Actor が動くときに、それを押し出したり、運搬したりしている Solid を考慮しないためです。

次に、X座標とY座標のいずれも動かすことで、Actor と及ぼし合う影響を解決します。まずは Solid と重なっている、押し出すべき Actor があるかをチェックします。ここで注意するべき点は、 Actor を動かす前に「乗っている」 Actor をチェックし、動かした後にこの押し出しのチェックをします。

Solid と重なっている Actor は、発見され次第その Solid から押し出します。この Actor は Solid が運搬しているか否かに関係なく押し出されます。押し出しは運搬より優先的に処理されるためです。Actor が重なっていない場合、運搬するべき Actor のリストにも含まれていないかどうかをチェックします。さもなくば、その Actor は放置しましょう。

それでは、Actor の押し出しと運搬の違いを見ていきましょう。

押し出された Actor は、指定した移動距離だけ押し出すのではなく、Actor が壁などの表面に密着するように、Solid の移動後の辺と Actor の移動前の辺の間のピクセル数だけ押し出します。

押し出しは Actor の Squish メソッドも使用します。上述しましたが、デフォルトでは Actor を破壊するメソッドです。Solid が Actor を他の Solid へ押し込むことでその処理が呼び出される、というわけです。Solid と Actor が重なることは許されず、Actor が逃げられる場所もないので、その Actor を破壊します。Actor をくねらせるなど、状況によっては処理を変更します。Towerfall やCeleste ではこういったケースを、状況ごとにさまざまな方法で処理しています。

運搬された Actor は衝突した際のコールバック処理を呼ぶことなく、プラットフォームの速度をそのまま得ることが出来ます。Actor は押しつぶされる危険もなく、Actor が壁にぶつかってもなにも起こらないのです。

迂闊な実装だと、横向きに運搬されている状態で壁に衝突すると Actor の Squish 判定を食らってしまうという話です。

これで終わり！この記事があなたにとって良い助けになることを願っています´ `)ﾉ

GitHubで編集を提案

Celesteでの例（正確なものでは無い）

Actor の基本

動く Solid への準備

超厄介な移動リフト

Discussion