UE5 A*(Star) 알고리즘을 이용하여 PathFinding 만들기(2)

전 포스팅에서 Grid와 GridVolume을 생성했다.

이번 포스팅에서는 A Star 알고리즘을 이용해서 실제 캐릭터가 길을 찾고 이동하는 기능을 구현해 보자.

알고리즘 설명과 구현 참조는 https://recall.tistory.com/40 포스팅을 참조했다.

1. PathFinderComponent.h

캐릭터나 컨트롤러에 PathFinderComponent를 추가한다.

마우스를 클릭 한 지점을 목표점으로 삼고, 현재 캐릭터의 위치에서 이동할 수 있는 경로를 찾는다.

이동할 수 있는 경로를 찾으면 스플라인포인트를 생성하여 캐릭터가 이 스플라인 방향을 따라 움직이도록 AddMovementInput을 호출해 주는 방식으로 구현했다.

//UPathFinderComponent.h
struct FAStarPathFindInfo
{
	int row = 0;
	int col = 0;

	int GCost = INT_MAX;
	int FCost = INT_MAX;
	int HCost = INT_MAX;

	FVector2D WorldLocation;

	TSharedPtr<FAStarPathFindInfo> ParentInfo;
};

UCLASS(ClassGroup = (Custom), meta = (BlueprintSpawnableComponent))
class PROJECTGO_API UPathFinderComponent : public UActorComponent
{
	GENERATED_BODY()

public:
	UPathFinderComponent();

protected:
	virtual void BeginPlay() override;

	UPROPERTY(VisibleAnywhere, BlueprintReadOnly)
	USplineComponent* Spline;

	UPROPERTY(VisibleAnywhere, BlueprintReadOnly)
	FVector Goal;

	UPROPERTY(VisibleAnywhere, BlueprintReadOnly)
	FVector NextPoint;

	UPROPERTY(VisibleAnywhere, BlueprintReadOnly)
	float DistanceToGoal;

	UPROPERTY(EditAnywhere, BlueprintReadWrite)
	float GoalDistanceThreshold;

	UPROPERTY(EditAnywhere, BlueprintReadWrite)
	float DistanceThreshold;
	
	UPROPERTY(VisibleAnywhere, BlueprintReadOnly)
	float Length;

	UPROPERTY(VisibleAnywhere, BlueprintReadOnly)
	float CurrentIndex;
public:
	virtual void TickComponent(float DeltaTime, ELevelTick TickType, FActorComponentTickFunction* ThisTickFunction) override;

	UFUNCTION(BlueprintCallable)
	const TArray<FVector2D> FindPath(const TArray<APathFindGrid*>& GridArray, const int32& StartGridIndex, const int32& TargetGridIndex, const int32& ColSize, const FVector2D& FinalLocation);

	UFUNCTION(BlueprintCallable)
	const TArray<APathFindGrid*> GetAroundGrids(const TArray<APathFindGrid*>& GridArray, const APathFindGrid* const NowGrid, const int32& ColSize);

	UFUNCTION(BlueprintCallable)
	void Navigate(const TArray<FVector2D>& PathPoints);

};

FAStarPathFindInfo에서 최솟값을 구하기 쉽게 디폴트 변숫값들을 INT_MAX로 했다.

 

2. PathFinderComponent.cpp 함수 구현 설명

const TArray<APathFindGrid*> UPathFinderComponent::GetAroundGrids(const TArray<APathFindGrid*>& GridArray, const APathFindGrid* const NowGrid, const int32& ColSize)
{
	const int GridRowMax = GridArray.Num() / ColSize;
	const int GridColMax = ColSize;

	TArray<APathFindGrid*> ArroundGrids;

	if (NowGrid)
	{
		const TArray<int32> Arr_Search_Row = { -1, -1, -1, 0, 0, 1, 1, 1 };
		const TArray<int32> Arr_Search_Col = { -1, 0, 1, -1, 1, -1, 0, 1 };

		int SearchRow = 0;
		int SearchCol = 0;

		for (int i = 0; i < Arr_Search_Row.Num(); ++i)
		{
			SearchRow = NowGrid->GetGridInfo().GetRow() + Arr_Search_Row[i];
			SearchCol = NowGrid->GetGridInfo().GetCol() + Arr_Search_Col[i];
			if (SearchRow >= 0 && SearchRow < GridRowMax && SearchCol >= 0 && SearchCol < GridColMax)
			{
				const int32 SearchGridIndex = SearchRow * GridColMax + SearchCol;
				if(GridArray[SearchGridIndex]->GetGridInfo().GetCanMove())
				{
					ArroundGrids.Add(GridArray[SearchGridIndex]);
				}
			}
		}
	}
	return ArroundGrids;
}

현재 Grid 기준 주변 8개의 Grid를 캐릭터가 이동 가능한 Grid인지 검사해서 가져오는 함수이다.

SearchGridIndex를 설정하는 과정은 언리얼 C++가 다차원 배열 지원이 안되기 때문에 2차원 배열의 인덱스를 1차원 배열의 인덱스로 변환하여 사용했다. 레벨에 배치된 Grid들의 row/col 순서가 다르면 인덱스 설정 하는 값도 달라짐을 기억해야 한다.

 

const TArray<FVector2D> UPathFinderComponent::FindPath(const TArray<APathFindGrid*>& GridArray, const int32& StartGridIndex, const int32& TargetGridIndex, const int32& ColSize, const FVector2D& FinalLocation)
{
	TArray<FVector2D> Path;
	Path.Empty();
	const int CrossCost = 10;
	const int XCost = 14;
	int32 TargetGridIndexRow = TargetGridIndex / ColSize;
	int32 TargetGridIndexCol = TargetGridIndex % ColSize;

	TMap<int32, FAStarPathFindInfo> CloseList;
	TPriorityQueue<FAStarPathFindInfo> PQ_OpenList;
	TMap<int32, FAStarPathFindInfo> PQ_OpenListMap;

	FAStarPathFindInfo StartGrid;
	StartGrid.row = StartGridIndex / ColSize;
	StartGrid.col = StartGridIndex % ColSize;
	StartGrid.GCost = 0;
	StartGrid.FCost = 0;
	StartGrid.HCost = 0;
	StartGrid.WorldLocation = GridArray[StartGridIndex]->GetGridInfo().GetWorldLocation();
	for (const auto AroundGrid : GetAroundGrids(GridArray, GridArray[StartGridIndex], ColSize))
	{
		FAStarPathFindInfo ArroundGridInfo;
		ArroundGridInfo.WorldLocation = AroundGrid->GetGridInfo().GetWorldLocation();
		ArroundGridInfo.row = AroundGrid->GetGridInfo().GetRow();
		ArroundGridInfo.col = AroundGrid->GetGridInfo().GetCol();
		ArroundGridInfo.ParentInfo = MakeShared<FAStarPathFindInfo>(StartGrid);

		const bool Cross = StartGrid.row == ArroundGridInfo.row || StartGrid.col == ArroundGridInfo.col;
		const int PlusCost = Cross ? CrossCost : XCost;
		ArroundGridInfo.GCost = PlusCost;

		ArroundGridInfo.HCost = (FMath::Abs(ArroundGridInfo.row - TargetGridIndexRow) + FMath::Abs(ArroundGridInfo.col - TargetGridIndexCol)) * 10;
		ArroundGridInfo.FCost = ArroundGridInfo.GCost + ArroundGridInfo.HCost;
		PQ_OpenListMap.Add(ArroundGridInfo.row * ColSize + ArroundGridInfo.col, ArroundGridInfo);
		PQ_OpenList.Push(ArroundGridInfo, ArroundGridInfo.FCost);
	}
	CloseList.Add(StartGridIndex, StartGrid);

	while (!PQ_OpenList.IsEmpty())
	{
		FAStarPathFindInfo NowGrid;
		NowGrid = PQ_OpenList.Pop();

		const int32 NowGridIndex = NowGrid.row * ColSize + NowGrid.col;
		CloseList.Add(NowGridIndex, NowGrid);
		PQ_OpenListMap.Remove(NowGridIndex);

		if (CloseList.Find(TargetGridIndex))
		{
			//UE_LOG(LogTemp, Log, TEXT("Target Area Added"));
			break;
		}

		for (const auto AroundGrid : GetAroundGrids(GridArray, GridArray[NowGridIndex], ColSize))
		{
			FAStarPathFindInfo AroundGridInfo;
			AroundGridInfo.WorldLocation = AroundGrid->GetGridInfo().GetWorldLocation();
			AroundGridInfo.row = AroundGrid->GetGridInfo().GetRow();
			AroundGridInfo.col = AroundGrid->GetGridInfo().GetCol();
			const int32 ArroundGridIndex = AroundGridInfo.row * ColSize + AroundGridInfo.col;
			if (CloseList.Find(ArroundGridIndex))
			{
				continue;
			}
			else
			{
				const bool Cross = NowGrid.row == AroundGridInfo.row || NowGrid.col == AroundGridInfo.col;
				const int PlusCost = Cross ? CrossCost : XCost;
				if (FAStarPathFindInfo* FindedGrid = PQ_OpenListMap.Find(ArroundGridIndex))
				{
					if((NowGrid.GCost + PlusCost) < AroundGridInfo.GCost)
					{
						AroundGridInfo.ParentInfo = MakeShared<FAStarPathFindInfo>(NowGrid);
						FindedGrid->GCost = NowGrid.GCost + PlusCost;
						FindedGrid->FCost = FindedGrid->GCost + FindedGrid->HCost;
					}
				}
				else
				{
					AroundGridInfo.GCost = NowGrid.GCost + PlusCost;
					AroundGridInfo.HCost = (FMath::Abs(AroundGridInfo.row - TargetGridIndexRow) + FMath::Abs(AroundGridInfo.col - TargetGridIndexCol)) * 10;
					AroundGridInfo.FCost = AroundGridInfo.GCost + AroundGridInfo.HCost;
					AroundGridInfo.ParentInfo = MakeShared<FAStarPathFindInfo>(NowGrid);

					PQ_OpenList.Push(AroundGridInfo, AroundGridInfo.FCost);
					PQ_OpenListMap.Add(AroundGridInfo.row * ColSize + AroundGridInfo.col, AroundGridInfo);
				}
			}
		}
	}
	if(const FAStarPathFindInfo* TargetGrid = CloseList.Find(TargetGridIndex))
	{
		TSharedPtr<FAStarPathFindInfo> ParentGrid = TargetGrid->ParentInfo;
		Path.Insert(FinalLocation, 0);
		while(ParentGrid.IsValid())
		{
			Path.Insert(ParentGrid.Get()->WorldLocation, 0);
			ParentGrid = ParentGrid->ParentInfo;			
		}
	}
	return Path;
}

전체 GridArray와 캐릭터위치의 GridIndex, 마우스가 클릭된 위치의 GridIndex, 2차원 인덱스를 1차원 인덱스로 바꾸기 위한 colsize, 마우스가 클릭된 최종 위치를 변수로 받는다.

 

우선 PriorityQueue가 언리얼 C++에서 없어서 구글링을 통해 TPriorityQueueNode를 만들었다. 

아래의 깃허브 소스와 동일하게 만들었다.

https://gist.github.com/SomethingWithComputers/48e32b281d1bf8e662412e4113df43dc

A simple Priority Queue (Binary Heap) wrapper for UE4's TArray (for example for A*/A star and Greedy graph traversal)

최소힙 방식으로 우선순위 큐를 만든 것 같다.

 

전체적인 프로세스는 

(1) 플레이어의 위치에서 8방향을 검사하여 이동 가능한 Grid들을 OpenList에 넣는다.

(2) 플레어의 위치를 CloseList에 넣는다

(3) OpenList에서 FCost가 가장 작은 Grid를 꺼내고, 해당 Grid가 목적지면 탐색을 중단하고 그렇지 않으면 CloseList에 넣고, 8방향의 Cost를 계산 한 뒤, 조건에 따라 OpenList에 검사 한 Grid를 넣거나, 수정하고, 부모 Grid로 설정한다.

(4) (3)의 프로세스를 OpenList가 Empty 될 때까지 수행한다.

(5) 목적지가 CloseList에 들어갔다면, 목적지 Grid로부터 부모노드를 쭉 이어가서 경로를 배열로 저장한다.

 

List 변수들에 대해 설명하자면

(1) CloseList : 시작점부터 목표점까지 최종 경로 후보들이 들어가는 리스트며, 탐색 도중 CloseList에 이미 해당 Grid가 있는지 없는지 검사해야 하기 때문에 Map으로 설정했다.

 

(2) OpenList : 현재 Grid에서 이동 가능한 후보들을 넣어놓는 리스트이다. 이동 거리가 짧은 순서대로 탐색을 수행하기 위해 PriorityQueue로 구현 했다. 언리얼 C++에서 우선순위 큐가 없기 때문에 별도로 구현 헀으며 후에 코드를 설명하겠다.

 

(3) OpenListMap : 위의 OpenList와 같은 형태인데, 큐에서는 추가할 Grid가 있는지 없는지 바로 확인이 안 되기 때문에 이 부분을 보정해 줄 Map리스트로 만들었다. OpenListMap에 해당 Grid가 있는지 먼저 검사하여 OpenList에 해당 Grid가 이미 들어가 있는지 없는지를 판단한다.

 

3번 라인부터 38 라인 까지는 플레이어의 폰 위치를 CloseList에 넣고, 주변 8방향 중 이동 가능한 Grid들을 OpenList에 넣는 작업을 한다. OpenList큐에 넣으면서, OpenListMap에도 같이 추가하여 해당 Grid의 보유 유무를 판단할 수 있게 했다.

 

40번 라인부터 91 라인 까지는 후보지점부터 목표지점까지 길을 탐색하는 부분이다.

제일 먼저 현재 조건을 탐색 중인 Grid가 목적지면 작업을 중단한다.

OpenList에서 가장 F비용이 낮은 Grid를 기준으로 8방향의 비용을 체크하는데, 2가지 조건을 바탕으로 OpenList와 OpenListMap을 변경한다.

 

(1)  CloseList에 없거나 이동 가능한 Grid들을 검사해야 한다. 현재 비용을 체크 중인 Grid가 OpenList에 있으면 GCost를 비교해서 비용이 더 작으면 이전의 경로보다 현재 경로의 비용이 더 저렴하므로 Grid를 GCost와 FCost를 수정하여 OpenList에 넣고 부모 Grid로 설정해 준다.

 

(2) 현재 탐색 중인 Grid가 OpenList에 없다면 이 경로는 새로 찾아가는 경로이므로 비용과 부모노드를 세팅하여 OpenList와 OpenListMap에 넣어준다.

 

마지막 92라인부터 103라인 까지는 목적지 Grid로부터 시작 위치까지 Path경로를 꺼내서 배열에 저장한다.

최종 목적지를 먼저 넣어주고, 목적지 Grid부터 캐릭터 Pawn 위치까지 Parent로 연결 됐기 때문에 ParentGrid를 순환하면서 Path를 넣어준다.

 

위의 프로세스를 통해서 캐릭터의 위치부터 목적지까지의 경로탐색을 해 봤다. 

다음은 탐색된 경로를 Spline으로 만들어서 실제 캐릭터 이동경로를 만들어보자.

UPathFinderComponent::UPathFinderComponent()
{
	// Set this component to be initialized when the game starts, and to be ticked every frame.  You can turn these features
	// off to improve performance if you don't need them.
	PrimaryComponentTick.bCanEverTick = true;
	Spline = CreateDefaultSubobject<USplineComponent>(TEXT("Spline"));
	Spline->ClearSplinePoints();
	DistanceToGoal = 0.0f;
	GoalDistanceThreshold = 100.0f;
	DistanceThreshold = 50.0f;
}

생성자에서 Spline컴포넌트를 추가하여 설정해 주고, 기본값을 설정 해 준다.

DistanceToGoal : 캐릭터와 최종 목적지 사이의 거리

GoalDistanceThreshold : 캐릭터가 최종 목적지에 도달했는지 범위로 판단하기 위한 변수

DistanceThreshold : 캐릭터가 중간 목적지에 도달했는지 범위로 판단하기 위한 변수

 

다음은 경로를 Spline으로 만들어 주는 함수이다.

void UPathFinderComponent::Navigate(const TArray<FVector2D>& PathPoints)
{
	Spline->ClearSplinePoints();
	for (const FVector2D& Point : PathPoints)
	{
		FVector Point_3D(Point.X, Point.Y, 0);
		Spline->AddSplineWorldPoint(Point_3D);
		Goal = Point_3D;
	}
	Length = Spline->GetSplineLength();
	Spline->Duration = Length;
	CurrentIndex = 1;
	NextPoint = Spline->GetWorldLocationAtSplinePoint(CurrentIndex);
}

Path경로를 받아서 Spline을 쭉 추가해 준다.

Goal변수는 마지막 최종위치의 값으로 저장한다.

CurrentIndex는 이동시킬 Spline의 인덱스로 캐릭터가 해당 Spline위치의 범위에 들어오면 값을 1씩 증가시켜 다음 Spline의 위치를 가져오는 변수로 사용했다.

 

경로를 Spline으로 추가했으니, TickComponent에서 캐릭터가 Spline을 따라서 이동하도록 구현해 보자.

void UPathFinderComponent::TickComponent(float DeltaTime, ELevelTick TickType, FActorComponentTickFunction* ThisTickFunction)
{
	Super::TickComponent(DeltaTime, TickType, ThisTickFunction);

	if(Spline->GetNumberOfSplinePoints() == 0)
	{
		return;
	}

	const FVector ActorLocation(GetOwner()->GetActorLocation().X, GetOwner()->GetActorLocation().Y, 0);
	DistanceToGoal = (Goal - ActorLocation).Size2D();
	if (DistanceToGoal <= GoalDistanceThreshold)
	{
		Spline->ClearSplinePoints();
		return;
	}

	const float DistanceToNextPoint = (NextPoint - ActorLocation).Size2D();
	if (DistanceToNextPoint <= DistanceThreshold)
	{
		CurrentIndex += 1;
		NextPoint = Spline->GetWorldLocationAtSplinePoint(CurrentIndex);
	}

	const FVector Direction = (NextPoint - ActorLocation).GetSafeNormal2D();
	Cast<APawn>(GetOwner())->AddMovementInput(Direction, 1.0f);
}

DistanceToGoal : 캐릭터와 목표 Goal위치의 거리를 계산해서 범위값보다 작으면 목적지에 도달한 것으로 간주하고 종료다.

DistanceToNextPoint : 다음 목적지와 캐릭터의 위치 거리값으로 DistanceThreshold 범위 안에 있으면 중간 위치에 도달한 것으로 간주하고 다음 Spline의 위치를 목적지로 설정한다.

NextPoint와 캐릭터 위치의 벡터계산으로 캐릭터가 이동할 방향을 설정한다. 

AddMovementInput을 TickComponent에서 호출해 주면 캐릭터가 바뀌는 Spline위치에 맞춰서 이동하게 된다.

 

다음 포스팅에서는 현재까지 구현한 것들을 바탕으로 Controller의 수정과 블루프린트 작업을 통해 캐릭터를 이동시켜 보자.

 

문제점이 몇 개 있을 수 있는데, 우선 하나의 문제를 보자면 목적지가 이동 가능한 경로일 때만 정상적인 탐색을 수행한다는 것이다. 목적지가 이동이 불가능 한 위치면 목적지에 가까운 이동 가능한 위치까지 이동할 수 있도록 코드를 수정해야 할 필요가 있다.