[Unreal 5/C++] 회전 발판과 움직이는 장애물 퍼즐 스테이지

서론

회전하는 발판 & 움직이는 발판을 적절하게 조합해서 특정 시작점에서 도착지점까지 랜덤으로 맵을 생성하는 것을 구현해보았다.

우선 중요한건 시작점에서 도착지점까지 4방향으로 랜덤한 범위만큼 왕복 이동하는 발판과 정지해있는 발판이 반드시 만나야하며 발판끼리 겹치는 경우도 없어야 한다.

---

DynamicActor 클래스 구현

우선 발판들의 공통적인 속성을 가지고 있는 Actor를 상속받는 부모 클래스인 DynamicActor를 만들어 준다.

DynamicActor.h

#pragma once

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

UCLASS()
class ASSIGNMENT_API ADynamicActor : public AActor
{
	GENERATED_BODY()
	
public:	
	ADynamicActor();
	virtual void BeginPlay() override;
	virtual void Tick(float DeltaTime) override;

	UPROPERTY(VisibleAnywhere) USceneComponent* SceneRoot;
	UPROPERTY(EditAnywhere) UStaticMeshComponent* StaticMeshComponent;

};

DynamicActor.cpp

#include "DynamicActor.h"

ADynamicActor::ADynamicActor()
{
	SceneRoot = CreateDefaultSubobject<USceneComponent>(TEXT("SceneRoot"));
	SetRootComponent(SceneRoot);

	StaticMeshComponent = CreateDefaultSubobject<UStaticMeshComponent>(TEXT("StaticMesh"));
	StaticMeshComponent->SetupAttachment(SceneRoot);
}

void ADynamicActor::BeginPlay()
{
	Super::BeginPlay();
}

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

DynamicActor는 공통적으로 사용하는 SceneRoot와 StaticMesh를 초기화한다.

---

PatrolActor 클래스 구현

DynamicActor를 상속받는 4방향으로 랜덤한 범위만큼 왕복 이동하는 발판인 PatrolActor는 다음과 같다.

PatrolActor.h

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

#pragma once

#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "DynamicActor.h"
#include "PatrolActor.generated.h"

UENUM()
enum class EDirection {
	Forward,
	Right,
	Backward,
	Left,
};

UCLASS()
class ASSIGNMENT_API APatrolActor : public ADynamicActor
{
	GENERATED_BODY()
	
public:	
	APatrolActor();
	virtual void Tick(float DeltaTime) override;

protected:
	virtual void BeginPlay() override;

private:
	UPROPERTY(EditAnywhere, Category = "Properties") EDirection PatrolDirection;
	UPROPERTY(EditAnywhere, Category = "Properties") float PatrolSpeed;
	UPROPERTY(EditAnywhere, Category = "Properties") float PatrolRange;

	FVector MovementOffsets[4] = { {1,0,0},{0,1,0},{-1,0,0},{0,-1,0} };
	float TotalMoveDistance = 0;

	FVector GetDirection();
	void Patrol(const float DeltaTime);

public:
	void Init(const EDirection Direction, const float Speed, const float Range);
};

PatrolActor.cpp

#include "PatrolActor.h"

APatrolActor::APatrolActor()
{
	PrimaryActorTick.bCanEverTick = true;
	
	static ConstructorHelpers::FObjectFinder<UStaticMesh> MeshAsset(TEXT("/Script/Engine.StaticMesh'/Engine/EditorMeshes/AssetViewer/Floor_Mesh.Floor_Mesh'"));
	if (MeshAsset.Succeeded())
	{
		StaticMeshComponent->SetStaticMesh(MeshAsset.Object);
	}

	PatrolDirection = EDirection::Forward;
	PatrolSpeed = 1000;
	PatrolRange = 1000;
}

void APatrolActor::BeginPlay()
{
	Super::BeginPlay();
	
}

FVector APatrolActor::GetDirection()
{
	if (TotalMoveDistance >= PatrolRange) {
		PatrolDirection = (EDirection)(((int)PatrolDirection + 2) % 4);
		TotalMoveDistance = 0;
	}
	return MovementOffsets[(int)PatrolDirection];
}

void APatrolActor::Patrol(const float DeltaTime)
{
	FVector MovementDelta = GetDirection() * PatrolSpeed * DeltaTime;
	AddActorLocalOffset(MovementDelta);
	TotalMoveDistance += MovementDelta.Length();
}

void APatrolActor::Init(const EDirection Direction, const float Speed, const float Range)
{
	PatrolDirection = Direction;
	PatrolSpeed = Speed;
	PatrolRange = Range;
}


void APatrolActor::Tick(float DeltaTime)
{
	Super::Tick(DeltaTime);
	Patrol(DeltaTime);
}

PatrolActor는 방향과 속도, 범위가 주어지면 해당 방향으로 출발해서 범위에 도착하면 다시 시작지점으로 돌아오는 것을 반복한다.

---

RotationActor 클래스 생성

정지된 발판이자 주어진 속도와 방향으로 계속 회전하는 RotationActor를 생성한다.

RotationActor.h

#pragma once

#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "DynamicActor.h"
#include "RotationActor.generated.h"

UCLASS()
class ASSIGNMENT_API ARotationActor : public ADynamicActor
{
	GENERATED_BODY()
	
public:	
	ARotationActor();
	virtual void Tick(float DeltaTime) override;

protected:
	virtual void BeginPlay() override;

private:
	UPROPERTY(EditAnywhere, Category = "Properties") bool bRotateRight;
	UPROPERTY(EditAnywhere, Category = "Properties") float RotationSpeed;

	void ActorRotation(float DeltaTime);

public:
	void Init(const bool bRotateRight, const float Speed);
};

RotationActor.cpp

#include "RotationActor.h"

ARotationActor::ARotationActor()
{
	PrimaryActorTick.bCanEverTick = true;
	bRotateRight = true;
	RotationSpeed = 1000;

	static ConstructorHelpers::FObjectFinder<UStaticMesh> MeshAsset(TEXT("/Script/Engine.StaticMesh'/Engine/EditorMeshes/AssetViewer/Floor_Mesh.Floor_Mesh'"));
	if (MeshAsset.Succeeded())
	{
		StaticMeshComponent->SetStaticMesh(MeshAsset.Object);
	}
}

void ARotationActor::BeginPlay()
{
	Super::BeginPlay();
}

void ARotationActor::ActorRotation(float DeltaTime)
{
	FRotator DeltaRotation = FRotator::ZeroRotator;
	DeltaRotation.Yaw = RotationSpeed * DeltaTime * (bRotateRight ? 1 : -1);
	AddActorLocalRotation(DeltaRotation);
}

void ARotationActor::Init(const bool RotateRight, const float Speed)
{
	bRotateRight = RotateRight;
	RotationSpeed = Speed;
}

void ARotationActor::Tick(float DeltaTime)
{
	Super::Tick(DeltaTime);
	ActorRotation(DeltaTime);
}

---

퍼즐 스테이지 구현

이제 랜덤으로 생성될 액터들은 전부 준비가 되었다. 해당 액터들을 랜덤으로 선택해 배치하는 ActorGenerator 클래스를 만들어 준다.

ActorGenerator.h

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

#pragma once

#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "DynamicActor.h"
#include "PatrolActor.h"
#include "ActorGenerator.generated.h"

UCLASS()
class ASSIGNMENT_API AActorGenerator : public AActor
{
	GENERATED_BODY()
	
public:	
	AActorGenerator();
	virtual void Tick(float DeltaTime) override;

protected:
	virtual void BeginPlay() override;

private:
	UPROPERTY(EditAnywhere, Category = "Properties") int Width;
	UPROPERTY(EditAnywhere, Category = "Properties") int Height;
	UPROPERTY(EditAnywhere, Category = "Properties") int MinPatrolRange;
	
	void GenerateActor();
	void InitializeGrid(TArray<TArray<TPair<EDirection, int>>>& Grid);
	void SetupGraph(TArray<TArray<TPair<EDirection, int>>>& Grid, TMap<TPair<int, int>, TArray<TPair<int, int>>>& Graph);
	bool FindPath(const TMap<TPair<int, int>, TArray<TPair<int, int>>>& Graph, TArray<TPair<int, int>>& Path);
	void SpawnActorsAlongPath(const TArray<TPair<int, int>>& Path, const TArray<TArray<TPair<EDirection, int>>>& Grid);
};

각각 사용되는 함수들의 기능은 다음과 같다.

InitializeGrid는 Height * Width 크기의 Grid를 원소들을 랜덤으로 생성해준다. 랜덤으로 생성되는 값은 방향과 각 위치에서 배열의 범위를 벗어나지 않는 값으로 주어지며 MinPatrolRange로 최소값을 지정해줄 수 있다.

void AActorGenerator::InitializeGrid(TArray<TArray<TPair<EDirection, int>>>& Grid)
{
    FMath::RandInit(FDateTime::Now().GetTicks());
    TArray<TArray<int>> Offset = { {1, 0}, {0, -1}, {0, 1}, {-1, 0} };
    for (int i = 0; i < Height; i++) {
        TArray<TPair<EDirection, int>> Row;
        for (int j = 0; j < Width; j++) {
            int Rand = FMath::RandRange(0, 3);
            switch (Rand)
            {
            case 0: Row.Add({ EDirection::Forward, FMath::RandRange(0, FMath::Min(Height - i - 1, MinPatrolRange)) }); break;
            case 1: Row.Add({ EDirection::Backward, FMath::RandRange(0, FMath::Min(i, MinPatrolRange)) }); break;
            case 2: Row.Add({ EDirection::Right, FMath::RandRange(0, FMath::Min(Width - j - 1, MinPatrolRange)) }); break;
            case 3: Row.Add({ EDirection::Left, FMath::RandRange(0, FMath::Min(j, MinPatrolRange)) }); break;
            }
        }
        Grid.Add(Row);
    }
}

가장 골아팠던 부분인데 생성된 Grid를 토대로 그래프를 만들어주는 함수인 SetupGraph이다.

우선 예를들어서 (X, Y)의 위치에서 Forward 방향으로 N만큼 이동하는 발판은 (X + N + 1, Y)의 발판과 (X + N, Y + 1), (X + N, Y - 1)의 발판과 연결되어 있는 것이다. 또 여기서 만약 (X + N + 1, Y)에 해당하는 발판이 Backward로 이동한다면 동선이 겹치게 되므로 이 경우도 필터링을 해주어야 한다.

void AActorGenerator::SetupGraph(TArray<TArray<TPair<EDirection, int>>>& Grid, TMap<TPair<int, int>, TArray<TPair<int, int>>>& Graph)
{
    for (int y = 0; y < Height; y++) {
        for (int x = 0; x < Width; x++) {
            TPair<EDirection, int> Node = Grid[y][x];
            TArray<TPair<int, int>> Neighbors;

            auto AddNeighbor = [&](int NewY, int NewX, EDirection OppositeDirection) {
                if (NewY >= 0 && NewY < Height && NewX >= 0 && NewX < Width) {
                    TPair<EDirection, int> NeighborNode = Grid[NewY][NewX];
                    if (NeighborNode.Key != OppositeDirection || NeighborNode.Value == 0) {
                        Neighbors.Add({ NewY, NewX });
                    }
                }
                };

            switch (Node.Key) {
            case EDirection::Forward:
                AddNeighbor(y + Node.Value + 1, x, EDirection::Backward);
                AddNeighbor(y + Node.Value, x + 1, EDirection::Left);
                AddNeighbor(y + Node.Value, x - 1, EDirection::Right);
                break;
            case EDirection::Backward:
                AddNeighbor(y - Node.Value - 1, x, EDirection::Forward);
                AddNeighbor(y - Node.Value, x + 1, EDirection::Left);
                AddNeighbor(y - Node.Value, x - 1, EDirection::Right);
                break;
            case EDirection::Right:
                AddNeighbor(y, x + Node.Value + 1, EDirection::Left);
                AddNeighbor(y + 1, x + Node.Value, EDirection::Backward);
                AddNeighbor(y - 1, x + Node.Value, EDirection::Forward);
                break;
            case EDirection::Left:
                AddNeighbor(y, x - Node.Value - 1, EDirection::Right);
                AddNeighbor(y + 1, x - Node.Value, EDirection::Backward);
                AddNeighbor(y - 1, x - Node.Value, EDirection::Forward);
                break;
            }

            Graph.Add({ y, x }, Neighbors);
        }
    }
}

다음은 SetupGraph에서 연결된 그래프로 시작지점부터 도착지점까지 BFS로 최단거리를 찾는 FindPath 함수이다.

여기서 만약에 랜덤으로 생성된 그래프가 시작지점부터 도착지점까지 연결될 수 없다면 false를 반환한다.

bool AActorGenerator::FindPath(const TMap<TPair<int, int>, TArray<TPair<int, int>>>& Graph, TArray<TPair<int, int>>& Path)
{
    TPair<int, int> Start = { 0, Width / 2 };
    TPair<int, int> End = { Height - 1, Width / 2 };

    TMap<TPair<int, int>, TPair<int, int>> CameFrom;
    TArray<TArray<bool>> Visited;
    Visited.SetNum(Height);
    for (int i = 0; i < Height; i++) {
        Visited[i].SetNum(Width);
    }

    TQueue<TPair<int, int>> Frontier;
    Frontier.Enqueue(Start);
    Visited[Start.Key][Start.Value] = true;
    CameFrom.Add(Start, Start);
    bool bPathFound = false;
    while (!Frontier.IsEmpty()) {
        TPair<int, int> Current;
        Frontier.Dequeue(Current);

        if (Current == End) {
            bPathFound = true;
            break;
        }

        for (const TPair<int, int>& Next : Graph[Current]) {
            if (!Visited[Next.Key][Next.Value]) {
                Frontier.Enqueue(Next);
                Visited[Next.Key][Next.Value] = true;
                CameFrom.Add(Next, Current);
            }
        }
    }

    if (!bPathFound) {
        return false;
    }

    TPair<int, int> Current = End;
    while (Current != Start) {
        Path.Add(Current);
        Current = CameFrom[Current];
    }
    Path.Add(Start);
    Algo::Reverse(Path);

    return true;
}

생성된 최단 경로를 따라 액터를 생성하는 SpawnActorsAlongPath 함수이다.

임의로 지정한 StaticMesh인 Plane이 길이가 1000짜리이기 때문에 Scale을 1000으로 지정하고 위치나 순찰 범위등을 지정해주었다. StaticMesh가 변경되면 당연히 동작안한다. (StaticMesh의 직경을 가져오는 함수가 있으면 그걸로 Scale을 지정해주면 될 듯.)

그리고 X값에 따라 액터의 위치를 지정해줄때 X 값에 Width / 2를 빼주었는데 이걸 안해주면 ActorGenerator를 기준으로 (0,0)위치에서 생성되기 때문에 Start위치에 맞춰서 위치를 조정해줬다.

또한 PatrolActor를 생성할때 이전 액터와 Speed 차이가 50이상이 나도록 랜덤으로 계속 바꿔주는데 이게 없으면 운나쁘게 스피드와 방향이 같은 PatrolActor가 연속으로 생성될때 영원히 두 발판은 만날 수 없기 때문에 Speed 차이를 줘서 언젠가는 만날 수 있게 해줬다.

void AActorGenerator::SpawnActorsAlongPath(const TArray<TPair<int, int>>& Path, const TArray<TArray<TPair<EDirection, int>>>& Grid)
{
    int Scale = 1000;
    FVector ForwardVector = GetActorForwardVector();
    FVector RightVector = GetActorRightVector();
    FVector StartLocation = GetActorLocation();

    float PrevSpeed = 0;
    for (const TPair<int, int>& Node : Path) {
        int Y = Node.Key;
        int X = Node.Value;

        float Range = Grid[Y][X].Value * Scale;
        float Speed = FMath::RandRange(100, Scale);

        ADynamicActor* Actor = nullptr;

        if (FMath::IsNearlyZero(Range)) {
            ARotationActor* RotationActor = GetWorld()->SpawnActor<ARotationActor>(ARotationActor::StaticClass());
            RotationActor->Init(static_cast<bool>(FMath::RandRange(0, 1)), Speed);
            Actor = RotationActor;
            Speed = 0;
        }
        else {
            APatrolActor* PatrolActor = GetWorld()->SpawnActor<APatrolActor>(APatrolActor::StaticClass());
            while (FMath::Abs(Speed - PrevSpeed) < 50) Speed = FMath::RandRange(100, Scale);
            PatrolActor->Init(Grid[Y][X].Key, Speed, Range);
            Actor = PatrolActor;
        }

        X -= Width / 2;
        FVector Location = StartLocation + ForwardVector * Y * Scale + RightVector * X * Scale;
        Actor->SetActorLocation(Location);

        PrevSpeed = Speed;
    }
}

마지막으로 BeginPlay에서 실행될 GenerateActor 함수이다. FindPath를 통해 시작지점부터 도착지점까지 경로를 찾지 못한다면 재귀해서 그리드를 다시 랜덤으로 생성한다. 뭐 이론상 시간복잡도가 $O(\mathrm{\infty })$ 지만 언젠가는 만들어지겠지..

void AActorGenerator::GenerateActor()
{
    TArray<TArray<TPair<EDirection, int>>> Grid;
    InitializeGrid(Grid);

    TMap<TPair<int, int>, TArray<TPair<int, int>>> Graph;
    SetupGraph(Grid, Graph);

    TArray<TPair<int, int>> Path;
    if (FindPath(Graph, Path))
    {
        SpawnActorsAlongPath(Path, Grid);
    }
    else
    {
        GenerateActor(); // 경로를 못찾으면 재귀
    }
}

그렇게 크게 어려운 알고리즘이 들어가거나 그러진 않았는데. STL로만 짜던 알고리즘들을 Unreal 라이브러리를 사용해서 구현하려니까 생각보다 시간이 오래걸린것 같다.