햄랑

공부했던 것들을 남기는 곳입니다:)

[Sebastian Lague] A* Pathfinding (E03: algorithm implementation)

업데이트:     Updated:

카테고리:

태그: , ,

이 포스팅은 Sebastian Lague의 A* Pathfinding 영상을 기반으로 진행됩니다.
깃허브 주소: Sebistian Lague’s Github

 

📦 구현

image

이전 pseudo 코드를 사용하여 A* 알고리즘을 구현할 것이다.
참고로, 저번 코드들에 포인터를 붙이는 등 수정사항이 많다.

📜 Pathfinding.h

// Fill out your copyright notice in the Description page of Project Settings.

#pragma once

#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "Pathfinding.generated.h"

struct FNode;
class AGrid;

UCLASS()
class SL_ASTAR_API APathfinding : public AActor
{
	GENERATED_BODY()
	
public:	
	// Sets default values for this actor's properties
	APathfinding();

  // 레벨에 있는 Grid를 참조하기 위한 변수.
  // Grid.h의 UCLASS 안에 BlueprintType을 넣어줘야 작동함.
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Pathfinding")
	AGrid* Grid;

  // 시작점
	UPROPERTY(EditAnywhere)
	AActor* Seeker;

  // 도착점
	UPROPERTY(EditAnywhere)
	AActor* Target;

protected:
	// Called when the game starts or when spawned
	virtual void BeginPlay() override;

public:	
	// Called every frame
	virtual void Tick(float DeltaTime) override;

  // 경로 찾기
	void FindPath(const FVector& StartPos, const FVector& TargetPos);

  // H값(현재 노드 - 도착 노드) 거리 구하는 함수
	int GetDistance(FNode* NodeA, FNode* NodeB);

  // FindPath 함수가 실행된 후, 최종 경로를 구하는 함수
	void RetracePath(FNode* StartNode, FNode* EndNode);
};

에디터 상에서 Seeker와 Target 역할을 해줄 임의 Actor를 만들고,
블루프린트 변수에 넣어주면 된다.

📜 Pathfinding.cpp

FindPath() 파트

void APathfinding::FindPath(const FVector& StartPos, const FVector& TargetPos) {
	FNode* StartNode = Grid->NodeFromWorldPoint(StartPos);
	FNode* TargetNode = Grid->NodeFromWorldPoint(TargetPos);

	TArray<FNode*> OpenSet;
	TSet<FNode*> ClosedSet;
	OpenSet.Emplace(StartNode);

	while (OpenSet.Num() > 0) {
    // OpenSet에서 FCost가 가장 작으면서, HCost 또한 작은 노드를 구함.
		FNode* CurrentNode = OpenSet[0];
		for (int i = 0; i < OpenSet.Num(); i++) {
			if (
				OpenSet[i]->FCost() < CurrentNode->FCost() ||
				(OpenSet[i]->FCost() == CurrentNode->FCost() && OpenSet[i]->HCost < CurrentNode->HCost)
				) {
				CurrentNode = OpenSet[i];
			}
		}
		OpenSet.Remove(CurrentNode);
		ClosedSet.Emplace(CurrentNode);

    // 목적지에 도달한 경우
		if (CurrentNode == TargetNode) {
      // 최종 경로 찾기
			RetracePath(StartNode, TargetNode);
			return;
		}

    // 현재 노드에서 모든 이웃 검색
		for (FNode* Neighbour : Grid->GetNeighbours(CurrentNode)) {
      // 이웃 노드가 장애물이거나, ClosedSet에 속한 경우 continue
			if (!Neighbour->bWalkable || ClosedSet.Contains(Neighbour)) continue;

      // 한번도 연산된적 없는 노드거나, 연산됐었지만 새로운 경로가 더 빠른 경우
			int NewMovementCostToNeighbour = CurrentNode->GCost + GetDistance(CurrentNode, Neighbour);
			if (NewMovementCostToNeighbour < Neighbour->GCost || !OpenSet.Contains(Neighbour)) {
				Neighbour->GCost = NewMovementCostToNeighbour;
				Neighbour->HCost = GetDistance(Neighbour, TargetNode);
				Neighbour->Parent = CurrentNode;

        // 연산된적 없는 노드였다면 OpenSet에 추가
				if (!OpenSet.Contains(Neighbour)) OpenSet.Emplace(Neighbour);
			}
		}
	}
}

👉🏻 특징

  1. Emplace()와 Add()
    • Emplace는 참조 변수를 추가하는 것이고, Add는 변수를 복사하여 추가하는 것으로 다르다.
      최적화를 위해선 알맞은 곳에 Emplace를 사용하는 것이 좋다.
  2. 포인터
    • 유니티의 클래스는 참조 형식, 구조체는 값 형식이다.
    • 언리얼은 클래스와 구조체 모두 값 형식으로 구현되어있다.
    • Sebastian Lague은 유니티를 쓰고, Node는 클래스로 구현되었으므로, 변수가 복사되는 일이 없었다.
      하지만 언리얼을 쓰는 상황에서 Neighbour와 Parent가 똑같은 객체를 가리키게 하기 위해선 포인터를 사용해야 했다.

GetDistance() 파트

// 두 노드 간의 거리
int APathfinding::GetDistance(FNode* NodeA, FNode* NodeB) {

	int DstX = abs(NodeA->GridX - NodeB->GridX);
	int DstY = abs(NodeA->GridY - NodeB->GridY);

	if (DstX > DstY)
		return 14 * DstY + 10 * (DstX - DstY);
	return 14 * DstX + 10 * (DstY - DstX);
}

👉🏻 특징

  1. 맞닿은 거리는 10, 대각선 거리는 14로 치고 계산하고 있다.

RetracePath() 파트

// 최종 경로 탐색 함수
void APathfinding::RetracePath(FNode* StartNode, FNode* EndNode) {
	
	Grid->Path.Empty();
	FNode* CurrentNode = EndNode;

	while (CurrentNode != StartNode) {
		Grid->Path.Emplace(CurrentNode);
		if (!CurrentNode->Parent) {
			UE_LOG(LogTemp, Warning, TEXT("Parent is nullptr"));
			return;
		}
		CurrentNode = CurrentNode->Parent;
	}
	Grid->Path.Emplace(StartNode);

	Algo::Reverse(Grid->Path);

}

👉🏻 특징

  1. TList 대신 TArray
    • 유니티에는 리스트가 잘 구현되어 있지만, 언리얼에는 리스트의 기능이 거의 없다시피 하다.
      TList보단 TArray로 구현하는 것을 추천하는 경우가 많아, TArray로 구현하였다.
  2. Reverse 함수
    • 언리얼의 TArray에는 Reverse가 내장되어 있지 않다.
      그렇기에 #include “Algo/Reverse.h”를 해준 뒤, Algo::Reverse 함수를 사용하여 해주었다.

Tick() 파트

// Called every frame
void APathfinding::Tick(float DeltaTime)
{
	Super::Tick(DeltaTime);

	// Seeker&Target 검사. 유효성 검사를 하지 않으면 크래시 나므로 주의.
	if (!Seeker || !Target) return;
  // 매 틱마다 Path 검사
	FindPath(Seeker->GetActorLocation(), Target->GetActorLocation());

}

📜 Grid.h

USTRUCT(Atomic)
struct FNode {
	GENERATED_USTRUCT_BODY()

public:
	bool bWalkable;
	FVector WorldPosition;

	FNode* Parent;

  // 그리드 내 배열 좌표
	int GridX;
	int GridY;

	int GCost;
	int HCost;
	int FCost() { return GCost + HCost; }

	FNode() {
		bWalkable = true;
		WorldPosition = FVector(0, 0, 0);
		Parent = nullptr;

		GridX = 0;
		GridY = 0;
	}

	FNode(bool _walkable, FVector _worldPos, int _gridX, int _gridY) {
		bWalkable = _walkable;
		WorldPosition = _worldPos;

		GridX = _gridX;
		GridY = _gridY;
	}

	bool operator==(const FNode& Other) const {
		return WorldPosition == Other.WorldPosition;
	}
};

FORCEINLINE uint32 GetTypeHash(const FNode& Node) {
	return GetTypeHash(Node.WorldPosition);
}

// 넣어주어야 에디터 상에서 해당 클래스를 다른 블루프린트 변수에 값으로 넣어줄수 있음
UCLASS(BlueprintType)
class SL_ASTAR_API AGrid : public AActor
{
public:
  TArray<FNode*> Path; // 최종 경로
  // ...
}

👉🏻 특징

  1. GetTypeHash()와 등위 연산자 오버로딩
    • TSet또는 TMap에 커스텀 구조체(FNode)를 넣어주기 위해선,
      등위 연산자(operator==)와 GetTypeHash()를 추가해주어야만 한다.
      참고 : https://devjino.tistory.com/267
  2. GridX, GridY, G, H, F 변수 추가
    • 새로 추가된 Pathfinding 클래스를 위해 선언하였다.
  3. UCLASS(BlueprintType)
    • 에디터 상에서 해당 클래스를 다른 블루프린트에 넣어주기 위함

🏃🏻 실행

image

올바르게 경로가 나타나는 것을 확인할 수 있다.

🪶 깃허브

Readme Card
Sebastian Lague - Unity
Readme Card
Me - UE5

Techniques 카테고리 내 다른 글 보러가기

댓글남기기

참고