のののーと

何か作った時のメモ書き

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

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

f:id:nonoui:20180115231046g:plain

※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つの黒い四角が壁である。

f:id:nonoui:20180115222317p:plain

推定値の設定

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

f:id:nonoui:20180115223121p:plain

探索フェイズ

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

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

また、捜索済みマスの合計値は以下のような感じになる f:id:nonoui:20180115225231p:plain

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

f:id:nonoui:20180115225532p:plain

走ることを強いられる...! f:id:nonoui:20180115231632g:plain

感想

参考になった書籍

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

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

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

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

お手軽にできない?

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

docs.unity3d.com

ソースコード

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

ライセンス表記

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