A*の最短経路を見つける


はじめに – Unityのプロジェクト

あなたがゲーム開発者でなくても、おそらく名前「A*」(スター)を聞きました。このチュートリアルでは、私は、このアルゴリズムを紹介しようとします。
あなたは GitHubのから完全なプロジェクトをダウンロードすることができます。

Unity project

Asset Storeの上で無料で利用可能であるユニティちゃんモデルを使用しました

私はプロジェクトに見て、それがどのように動作するかを自分で参照することをお勧めします。グリッドを生成するための責任の基本的なクラスなどの文字の動きを管理する、既に存在します

Grid size

グリッド マネージャ

シーンPathfinding.unityでは、同じ名前の添付スクリプトを使用してGridManagerと呼ばれるゲームオブジェクトを見つけることができます。あなたはそこにあなたのグリッドのサイズを指定することができます。

リソースの下であなたはすべてのグリッドがで建設されるベースタイルですNodeVisualと呼ばれるプレハブを見つけることができますフォルダ。もう一つ興味深いのは、タイルと呼ばれるはScriptableObjectです。これは、列挙TerrainType.csに指定されているすべての地形タイプの配列を保持します。あなたはそこに地形を用いて可視化された色、この地形上を移動のコストを設定することができます。

Unity project

視覚的なノードとタイルエディタ

あなたがプレイを押すと、グリッドは指定された大きさのResourcesフォルダにNodeVisualで生成されています。で、あなたは、次のTerrainTypeに切り替えるノードを右クリックしてください。あなたはノードの上にマウスをドラッグすると、新しいパスが計算されます。あなたはときにそれらのいずれかを左クリックして、ユニティ・チャンは、選択したノードに行きます。

Preview

シーンのトップダウンビュー


A *アルゴリズム

*は広くビデオゲームのすべての種類に使用される経路探索アルゴリズムです。これはダイクストラのアルゴリズムを拡張したものです。ダイクストラアルゴリズム以上、その最大の利点は、それがグラフのノードが最初に横断されるべき推定ヒューリスティックを使用していることです。

ヒューリスティックは、ターゲットノードに現在のノードからの距離になります。ここでは、2Dグリッドで使用される最も人気の高い2つのヒューリスティックについての素晴らしい記事です。

そこにA*を(最新のゲームエンジンは、ナビゲーションメッシュ使用)アウトパフォームすることができますそこに多くのアルゴリズムがありますが、私はそれはまだ使用することができ、多くの状況を想像することができます。最も一般的な用途の一つは、タイルベースのゲームでの最短パスを見つけることです。のは、それを右に飛び込むしてみましょう。

下の画像上のようなノードの2Dグリッドを想像してみてください。

5x3 grid of tiles

ノードの5×3グリッド

これらの緑のタイルのそれぞれは、ノードと呼ばれます。あなたは、水平および斜め、垂直方向にこのグリッドに移動することができます。

擬似コード。

  1. 既にチェックされたノードのために評価されているノードのためのオープンセットと閉集合を宣言
  2. 指定された開始とターゲットノードと、オープンリストに開始ノードを追加します。
  3. オープンセットが空ではありませんが
    3.1. オープンセットのint最低のFコストでノードを検索し、可変電流ノードに割り当て
    3.2. オープンセットから現在のノードを削除し、閉集合に追加
    3.3. 現在のノードが対象ノードであればYESの場合、チェック – リターン
    3.4. 歩きやすいし、閉集合に含まれていない各隣接ノードの場合:
    3.4.1. 隣人へのパスが短くなるか、隣人がオープンセット内にない場合
    3.4.1.a. 隣人の設定Fコスト
    3.4.1.b. .隣人の親として現在の設定
    3.4.1.c. それはまだそこにいなかったらセット開くために隣人を追加
  4. ループの外では、ヌルを返した場合 – パスを見つけることができません

それが現実のC#コードでどのように見えるかです:

それはあなたのために、まだはっきりしていない場合は、何の心配は、私はそれがステップバイステップで通過しません。

ユニティちゃんは青ノードに赤のノードからの最短経路を見つけようとすると仮定しましょう。

Target and start nodesUnity Chan

あなたは上の写真で見ることができるように、最初のノード内部の3つの数字があります。私はH、GとFコストを表現するためにそれらを使用します。

  • ボトム       – Hコスト(見積コスト)
  • センター   – Gのコスト(これまでのコスト)
  • トップ       – Fコスト(総コスト)

グリーンノードは未訪問のノードを表します

黒のノードが閉集合を表します

レッドノードは開集合を表します

 

First iteration

第一反復

アルゴリズムを実行すると、最初の(スタート)ノードは、右のメインループに入る前に、オープンセットに追加されます。ループの終了条件は、オープンセットが空であることです。 1ノードが開集合でそこにあるので、ループの最初の反復が開始されます。現在のノードが最低のFとHコストによって選択され、それが閉集合に追加されます。
その後、我々は閉集合の内側ではありません、現在のノードのすべてのネイバーを取り、適切なG、HとFコストが計算されます。近隣の親は、現在ノードとして設定されています。

Second iteration

第二反復

あなたが見ることができるように、ループの2回目の反復内で、最低のFコストとHコストを持つノードが選ばれたと我々は斜めに移動します。すべてのネイバーを確認し、現在のノードに親を設定した後、オープンとクローズのセットは、上記の画像上のようになります。

いくつかのより多くの反復した後、現在のノードがターゲットノード(青色)とメインループが終了に等しくなります。すべての反復内で、我々はすべての隣人の親として現在のノードを設定しているので、我々は従う必要があり、パスをたどることができます。

Final Path

最終パス


概要

このチュートリアルでは、Unity5とC#で基本的なA *経路探索アルゴリズムを実装する方法を学びました。我々はここで行うことができ、最適化がたくさんあります。ご希望の場合は私に知らせてください、この経路探索技術に関するさまざまなバリエーションや改善についての次の部分があります。

自分で*を探索に興味を持っている場合は、GitHubの上の私のプロジェクトに見てみるお気軽に。

あなたはそれが便利なチュートリアルが見つかった場合、あなたには、いくつかの他のソリューションについて学びたい、私は下のコメント欄でそれについて知っている、または電子メールにてご連絡下さい。

これらは、自分で*について学習するときに役立つかもしれないウェブサイトです。

スタンフォード大学の材料
Sebastian Lague ユーチューブチュートリアル

1 comment

Add yours

+ Leave a Comment