A*を用いてゲームつくる

相手よりも先に金のボール(スターのつもり)を3つ獲得するゲームをつくった。自分は左下のキャラで相手は右上のキャラ(unity界のアイドル)。 この敵の移動経路を求めるためにA*という探索アルゴリズムを用いた。今回はA*をメインにメモする。

※unity version 2017.2

A*ってなんぞや

Wikipediaによると

A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。

自分の言葉に置き換えるなら目的地までの最短経路を探すアルゴリズムという感じだろうか

考え方

以下のルーチンを処理する。

1. マス目状の盤面を用意する
2. スタート地点とゴール地点を決める
3. 各マスに推定値(ヒューリスティックコスト)を設定する
4. スタート地点を探索マスとし、探索値を1に初期化する。そして以下の処理をゴールにたどり着くまでループする
   1. 探索マスの周り(今回は上下左右の4マス)に対して以下の処理を行い、探索済みにする
      1. 探索値を設定する
      2. 合計値(探索値+推定値)を算出する
      3. 捜索済みにする
      4. もしこのマスがゴールマスなら、到着したとみなしてループを抜ける
   2. 未探索で捜索済みのマスの中から合計値が最も高いマスを次の探索マスとする
   3. 探索値を+1する

マス目の盤面を用意する

自分のステージを縦横10マスの格子状に区切ると以下のようになる。 真ん中の4つの黒い四角が壁である。

推定値の設定

今回は「ゴールからの距離」を推定値として設定する。ゴールをG、スタートをSとしたとき、以下のように割り振られる。Gを中心に遠くなるほど、値が大きくなる感じやね。 GとSは推定値を割り振っても使わないので割り振っていない。

探索フェイズ

推定値までの実装は自分でも実装出来たけど、探索ルーチンが分からない... なので以下の記事の考え方を参考にコードを書き書き。各マスの捜索時に探索マスを親として持たせることで、ゴールからスタートまでの経路をたどれるようになるのは、まさに目から鱗である。 qiita.com

探索結果、各マスの探索値は以下のような感じになる。「0」は捜索されていないマスである。なんてスマートなんだ...

また、捜索済みマスの合計値は以下のような感じになる

そして、最終的に算出された経路はこちら。ゴールに近づくにつれて値が大きくなってる...!

走ることを強いられる...!

感想

参考になった書籍

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

週末開発として始めたんだけど、このルーチン考えるだけで週末終わってしまった...ムネンナリ

週末はこんなの作りたい#weekendevelop pic.twitter.com/BazjiQyoxy

— ののか (@79onoka) 2018年1月12日

ゲームはwebGLのビルドが成功したらunityroomに置いときたい

お手軽にできない?

こんなの...あるそうですよ...

docs.unity3d.com

ソースコード

トリプルA級汚ソースはこちら。

▶クリックで展開

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStar : MonoBehaviour {
  int massCount;
  Mass[,] massArrays;
  Vector2 goalPos = Vector2.zero; //正規化されたゴール位置
  Vector2 startPos = Vector2.zero; //正規化されたスタート位置

  public void Initialize(int _massCount) {
    massCount = _massCount;
    massArrays = new Mass[massCount, massCount];
  }

  public void MakeMassArrays(int width, int height) {
    var xRange = (float)width/massCount;
    var yRange = (float)height/massCount;
    var yPos = yRange/2f;
    var xPos = xRange/2f;
    for (int y = 0; y < massCount; y++) {
      xPos = xRange/2f;
      for (int x = 0; x < massCount; x++) {
        var center = new Vector3(xPos - width/2f, 0, yPos - height/2f);
        if (StageSystem.HasTile(center, new Vector3(xRange/2f, 0.5f, yRange/2f))) {
          massArrays[y, x] = new Mass(center, xRange, yRange, new Vector2(x, y));
        } else {
          massArrays[y, x] = new Mass();
        }
        xPos += xRange;
      }
      yPos += yRange;
    }
  }

  public List<Vector2> MakePath() {
    Reset();
    var pos = transform.position;
    MarkStartTile(new Vector2(pos.x, pos.z));
    SearchGoal();
    DecideCostToGoal();
    ShowDebug(0);
    Search();
    ShowDebug(1);
    ShowDebug(2);
    ShowPath();

    return GetPath();
  }

  void Reset() {
    for (int y = 0; y < massCount; y++) {
      for (int x = 0; x < massCount; x++) {
        if (!massArrays[y, x].isMass) continue;
        massArrays[y, x].Reset();
      }
    }
  }

  void MarkStartTile(Vector2 charaPos) {
    var pos = Vector2.zero;
    var minDistance = 999999f;
    for (int y = 0; y < massCount; y++) {
      for (int x = 0; x < massCount; x++) {
        if (!massArrays[y, x].isMass) continue;
        var distance = (charaPos - massArrays[y, x].ToVector2()).sqrMagnitude;
        if (distance < minDistance) {
          minDistance = distance;
          pos.Set(x, y);
        }
      }
    }

    massArrays[(int)pos.y, (int)pos.x].SetMassType(MassType.START);
    startPos.Set(pos.x, pos.y);
  }

  void SearchGoal() {
    for (int y = 0; y < massCount; y++) {
      for (int x = 0; x < massCount; x++) {
        if (!massArrays[y, x].isMass) continue;
        if (StageSystem.HasStar(massArrays[y, x].pos, new Vector3(massArrays[y, x].width*4/5f, 5, massArrays[y, x].height*4/5f))) {
          massArrays[y, x].SetMassType(MassType.GOAL);
          goalPos.Set(x, y);
          return; //finish
        }
      }
    }
  }

  void DecideCostToGoal() {
    for (int y = 0; y < massCount; y++) {
      for (int x = 0; x < massCount; x++) {
        if (!massArrays[y, x].isMass) continue;
        if (massArrays[y, x].massType != MassType.CHECK_POINT) continue;        
        var cost = Mathf.RoundToInt((goalPos - new Vector2(x, y)).magnitude);
        massArrays[y, x].Initialize(cost);
      }
    }
  }

  void Search() {
    var y = (int)startPos.y;
    var x = (int)startPos.x;
    var searchCost = 0;

    //massArrays[y, x].Search(startPos); //スタート地点を探索済みにする (親:スタート地点)

    while (true) {
      //周り(上下左右)のマスを発見する
      searchCost++;
      var pos = new Vector2(x, y+1);
      if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].canSearch()) {
        massArrays[(int)pos.y, (int)pos.x].Discover(searchCost, new Vector2(x, y));
      } else if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].massType == MassType.GOAL) {
        break;
      }
      pos = new Vector2(x, y-1);
      if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].canSearch()) {
        massArrays[(int)pos.y, (int)pos.x].Discover(searchCost, new Vector2(x, y));
      } else if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].massType == MassType.GOAL) {
        break;
      }
      pos = new Vector2(x-1, y);
      if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].canSearch()) {
        massArrays[(int)pos.y, (int)pos.x].Discover(searchCost, new Vector2(x, y));
      } else if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].massType == MassType.GOAL) {
        break;
      }
      pos = new Vector2(x+1, y);
      if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].canSearch()) {
        massArrays[(int)pos.y, (int)pos.x].Discover(searchCost, new Vector2(x, y));
      } else if (InField(pos) && massArrays[(int)pos.y, (int)pos.x].massType == MassType.GOAL) {
        break;
      }

      if (searchCost > 10000) {
        Debug.Log("error: don't finish search");
        break;
      }

      //探索する = 次の基点を探す
      var nextSearchPos = GetTileOfMinimumTotalCost();
      //Debug.Log("next:"+nextSearchPos);
      massArrays[(int)nextSearchPos.y, (int)nextSearchPos.x].Search();
      x = (int)nextSearchPos.x;
      y = (int)nextSearchPos.y;
    }

    massArrays[(int)goalPos.y, (int)goalPos.x].Search(massArrays[y, x].address);
  }

  List<Vector2> GetPath() {
    List<Vector2> checkPointList = new List<Vector2>();
    var pos = goalPos;
    var counter = 0;
    var starPos = StageSystem.GetStar().transform.position;
    checkPointList.Add(new Vector2(starPos.x, starPos.z));
    //checkPointList.Add(massArrays[(int)pos.y, (int)pos.x].pos); //ゴール地点
    while (massArrays[(int)pos.y, (int)pos.x].massType != MassType.START) {
      checkPointList.Add(massArrays[(int)pos.y, (int)pos.x].ToVector2());
      pos = massArrays[(int)pos.y, (int)pos.x].parnentPos;
      if (counter++ > 10000)
        break;
    }

    checkPointList.Reverse();//スタート順にソート

    return checkPointList;
  }

  void ShowDebug(int type) {
    var str = "";
    if (type == 0) str += "推定コスト\n";
    else if (type == 1) str += "実コスト\n";
    else if (type == 2) str += "合計コスト\n";
    for (int y = massCount - 1; y >= 0 ; y--) {
      for (int x = 0; x < massCount; x++) {
        if (type == 0) 
          str += massArrays[y, x].costToGoal.ToString("00") +" ";
        else if (type == 1)
          str += massArrays[y, x].costFromStart.ToString("00") +" ";
        else if (type == 2)
          str += massArrays[y, x].totalCost.ToString("00") +" ";
      }
      str +="\n";
    }

    Debug.Log(str);
  }

  void ShowPath() {
    var str = "最短経路\n";

    var pos = goalPos;
    var counter = 0;
    while (massArrays[(int)pos.y, (int)pos.x].massType != MassType.START) {
      str += massArrays[(int)pos.y, (int)pos.x].address +" -> ";
      pos = massArrays[(int)pos.y, (int)pos.x].parnentPos;
      if (counter++ > 10000)
        break;
    }

    Debug.Log(str);
  }

  bool InField(Vector2 pos) {
    return (0 <= (int)pos.x && (int)pos.x < massCount) && (0 <= (int)pos.y && (int)pos.y < massCount);
  }

  Vector2 GetTileOfMinimumTotalCost() {
    var pos = Vector2.zero;
    var minTotalCost = 99999;
    var minHeuristicCost = 99999;
    for (int y = 0; y < massCount; y++) {
      for (int x = 0; x < massCount; x++) {
        if (!massArrays[y, x].isMass) continue;
        if (massArrays[y, x].searched) continue;
        if (!massArrays[y, x].discovered) continue;
        if (massArrays[y, x].massType != MassType.CHECK_POINT) continue;

        var totalCost = massArrays[y, x].totalCost;
        var heuristicCost = massArrays[y, x].costFromStart;

        if (totalCost > minTotalCost) continue;
        if (totalCost == minTotalCost) {
          if (heuristicCost >= minHeuristicCost) continue;
        }

        pos.Set(x, y);
        minTotalCost = totalCost;
        minHeuristicCost = heuristicCost;
      }
    }

    return pos;
  }
}

public class Mass {
  public Vector3 pos {get; private set;}
  public float width;
  public float height;
  public bool isMass {get; private set;}
  public MassType massType {get; private set;}
  public int costToGoal {get; private set;} //推定コスト
  public int costFromStart {get; private set;} //実コスト
  public int totalCost {get; private set;} //= costToGoal + costFromStart
  public bool discovered {get; private set;} //発見したかどうか
  public bool searched {get; private set;} //探索したかどうか
  public Vector2 address; //ポインタ
  public Vector2 parnentPos {get; private set;} //親ポインタ

  public Mass(Vector3 _pos, float _width, float _height, Vector2 _address) {
    isMass = true;
    pos = _pos;
    width = _width;
    height = _height;
    address = _address;
  }

  public Mass() {
    isMass = false;
  }

  public void Reset() {
    SetMassType(MassType.CHECK_POINT);
    costToGoal = 0;
    costFromStart = 0;
    totalCost = 0;
    searched = false;
    discovered = false;
    parnentPos = Vector2.zero;
  }

  public void Initialize(int initCostToGoal) {
    costToGoal = initCostToGoal;
    costFromStart = 0;
    totalCost = 0;
    searched = false;
    discovered = false;
    parnentPos = Vector2.zero;
  }

  public void Discover(int _costToFromStart, Vector2 parnent) {
    parnentPos = parnent;
    costFromStart = _costToFromStart;
    totalCost = costToGoal + costFromStart;
    discovered = true;
  }

  public void Search() {
    searched = true;
  }
  public void Search(Vector2 parnent) {
    parnentPos = parnent;
    searched = true;
  }

  public bool canSearch() {
    return isMass == true && discovered == false && massType == MassType.CHECK_POINT;
  }

  public void SetMassType(MassType type) {
    massType = type;
  }

  public Vector2 ToVector2() {
    return new Vector2(pos.x, pos.z);
  }

}

public enum MassType {
  START,
  CHECK_POINT,
  GOAL,
}

ライセンス表記

ゲームで3Dモデルをつかったので。 © Unity Technologies Japan/UCL