[Unity] ComputeShaderでモブを動かす【その５：衝突予測・リベンジ】

# 経緯

コンピュートシェーダー(ComputeShader)を学ぶため、自動車を動かす交通シミュレーターもどきを作ってみようと思いました。個々の自動車がそれぞれ衝突を回避しつつ適切な経路で目的地に移動できるようになるのが目標です。
前回 [衝突予測と減速を組み込みました](https://qiita.com/Shinoda_Naoki/items/d2279f087ae104e2f291) が、隣接する車線の車にも反応してしまってうまくいきませんでした。

結局の所、危険運転をする車がいない前提なら同じ車線だけ見てればいいはずなので、今回よりロジックを単純化した衝突予測に挑戦してみました。
なお、コードはいままでの分も含め全て[Github](https://github.com/ShinodaNaoki/learnComputeShader)にあります。
![road06_gpu_run.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/75035/ac1b1fb4-1841-b07f-5780-7648f0167ead.gif)

◀【[その4：衝突予測・失敗談](https://qiita.com/Shinoda_Naoki/items/d2279f087ae104e2f291)】
【[その６：二次元スレッド・複カーネル化／効果なし](https://qiita.com/Shinoda_Naoki/items/9c244afae590fd5a9fb3)】▶

# C#側実装

## 構造体の変更

現在の車線情報をもたせるため動的情報構造体に lane プロパティを追加しました。
静的情報は Car03s をそのまま使います。

```csharp:CarTemplate04.cs
/// <summary>
/// 車の構造体
/// </summary>
public struct Car04d : ICarDynamicInfo
{
    public Vector2 pos { get; set; }
    public Vector2 direction { get; set; }
    public float velocity { get; set; }
    public int lane { get; set; }
    public int colider { get; set; }

    public override string ToString()
    {
        return string.Format("[{0},{5}({1:0.0},{2:0.0})>>({3:0.0},{4:0.0})]", 
            typeof(Car04d).Name, 
            pos.x, pos.y, 
            direction.x * velocity, direction.y * velocity,
            lane
        );
    }
}
```

## コントローラー
【[CarController05の全体はこちら](https://github.com/ShinodaNaoki/learnComputeShader/blob/master/Assets/Scripts/CarsController05.cs)】

車を追加する部分に lane をセットする行を追加しました。

```csharp：CarsController05.cs
    private void OnEachScan(Car[] cars)
    {
        if (factory.ActiveCars >= MAX_CARS) return;

        var entries = roadPlane.EntryPoints;

        // 車を追加する
        int index = Random.Range(0, entries.Count);
        int f;
        if( _lastEntries.TryGetValue(index, out f) && Time.frameCount - f < MIN_INTERVAL_FRAMES)
        { // 最初から衝突するのを避けるため、一定フレーム数内に車が入ったばかりなら次の機会を待つ
            return; 
        }

        var entry = entries[index];
        var car = factory.CreateRandomType(entry.pos, entry.dir);
        var car_d = car.Dynamic;
        car_d.lane = index;
        car.Dynamic = car_d;
        _lastEntries[index] = Time.frameCount;
        factory.ApplyData();
    }
```

# 衝突回避アルゴリズム(シェーダー側)
【[全体のソースはこちら](https://github.com/ShinodaNaoki/learnComputeShader/blob/master/Assets/Shader/DrivingComputeShader05.compute)】

基本的な考え方は[前回](https://qiita.com/Shinoda_Naoki/items/d2279f087ae104e2f291#%E8%A1%9D%E7%AA%81%E5%9B%9E%E9%81%BF%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%B7%E3%82%A7%E3%83%BC%E3%83%80%E3%83%BC%E5%81%B4)と同じですが、同じ車線の車に対してのみ行います。

```GLSL
  // 別車線は無視
  if (carD1.lane != carD2.lane)
  {
      return;
  }
```

背後から接近してくるもの、相対速度が小さいものは早期リターン。
同じ車線なら向きは同じと仮定できるので、相対速度はスカラー計算でOK。

```GLSL
  // 相対位置ベクトル
  float2 diffPos = carD2.pos - carD1.pos;
  // 背後から接近してくるものは回避しない（相手任せ）
  if (dot2d(carD1.dir, diffPos) <= 0) return;

  // 相対速度
  float diffVel = (carD1.velocity - carD2.velocity) * 0.28;
  if(diffVel < 0.00001){
    return; // 接近していない
  }
```

衝突時刻を予想して、遠い未来なら無視

```GLSL
  float absPos = length(diffPos);
  float countAssume = absPos / diffVel;
  if(countAssume > 100000){
    return; // 遠い未来過ぎるので無視
  }
```

車のサイズと速度を考慮した停止距離を計算します。
車の向きは同じはずなので、衝突距離は size.z だけから簡易的に計算できます。

```GLSL
  // 二つの車のサイズを考慮した距離を求める
  // 同一車線なので基本的に両車の長さの半分を足したもの
  CarS carS1 = CarsStatic[id1];
  CarS carS2 = CarsStatic[id2];
  float distance = (carS1.size.z + carS2.size.z) * 0.5; 
  // どちらかが高速で移動しているなら停止距離には余裕を持つ
  distance += max(carD1.velocity, carD2.velocity) * 0.28f;
```

停止距離で補正した衝突予想時刻を改めて計算、最小値とその時の相手の車のIDを保持します。

```GLSL
  float t = max(0, (absPos - distance) / diffVel);
  // このままだと近い将来衝突しそう
  if(t > timeMin){
    return; // もっと近い相手が既にいる
  }

  // 最小値更新
  timeMin = t;
  idMin = id2;
```

衝突予測に基づく加減速処理はこんな感じ

```GLSL
 if(idMin == id.x) { // 衝突の可能性の高い車はない
    if(carD.velocity < carS.idealVelocity) {
      carD.velocity = min(carD.velocity + carS.mobility, carS.idealVelocity);
    }
  }
  else {
    if(carD.velocity > 0) {
      carD.velocity = max(0,  carD.velocity - carS.mobility * 2.0);
      if( length(CarsDynamic[idMin].pos - carD.pos) < 5 ){
        carD.velocity = 0;
      }
    }
  }
```

## おまけのC#版

だいぶロジックが簡略化されたとは言え、まだまだ脳内デバッグでは辛いので、今回も C# で動作確認してから移植しました。

```csharp:CarsController05.driving.cs
    private void FindMostDangerCar(Car[] cars, int id1, int id2, ref float timeMin, ref int idMin)
    {
        if (timeMin <= 0) return; // 時すでに遅し

        var carD1 = cars[id1].Dynamic;
        var carD2 = cars[id2].Dynamic;
        // 別車線は無視
        if (carD1.lane != carD2.lane)
        {
            return;
        }

        // 相対位置ベクトル
        Vector2 diffPos = carD2.pos - carD1.pos;

        // 背後から接近してくるものは回避しない（相手任せ）
        if(dot2d(carD1.direction, diffPos) <= 0) return;

        // 相対速度ベクトル
        float diffVel = (carD1.velocity - carD2.velocity) * 0.28f;
        if (diffVel < 0.001f) return; // 接近していない

        float absPos = diffPos.magnitude;
        float countAssume = absPos / diffVel;
        if (countAssume > 100000f)
        {
            return; // 遠い未来過ぎるので無視
        }

        // 二つの車のサイズを考慮した距離を求める
        // 同一車線なので基本的に両車の長さの半分を足したもの
        var carS1 = cars[id1].Static;
        var carS2 = cars[id2].Static;
        float distance = (carS1.size.z + carS2.size.z) * 0.5f;
        // どちらかが高速で移動しているなら停止距離には余裕を持つ
        distance += Mathf.Max(carD1.velocity, carD2.velocity) * 0.28f;

        float t = Mathf.Max(0, (absPos - distance) / diffVel);
        // このままだと近い将来衝突しそう
        if (t > timeMin)
        {
            return; // もっと近い相手が既にいる
        }        

        // 最小値更新
        timeMin = t;
        idMin = id2;
        if(carD1.direction.y >= 0)
        Debug.Log(
            string.Format("<color='grey'>{0}<->{1}:\n</color> dPos={2:0.0}, dst={3:0.0}, dV={4:0.0} (t={5:0.0})",
                DebugStr(id1, cars[id1]), DebugStr(id2, cars[id2]), absPos, distance, diffVel, t));

    }

```
ファイル全体のソースは[こちら](https://github.com/ShinodaNaoki/learnComputeShader/blob/master/Assets/Scripts/CarsController05.driving.cs)

# 結果
今回はうまくいきました。
車は色ごとに違う速度になっていて、 **赤100>青90>白80>水色=黄70>緑60** に設定してます。
![road06_gpu_run.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/75035/ac1b1fb4-1841-b07f-5780-7648f0167ead.gif)
減速が効いてなければ赤や青はすぐに緑に追突するはずですが、全体の車の流れがおおむね緑に合わせた速度に落ち着いています。

しかし若干重い気がしますね。次はパフォーマンスアップを期待して、（`[numthreads(8,8,1)]` みたいな）二次元スレッドでマルチパスに挑戦してみたいと思います。