愛をもってゲームをつくるゴリラのブログ

UE5勉強中のゴリラがいろいろ頑張ります。

ウェイポイントの経路探索をA*アルゴリズムでやってみました。

この記事はUnreal Engine 4(UE4) #2 Advent Calendar 2019の15日目の投稿記事です。 qiita.com

ごりです。 久々の投稿で、初のアドカレ参加となります。
わかりにくいところ等ありましたら
連絡をいただけると助かります。

はじめに

A*アルゴリズムとは、探索アルゴリズムの一種です。
スタートノード(開始地点)からゴールノード(目標地点)までの経路を計算し、
この経路が最短であることを保証するアルゴリズムとなります。
今回はレベルに配置するウェイポイントをノードとして
A*アルゴリズムの経路探索を行っていきます。

サンプルプロジェクト作成しました

GooglDriveにてサンプルプロジェクトを配布しています。
サンプルプロジェクトを作って配布するというのが初めてなので、
中の作りがわかりづらいかもしれませんが、温かい目で見てもらえると助かります。

drive.google.com

バージョン

ソースコードも含めていますので、ビルド環境が必要となります。
以下の環境で作成しました。
UE4 Ver.4.24.0
Microsoft VisualStudio Community 2017 - Ver.15.9.5

動かしてみる

起動すると数字と矢印が配置されたレベルが表示されます。
この数字それぞれが今回作成するウェイポイントです。
矢印が表示されない場合はこのあと記載するウェイポイントの配置変更手順を試してみてください。 f:id:m-goolee-y:20191213182119p:plain

ウェイポイントの配置を変更したい場合は、 「EUQ_RegisterWayPoint」を右クリックで、RunEditorUtilityWidgetを選択してください。 f:id:m-goolee-y:20191213182542p:plain

画像のようなレイアウトにしておくと配置変更がしやすいです。 f:id:m-goolee-y:20191213182801p:plain

配置を反映させる場合は, 街名には、HogeCityと記入して登録をクリックしてください。
今回予め用意したデータアセットに変更がかかります。

※Data/HogeCity が変更されます。保存を必ず行ってください。

プレイを押して、動かしてみると、 グレイマンが数字を行き来するようになりましたね。
これだけですが、私はずっと見ていられました。(笑)

数字と矢印をプレイ中に表示したくない場合は、
「BP_WayPoint」のActorHiddenInGame を True にしてください。

この数字から数字へ移動する経路を探索するのが
今回解説するA*アルゴリズムです。

実装解説

CityData.h/cpp

ノードの定義

必要なデータは下記となります。

  • 座標
  • 隣接ノードIDリスト
  • Closeフラグ
    ノードの状態がOpenかCloseかの意味で扱います。
    true でCloseだった場合には、計算をスキップするといったことを行います。
  • 親ノードID
    ゴールからスタートまでこのIDをたどっていくと
    探索した最短経路になります。
  • 実移動コスト
    スタートからノードまでにかかるコストです。
    ノードからノードまでの距離をコストとしています。
  • ヒューリスティックコスト
    ノードからゴールまでの推定コスト
    ヒューリスティック関数はゴールまでの距離としました。
ノードの管理

ウェイポイントノードは DataAsset で管理をしています。
市民AIを作ることを想定して作成しており、街毎のデータを
どう管理しようと思った際に、DataAssetという結論にいたりました。
ノードの情報はすべてこのDataAsset を通して取得できるようにしています。

WayPoint.h/cpp

このクラスはレベル上に実際に配置するアクターです。 ウェイポイントに持たせる変数は下記になります。

  • 登録する街名
  • ノードID
  • 隣接するノードIDリスト

今回は配置した際にIDと隣接するノードがどこかわかりやすくするために、
TextRenderComponentとArrowComponentを変数に追加しています。

AWayPoint::Register で 街名をもとにデータをロードし、
ノードデータに変換して登録しています。

FString Path = DataFolderPath + CityName;
UCityData* Data = LoadObject<UCityData>(NULL, *Path, NULL, LOAD_None, NULL);
if (Data == nullptr) {
    UE_LOG(LogTemp, Error, TEXT("CityData not found."));
    UE_LOG(LogTemp, Error, TEXT("Check if there is CityData in /Game/Data/City/."));
    return;
}
/**
* ノードデータを作成
*/
FWayPointNode Node;
Node.Location = GetActorLocation();
Node.NextNodeIDList = NextNodeIDList;

/**
* 街データに登録
*/
Data->Register(NodeID, Node);

/**
* 登録した際にIDを取得するので、レベル上に表示されるように
* TextRender に設定
*/
if (TextRender) {
    TextRender->SetText(FString::FromInt(NodeID));
}

PathFindComponent.h/cpp

アルゴリズムの流れ

経路を実際に探索している UPathFinder::PathFind の解説を行っていきます。
最初に探索の準備としてOpenListを空にし、ウェイポイントノードすべてを初期化しています。

OpenList.Empty();
CityData->InitWayPointNodes();

1. スタートノードのIDをOpenリストに追加
スタートノードから移動開始のため、 実移動コストは 0

CityData->SetCost(StartID, 0.f, CalcHCost(StartID, GoalID));
PushID(StartID);

2. Openリストから最小スコアのノードIDを取得
Openリストが空の場合、スタートからゴールにたどりつく経路が
なかったということになり、探索失敗。

if (PopLowestCostID(LowestCostID) == false) {
  UE_LOG(LogTemp, Error, TEXT("------- Failed -------"));
  return false;
}

3. 取り出した最小スコアノードIDがゴールノードIDと一致した場合探索終了
異なった場合は、最小スコアノードをCloseとする。

if (LowestCostID== GoalID) {
    break;
}
CityData->ChangeState(LowestCostID, true);

4. 隣接する全ノードに対して以下を実行

int32 NextNodeID = CityData->GetNextNodeID(LowestCostID, i);
/**
*  計算中のノードから隣接ノードまでのコストを計算
*/
float GCost= CalcGCost(LowestCostID, NextNodeID);
float HCost= CalcHCost(NextNodeID, GoalID);
float TotalCost = FMath::Clamp(GCost+ HCost, 0.f, FLT_MAX);
/**
* すでに算出されている隣接ノードのコストを取得
*/
float NextTotalCost = CityData->GetTotalCost(NextNodeID);
float NextGCost = CityData->GetGCost(NextNodeID);
  • 隣接ノードの状態に応じて以下の処理を行う

    • 隣接ノードがOpenList に含まれており、以前に計算したコストよりも低い場合
    • 隣接ノードがOpenList になく、Closeでもない場合
      ノードのスコアと親ノードを更新する。
      ノードをOpenリストに追加する。

    • 隣接ノードがOpenListになく、Closeで以前に計算したコストよりも低い場合
      ノードのスコアと親ノードを更新する。
      ノードをOpenとし、Openリストに追加する。

if (OpenList.Contains(NextNodeID)) {
    if (TotalCost > NextTotalCost) {
        continue;
    }else if (TotalCost == NextTotalCost && GCost > NextGCost) {
        continue;
    }
}else {
    if (CityData->IsNodeClosed(NextNodeID)) {
        if (TotalCost > NextTotalCost) {
            continue;
        }else if (TotalCost == NextTotalCost && GCost > NextGCost) {
            continue;
        }
        CityData->ChangeState(LowestCostID, false);
    }
}
CityData->SetCost(NextNodeID, GCost, HCost);
CityData->SetParentNodeID(NextNodeID, LowestCostID);
PushID(NextNodeID);

5.2以降をループ

6. 探索に成功した場合、パスをゴールからたどる

int32 CurrentID = GoalID;
FoundPath.Add(CurrentID);
UE_LOG(LogTemp, Error, TEXT("GOAL"));
UE_LOG(LogTemp, Error, TEXT("%d"), CurrentID);

do {
    CurrentID = CityData->GetParentNodeID(CurrentID);
    FoundPath.Add(CurrentID);
    UE_LOG(LogTemp, Error, TEXT("|"));
    UE_LOG(LogTemp, Error, TEXT("%d"), CurrentID);
} while (CurrentID != StartID);

UE_LOG(LogTemp, Error, TEXT("START"));
UE_LOG(LogTemp, Error, TEXT("-------------------------"));

f:id:m-goolee-y:20191213175908p:plain

プロジェクトを実行すると画像のようなログ出力が出るようにしています。
実際に扱う際には、反転してもいいと思います。
私は配列の最後から順番に取得して使っています。

まとめ

A*アルゴリズムは CPUの使用率、メモリの使用率など計算不可が高いですが、
問題に応じた適切なヒューリスティック関数を用いることで問題に対して最適化が可能です。

最適化の手段として

  • 計算で求めたパスをキャッシュしておく
    サンプルプロジェクトの移動処理では計算結果をキャッシュしております。
  • 計算量が多すぎる場合は、次のフレームにまわす

といったことも挙げられます。
「ここをこうしたらもっと速くできるよ。」などありましたら、ぜひ教えていただけたらなと思います。

こちらは以前にアセットを変更して動かしてみた動画です。
よかったらこの記事を読んでいるみなさんも、アセットを変えて動かしてみてください。

ここまで読んでいただきありがとうございました。

明日は @torisutamoyasi さんのトゥーンエフェクト用のマテリアル! です。