몬스터(NPC) AI 적용 및 길찾기 (1)

MMORPG에서 몬스터 처리는 모두 서버가 해줘야한다.

몬스터는 어떠한 유저한테서나 동일한 AI를 보여줘야하기 때문이다.

 

플레이어의 경우 각자 유저의 PC에서 조작하는 개체이기 때문에,

서버에서 굳이 플레이어의 길찾기를 대신 해주지 않고 클라에서 길찾기 연산을 담당하게 된다.

실제로 클라가 서버에 전송하는 것은 전체 경로가 아니라,

다음에 이동할 '근시적인' 목적 좌표만 주기적으로 서버에 전송하게 된다.

 

게임에 따라서 자동 이동을 지원하는 경우가 있는데 (특히 오픈필드 모바일 mmo)

이 때도 좌표 계산을 서버에 위임하지 않고 클라에서 직접하게 된다.

그러나 광활한 경로를 노드 기반으로 하나씩 계산하게 되면 길찾기를 할때마다 클라에 렉 걸리는 현상이 일어날것이다.

따라서 아주 먼 거리 자동이동이 들어가는 게임 (마을 간 자동 이동이라거나)의 경우,

모든 경로를 한 번에 계산하지 않고 다양한 최적화가 들어가게 된다.

 

예를 들면 '검은사막' 같은 게임에서 다른 마을로 길찾기를 찍어놓으면,

일단 큰 길로 이동을 한 다음, 그 큰 길의 경로를 따라가간다.

큰 길로 이동하는 부분은 길찾기를 이용한 다음, 큰 길에서 찍힌 좌표대로 이동을 하는 방식이라고 유추할 수 있다.

---

아무튼 Server Side에서 길찾기를 해줄려면 레벨의 지형지물 정보를 데이터화 하여 서버에 보내줘야

이를 이용한 길찾기 수행 가능하다.

그리고 굳이 똑같은 지형 정보를 여러 클라이언트에서 여러번 보내지 말고, 빌드하면서 xml이든 json 파일이든 텍스트 파일이든 만들어서 서버 파일로 복사해주자.

그러면 지형정보가 업데이트 될 때 마다 파일만 복사해주면 될 것이다.

---

PathFinder 클래스

UCLASS()
class IOCPUNREAL_API APathFinder : public AActor
{
	GENERATED_BODY()
	
public:	
	APathFinder();

protected:
	virtual void BeginPlay() override;
	virtual void Tick(float DeltaTime) override;

public:	
	UPROPERTY(EditAnywhere)
	float LevelBoundary = 0.f;
	
	UPROPERTY(EditAnywhere)
	float _GridSize = 0.f;

	TArray<FVector> GenerateNodes(UWorld* World, float GridSize);
	bool IsLocationNavigable(UWorld* World, FVector Location);
	TMap<FVector, TArray<FVector>> GenerateEdges(const TArray<FVector>& Nodes, float GridSize);

	const TArray<FVector> NeighborOffsets = {
	FVector(1, 0, 0), FVector(-1, 0, 0),
	FVector(0, 1, 0), FVector(0, -1, 0)
	};

	TArray<FVector> NodeArr;
	TMap<FVector, TArray<FVector>> EdgesMap;
};

 

#include "PathFinder.h"
//#include "../XmlParser/Public/XmlFile.h"

// Sets default values
APathFinder::APathFinder()
{
	PrimaryActorTick.bCanEverTick = true;

}

void APathFinder::BeginPlay()
{
	Super::BeginPlay();
	
    GenerateEdges(GenerateNodes(GetWorld(), _GridSize), _GridSize);
    UE_LOG(LogTemp, Warning, TEXT("DebugTest"));
}

void APathFinder::Tick(float DeltaTime)
{
    Super::Tick(DeltaTime);
}

TArray<FVector> APathFinder::GenerateNodes(UWorld* World, float GridSize)
{
    TArray<FVector> Nodes;

    // 레벨의 경계를 기준으로 노드를 생성
    for (float x = -LevelBoundary; x <= LevelBoundary; x += GridSize)
    {
        for (float y = -LevelBoundary; y <= LevelBoundary; y += GridSize)
        {
            FVector Location(x, y, 0);
            if (IsLocationNavigable(World, Location))
            {
                Nodes.Add(Location);
            }
            else
            {
                UE_LOG(LogTemp, Warning, TEXT("Obstacle : %f,%f,%f"), Location.X, Location.Y, Location.Z);
            }
        }
    }

    NodeArr = Nodes;

    return Nodes;
}

bool APathFinder::IsLocationNavigable(UWorld* World, FVector Location)
{
    // 레이캐스트 등을 사용하여 Location이 이동 가능한지 확인
    FHitResult Hit;
    FVector Start = Location + FVector(0, 0, 100);
    FVector End = Location - FVector(0, 0, 100);
    FCollisionQueryParams Params;

    bool Result = !World->LineTraceSingleByChannel(Hit, Start, End, ECC_GameTraceChannel5, Params);

    if (Result)
        DrawDebugLine(GetWorld(), Start, End, FColor::Green, false, 10.f);
    else
        DrawDebugLine(GetWorld(), Start, End, FColor::Red, false, 10.f);

    return Result;
}

TMap<FVector, TArray<FVector>> APathFinder::GenerateEdges(const TArray<FVector>& Nodes, float GridSize)
{
    TMap<FVector, TArray<FVector>> Edges;

    for (const FVector& Node : Nodes)
    {
        TArray<FVector> Neighbors;
        for (const FVector& Offset : NeighborOffsets)
        {
            FVector Neighbor = Node + Offset * GridSize;
            if (Nodes.Contains(Neighbor))
            {
                Neighbors.Add(Neighbor);
            }
        }
        Edges.Add(Node, Neighbors);
    }

    EdgesMap = Edges;

    return Edges;
}

 

 

테스트를 위해 레벨 크기는 100, 그리드 사이즈는 10으로 해봤는데

생각보다 그리드가 너무 작은것 같다. 좀 더 키워보자.

 

 

 

 

사이즈를 키워주니 괜찮게 나오는 것 같다.

 

 

장애물이 있는 위치는 빨갛게 나온다.

 

 

텍스트 파일도 정상적으로 추출 되었다.

이제 노드는 만들어 졌으니 서버에서 이를 파싱해서 길찾기 알고리즘을 하는 기능들을 만들어 주자.

---

서버 PathFinder 클래스

struct Vector
{
    float x;
    float y;
    float z;

    bool operator < (const Vector& vec) const
    {
        if (x != vec.x)
            return x < vec.x;
        else if (y != vec.y)
            return y < vec.y;
        else if (z != vec.z)
            return z < vec.z;
        else
            return false;
    }
};

struct Node
{
    Vector Position;
    float GCost;
    float HCost;
    float FCost() const { return GCost + HCost; }
    Node* Parent;

    bool operator>(const Node& Other) const { return FCost() > Other.FCost(); }
};

class PathFinder
{
public:
    xmap<Vector, xvector<Vector>> EdgeMap;

public:
    xvector<Vector> AStart(const Vector& Start, const Vector& Goal, const xmap<Vector, xvector<Vector>>& Edges);
    void ReadFile();

private:
    Vector parseToVector(const string& str);
};

extern PathFinder GPathFinder;

 

#include "pch.h"
#include <fstream>
#include <sstream>
#include <tuple>
#include "PathFinder.h"

PathFinder GPathFinder;

xvector<Vector> PathFinder::AStart(const Vector& Start, const Vector& Goal, const xmap<Vector, xvector<Vector>>& Edges)
{
	return xvector<Vector>();
}

void PathFinder::ReadFile()
{
	ifstream file("LevelInfo.txt");
	string line;
	Vector currentKey;

	while (getline(file,line))
	{
		line.erase(remove_if(line.begin(), line.end(), ::isspace), line.end());

		if (line.substr(0, 4) == "Key:") 
		{
			currentKey = parseToVector(line.substr(4));
			EdgeMap[currentKey];
		}
		else if (line.substr(0, 6) == "Value:")
		{
			Vector value = parseToVector(line.substr(6));
			EdgeMap[currentKey].push_back(value);
		}
	}

	cout << "done" << endl;
}

Vector PathFinder::parseToVector(const string& str)
{
	Vector vec;
	sscanf_s(str.c_str(), "(%f,%f,%f)", &vec.x, &vec.y, &vec.z);
	return vec;
}

 

 

클라이언트에서 전달한 레벨의 정보를 서버의 메모리에서도 저장시켜 주었다.

이제 이를 이용해 길찾기 알고리즘을 완성 시키고, 만들어진 경로를 클라이언트에게 전달해주도록 하자.