jpnPath Guide - B477042/GraduationProject GitHub Wiki
Playerのゲーム進行に役立つよう追加しました。
NodeをTree形式で構成した後、その中でAstarを適用させたら道を案内できるのか知りたくて、TreeとAstarを組み合わせた形をしています。
UCLASS()
class ESCAPEGAME_API AAStarFinder : public AActor
{
//訪問するノードです。
TQueue<TWeakObjectPtr<AAstarNode>>ToVisitNodes;
//到着地点ノード
UPROPERTY(Transient, EditInstanceOnly, meta = (AllowPrivateAccess = "true"))
TWeakObjectPtr<AAstarNode> GoalNode;
//カードキーの位置ノード
TWeakObjectPtr<AAstarNode>KeyNode;
UPROPERTY(Transient, meta = (DisplayName = "Nodes"))
TArray< TWeakObjectPtr<AAstarNode>>AllNodes;
}
初期はUE4のSingletonclassに設定して活用しました。 しかし、Singletonclassの特性上、エディタとゲームに存在し続けているため、目的に合わずActor形態で作り直しました。
AAstarNodeをAllNodesという配列にWeakPointerの形で入れておきました。
経路を見つけたノードをGoalあるいはKeyメンバー変数値で指定しました。
void AAStarFinder::PathFind(AAstarNode * Start,EPathTarget Mode)
{
if (!Start)
{
EGLOG(Error, TEXT("Start is nullptr"));
return;
}
ToVisitNodes.Empty();
ToVisitNodes.Enqueue(Start);
switch (Mode)
{
case EPathTarget::Key:
KeyFind(Start, KeyNode.Get());
break;
case EPathTarget::Gate:
GoalFind(Start, GoalNode.Get());
break;
default:
break;
}
}
void AAStarFinder::GoalFind(AAstarNode * Start, AAstarNode * Goal)
{
if (!Start)
{
EGLOG(Error, TEXT("Nullptr"));
return;
}
if (!Goal)
{
EGLOG(Error, TEXT("Nullptr"));
return;
}
}
パスの探索機能でGoalとKeyを探す機能を提供しています。 2つのアルゴリズムは、同じで探す対象のみ異なる関数です。
TWeakObjectPtr<AAstarNode> PopedNode;
int i = 0;
//訪問するノードが空になるまでです。
while (!ToVisitNodes.IsEmpty())
{
i++;
//Queueから1つを取り出します。
ToVisitNodes.Dequeue(PopedNode);
if (!PopedNode.IsValid())
{
EGLOG(Error, TEXT("PopedNode is invalid"));
return;
}
//EGLOG(Warning, TEXT("Current Node : %s"), *PopedNode->GetName());
//ノードに訪問します。
PopedNode->VisitNode();
//読み取ったノードがGoalと同じ位置であれば
if (PopedNode->GetActorLocation() == Goal->GetActorLocation())
{
//Goal Nodeを設定し、ToVisite Nodeを空にします。
// EGLOG(Error, TEXT("Goal Find! : %s"), *PopedNode->GetName());
GoalNode = PopedNode.Get();
ToVisitNodes.Empty();
break;
}
whileループの条件としてToVisitNodesが空になるまで繰り返されるようにしました。そしてQueueに含まれる順番にノードを検査しました。
ノードを切り出した直後、ノードに訪問したノードであることを表示しました。 Goalノードを探す作業ですので、ここではGoalノードの認知検査をしました。
//近くのノードの周りのノードがあれば、
if (PopedNode->NearNodes.GetData() != nullptr)
//近隣ノードの値を計算する。
{
for (auto it : PopedNode->NearNodes)
{
//有効でなければ次に進みます。
if (!it.IsValid())continue;
//訪問したノードが通る。
if (it->IsVisitedNode())continue;
it->CalcFCount(Start->GetActorLocation(), Goal->GetActorLocation());
}
//取り出したノードの周辺ノードの以前のノードを取り出したノードに設定してくれる。
PopedNode->SetNearNodesPrevAsMe();
//fcount順に整列
for (int k = 0; k < PopedNode->NearNodes.Num();++k)
{
for (int j = k+1 ; j < PopedNode->NearNodes.Num()-1; ++j)
{
//比較前有効性検査
if (!PopedNode->NearNodes[k].IsValid() || !PopedNode->NearNodes[j].IsValid())continue;
if (PopedNode->NearNodes[k]->GetF() > PopedNode->NearNodes[j]->GetF())
PopedNode->NearNodes.Swap(k, j);
}
}
訪問したこのノードがGoalでない場合は近隣ノードの有効性を検査してからFCountを計算しました。
スキャンが終わった後にパスを表示するためにList形式でNodeを接続させるため、周辺ノードの前のノード値を自分が指定します。
そして、NearNodeの配列順序をFcount順に整列します。 場合の数が多くないためBubble Sortを実行しました。
F、G、H カウントの計算の基準はオブジェクトの座標ベクトル値としました。
//整列された順に入れる
for (auto it : PopedNode->NearNodes)
{
//有効でなければ次に進みます。
if (!it.IsValid())continue;
//訪問したノードなら もう入れなくても大丈夫です。
if (it->IsVisitedNode())continue;
//PopedNode->VisitNode();
// EGLOG(Warning, TEXT("Enqueue : %s"), *it->GetName());
ToVisitNodes.Enqueue(it.Get());
}
}
}
//================ While ループ終了==============
//ゴールノードを見つけたら、経路を活性化してくれます。
if (GoalNode.IsValid())
ShowPath(EPathTarget::Gate);整列された順番にToVisit Nodesに入れます。
Whileループが終わってGoalNodeを発見して探したら、Nodeに指定した以前のノードを有効にして経路を表示させる方法です。
ツリーの形の構造なのにAstarが適用されるのかという疑問がありましたが、結果的にパスはうまく表示されました。
これを実現するときに集中したのは、計算を始める時点がPlayerがノードに触れたときに始まるために、この作業によって性能が著しく落ちることがないようにという考えだけでした。 目立ったフレームの変化なく、経路がよく表示されてよかったです。
AStarアルゴリズムを正確に理解して作るためにAStarを勉強する過程が難しかったです。 F、G、Hというアルファベットを変数として使ったせいで、これがどういう意味なのかわからなくなりました。 勉強を終えた後、F、G、Hに名前を新しく付けるかどうか悩んだのですが、全世界の人々がF、G、Hと使うので諦めました。この作業を通じて、ゲームの中に道探しを適用させる経験をするようになり、アルゴリズムがなかったら、これをどのように実現できたのか途方に暮れてしまい、このようなアルゴリズムを作ってくださった方々に感謝の気持ちを持つようになりました。
この方法を使用する場合、ノードをエディタでつなぎ合わせる作業が必要なので、良い作業ではありません。 どうしたら自動で貼り合えるのか、方法を探したくなってきました。