AlgorithmUnityで幅優先探索で最短経路を求めてみます。関連Unity2019.1.10幅優先探索?この記事では幅優先探索により最短経路を求めてみます。このアルゴリズムを理解します。いま、このようにゴール地点と、通り抜けられない壁が存在するマス目があるとします。幅優先探索ではまずゴールに隣接するマスに、自身を指す向きの矢印を書きます。次に、先ほど矢印を書いたマスからさらに隣接するマスに、自身を指す向きの矢印を書きます。この作業をマス目が埋まる(もしくは行き止まる)まで繰り返します。あとは任意のマスを選択し、矢印を辿ればそれがゴールまでの最短距離となります。幅優先探索のメリットとデメリット(A*アルゴリズムとの比較)幅優先探索以外の経路探索アルゴリズムとして、当サイトでは過去にA*を紹介しています。light11.hatenadiary.comA*と比べると幅優先探索は、全部のセルを計算する必要があるものの、ゴールが複数だったり任意のマスからの最短距離をまとめたりする場合にはメリットがあるといえそうです。ソースコードさてそれでは前節のアルゴリズムをソースコードで実装してみます。各マスごとの処理を書きます。}}上下左右のCellに対してExtendPathTo()を呼ぶことで最短経路の進行方向のセルがNextCellとして入ってきます。下の方はギズモ描画用のメソッドです。次にこのCellを管理するクラスを実装します。}}_cellPrefabには先ほどのCellコンポーネントをアタッチしたPrefabを設定します。すると_sizeに入力した大きさのマス目が生成されます。ゴールと障害物の座標は_goalCoordsと_obstacleCoordsに入力しておきます。Objectにアタッチしてから再生すると、Sceneビューに次のようなGizmoが表示されます。青い四角はゴールとして設定したマス、赤い×は障害物として設定したセルです。三角形は進行方向を示しています。上図から、ゴールへの最短経路が正常に求められていることがわかりました。»プロフィールUnityエンジニア。グラフィックスへの興味が強めです。インストールから基本的な使い方・注意点まとめ【Unity】【エディタ拡張】テクスチャを指定したUV座標で切り取って保存する【Unity】指定したアセットのAssetBundle名を取得する【Unity】【シェーダ】スクリプトからVP行列を渡してシェーダで座標変換に使う【Unity】【シェーダ】FloatやVectorをリニアライズ対象にするGammaアトリビュート月別アーカイブはてなブログをはじめよう!halya_11さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。