[Unreal Engine C++] 청크 개념을 이용한 랜덤 맵 생성 알고리즘

이전 포스팅에서 말했듯이 BSP, MST를 이용한 랜덤생성 등등의 알고리즘을 사용하지 못하고 새롭게 생각한 아이디어인 청크 개념을 활용하여 랜덤 맵을 생성해보기로 하였다.
C++로 구현해 보았던 과정 및 결과를 글에 적어본다.

---

시작하기 전 - 설명

청크란? 영어에서 사용하는 뜻은 '서로 밀접하게 연결된 단어들의 집합 ' 이다.

코딩에 있어서는 하나의 큰 정보라고 생각해보자.

필자가 만든 이 랜덤 맵에서 하나의 청크인 이 큰 정보는 작은 정보를 포함하고 있다.
작은 정보는 위치가 어디인지와 이 곳에 무엇이 생성될 것인지, 어디로 이어지는지 등인 것이다.

앞으로 작은 정보들이 더 추가될 수 있지만, 이 세개면 일단 기본적인 구성은 준비된 것이라고 생각하였다.

---

만들기전에 준비하자 - 랜덤맵에 사용할 액터 생성

먼저 맵 생성을 담당하는 액터를 만들어 줄 것이다. 이름은 자유롭게 설정해주도록 하자.

물론 이 알고리즘 생성은 공부였기 때문에 간단하게 사용하기 위해 액터를 사용했지만 본격적인 게임을 만들 때엔 여러가지 맵이 필요하지 않거나, 싱글톤 패턴을 사용하고 싶다면 GameSubsystem을 사용했을 것 같다.

또한 똑같이 모든 방, 복도의 부모가 될 청크 액터도 만들어주도록 하자.

모든 클래스 표시를 클릭한 후 방과 복도는 청크를 부모로 하여 다시 액터 형태로 만들어 줄 것이다.

기본적인 준비는 끝났다.

---

시작해보자 - 청크, 방과 복도 구성

먼저, 메인시스템을 구현하기 전 방과 복도 정보를 저장할 변수 및 설정들을 만들어두자.

방이든 복도든 종류에 상관없이 자신의 종류가 무엇인지와 어디로 연결되는지를 알아야 할 필요가 있다.
또한 막혀있지만 이후에 복도가 연결될 때 그 쪽으로 뚫어줄 방법이 필요하다. (간단하게 문으로 생각하였다.)

// Chunk.h

public:	
	bool GetDoor(FString direction);
	void SetDoor(FString direction, bool state);

	UPROPERTY(VisibleAnywhere, Category = "RoomSetting")
	bool up;

	UPROPERTY(VisibleAnywhere, Category = "RoomSetting")
	bool right;

	UPROPERTY(VisibleAnywhere, Category = "RoomSetting")
	bool down;

	UPROPERTY(VisibleAnywhere, Category = "RoomSetting")
	bool left;
    
protected:
	enum Type {
		NONE, MAIN, ROOM, CORRIDER
	};
    
    int8 chunkType;

// Chunk.cpp

bool AChunk::GetDoor(FString direction)
{
	if (direction == FString("down"))
		return down;
	else if (direction == FString("up"))
		return up;
	else if (direction == FString("left"))
		return left;
	else if (direction == FString("right"))
		return right;
	else
		return false;
}

void AChunk::SetDoor(FString direction, bool state)
{
	if (direction == FString("down"))
		down = state;
	else if (direction == FString("up"))
		up = state;
	else if (direction == FString("left"))
		left = state;
	else if (direction == FString("right"))
		right = state;
}

각각 연결된 위치들은 디버깅시 쉽게 볼 수 있다록 UPROPERTY 속성을 이용하여 에디터에서 볼 수 있게 하였다.

 

이 청크를 상속받는 방들과 복도는 시작부터 기본적으로 문에 대한 정보를 가지고 시작하기 때문에 청크 타입만 지정해주었다.

// Room.cpp

ARoom::ARoom()
{
	...

	chunkType = ROOM;
}

---

가장 중요한 부분 - 맵 생성 알고리즘의 제작

간단한 방과 복도의 구성이 끝났다. 이제 본격적으로 만들어보자.

필자는 가지고 있는 에셋을 사용할 것이다.

가장 큰 방이자 게임에 핵심 맵으로 작동할 거실방, 복도들, 게임에서 사용될 액터들이나 여러 변수들이 생성될 각각의 다른 컨셉을 가진 작은방 이 있다.

메인 거실방

작은 방

복도

이 에셋들을 그대로 활용할 것이기 때문에 청크의 크기를 정사각형으로 고정하였다.

각각의 청크는 정사각형의 크기에 맞춰 양옆과 위아래로 모두 배치될 것이기 때문에 ChunkDistance로 미리 지정해주었다.
또한 가지고 있는 거실방 에셋은 각각 X가 증가하는 right, 감소하는 left, Y가 감소하는 down으로 이동할 수 있기 때문에 미리 복도를 스폰시키고 door값을 저장해주었다.

// MapGeneratorActor.cpp

void AMapGeneratorActor::GeneratingMap()
{
	FActorSpawnParameters tParams;
	
	// 메인 룸 스폰
	AMainRoom* Main = GetWorld()->SpawnActor<AMainRoom>(AMainRoom::StaticClass(), GetActorLocation(), FRotator::ZeroRotator, tParams);
	
	//ACorrider* upCorrider = GetWorld()->SpawnActor<ACorrider>(ACorrider::StaticClass(), FVector(GetActorLocation().X + ((i + 1) * ChunkDistance), GetActorLocation().Y, GetActorLocation().Z), FRotator::ZeroRotator, tParams);
	ACorrider* rightCorrider = GetWorld()->SpawnActor<ACorrider>(ACorrider::StaticClass(), FVector(GetActorLocation().X, GetActorLocation().Y + ChunkDistance, GetActorLocation().Z), FRotator::ZeroRotator, tParams);
	ACorrider* downCorrider = GetWorld()->SpawnActor<ACorrider>(ACorrider::StaticClass(), FVector(GetActorLocation().X - ChunkDistance, GetActorLocation().Y, GetActorLocation().Z), FRotator::ZeroRotator, tParams);
	ACorrider* leftCorrider = GetWorld()->SpawnActor<ACorrider>(ACorrider::StaticClass(), FVector(GetActorLocation().X, GetActorLocation().Y - ChunkDistance, GetActorLocation().Z), FRotator::ZeroRotator, tParams);
	
	rightCorrider->SetDoor(FString("left"), true);
	downCorrider->SetDoor(FString("up"), true);
	leftCorrider->SetDoor(FString("right"), true);

	AChunk* root_1 = rightCorrider;
	AChunk* root_2 = downCorrider;
	AChunk* root_3 = leftCorrider;

	//root 1
	for (int i = 0; i < 10; i++)
	{
		root_1 = GeneratingChunk(root_1);

		if (root_1 == nullptr)
			break;
	}

	//root 2
	for (int i = 0; i < 10; i++)
	{
		root_2 = GeneratingChunk(root_2);

		if (root_2 == nullptr)
			break;
	}

	//root 3
	for (int i = 0; i < 10; i++)
	{
		root_3 = GeneratingChunk(root_3);

		if (root_3 == nullptr)
			break;
	}
}

각각의 루트들은 이동하면서 현재 위치를 저장할 것이고, 그 위치에서 위아래 양옆을 확인하고 어디로 이어줄지 결정해줄 것이다.

// MapGenerator.cpp

AChunk* AMapGeneratorActor::GeneratingChunk(AChunk* CurrentChunk)
{
	FCollisionQueryParams QueryParams;
	QueryParams.AddIgnoredActor(CurrentChunk);

	AChunk* returnActor = CurrentChunk;

	bool upHitSuccess;
	bool rightHitSuccess;
	bool downHitSuccess;
	bool leftHitSuccess;
	FHitResult upHitResult;
	FHitResult rightHitResult;
	FHitResult downHitResult;
	FHitResult leftHitResult;

	upHitSuccess = GetWorld()->LineTraceSingleByChannel(
		upHitResult,
		CurrentChunk->GetActorLocation(),
		FVector(CurrentChunk->GetActorLocation().X + ChunkDistance, CurrentChunk->GetActorLocation().Y, CurrentChunk->GetActorLocation().Z),
		ECC_Visibility,
		QueryParams
	);

	rightHitSuccess = GetWorld()->LineTraceSingleByChannel(
		rightHitResult,
		CurrentChunk->GetActorLocation(),
		FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y + ChunkDistance, CurrentChunk->GetActorLocation().Z),
		ECC_Visibility,
		QueryParams
	);

	downHitSuccess = GetWorld()->LineTraceSingleByChannel(
		downHitResult,
		CurrentChunk->GetActorLocation(),
		FVector(CurrentChunk->GetActorLocation().X - ChunkDistance, CurrentChunk->GetActorLocation().Y, CurrentChunk->GetActorLocation().Z),
		ECC_Visibility,
		QueryParams
	);

	leftHitSuccess = GetWorld()->LineTraceSingleByChannel(
		leftHitResult,
		CurrentChunk->GetActorLocation(),
		FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y - ChunkDistance, CurrentChunk->GetActorLocation().Z),
		ECC_Visibility,
		QueryParams
	);
    
    ...

현재 있는 청크는 CurrentChunk이고, 이 위치에서 모든 방향을 라인트레이스로 확인하여 Hit한 Actor에 정보들을 HitResult에 저장해준다.

 

// MapGenerator.cpp

/*
* 위가 막혀있는 경우
*/
if(upHitSuccess && !rightHitSuccess && !downHitSuccess && !leftHitSuccess)
{
	// 방을 스폰시킬지 결정
	if (FMath::RandRange(0, 1) == 0)		// 방을 스폰
	{
		/*
		* 방을 스폰 시킨 뒤, 복도를 하나 더 만들지 말지를 결정.
		* Door가 있는 부분도 함께 저장해준다.
		*/
		int8 roomLocation;

		switch (FMath::RandRange(0, 2))
		{
			// RIGHT
		case 0:
			SpawnRoom(FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y + ChunkDistance, CurrentChunk->GetActorLocation().Z), FString("left"));
			roomLocation = 1;
			CurrentChunk->SetDoor(FString("right"), true);
			break;
			// DOWN
		case 1:
			SpawnRoom(FVector(CurrentChunk->GetActorLocation().X - ChunkDistance, CurrentChunk->GetActorLocation().Y, CurrentChunk->GetActorLocation().Z), FString("up"));
			roomLocation = 2;
			CurrentChunk->SetDoor(FString("down"), true);
			break;
			// LEFT
		case 2:
			SpawnRoom(FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y - ChunkDistance, CurrentChunk->GetActorLocation().Z), FString("right"));
			roomLocation = 3;
			CurrentChunk->SetDoor(FString("left"), true);
			break;
		default:
			break;
		}
        
		int8 checkCanGo = FMath::RandRange(0, 2);
		TArray<int8> roomNumber = {1, 2, 3};

		while (roomNumber[checkCanGo] == roomLocation)
			checkCanGo = FMath::RandRange(0, 2);

		switch (checkCanGo)
		{
			// RIGHT
		case 0:
			returnActor = SpawnCorrider(FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y + ChunkDistance, CurrentChunk->GetActorLocation().Z), FString("left"));
			CurrentChunk->SetDoor(FString("right"), true);
			break;
			// DOWN
		case 1:
			returnActor = SpawnCorrider(FVector(CurrentChunk->GetActorLocation().X - ChunkDistance, CurrentChunk->GetActorLocation().Y, CurrentChunk->GetActorLocation().Z), FString("up"));
			CurrentChunk->SetDoor(FString("down"), true);
			break;
			// LEFT
		case 2:
			returnActor = SpawnCorrider(FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y - ChunkDistance, CurrentChunk->GetActorLocation().Z), FString("right"));
			CurrentChunk->SetDoor(FString("left"), true);
			break;
		default:
			break;
		}
	}
	else									// 복도를 스폰
	{
		switch (FMath::RandRange(0, 2))
		{
			// RIGHT
		case 0:
			returnActor = SpawnCorrider(FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y + ChunkDistance, CurrentChunk->GetActorLocation().Z), FString("left"));
			CurrentChunk->SetDoor(FString("right"), true);
			break;
			// DOWN
		case 1:
			returnActor = SpawnCorrider(FVector(CurrentChunk->GetActorLocation().X - ChunkDistance, CurrentChunk->GetActorLocation().Y, CurrentChunk->GetActorLocation().Z), FString("up"));
			CurrentChunk->SetDoor(FString("down"), true);
			break;
			// LEFT
		case 2:
			returnActor = SpawnCorrider(FVector(CurrentChunk->GetActorLocation().X, CurrentChunk->GetActorLocation().Y - ChunkDistance, CurrentChunk->GetActorLocation().Z), FString("right"));
			CurrentChunk->SetDoor(FString("left"), true);
			break;
		default:
			break;
		}
	}
}

FMath::RandRange를 이용하여 방 or 복도 어떤 것을 스폰할지 정해준 뒤 각각의 작업을 수행한다.
RoomLocation을 상요하여 어떤 방을 스폰시켜주었는지를 저장한 뒤, 복도를 스폰시킬 때 겹치지 않게 저장한 정보를 이용하여 남은 다른 위치에 스폰시킨다.

이 작업을 가능한 모든 경우를 확인하여 지정하여준다.

이 때 이런 생각이 들 것이다

만약에 이렇게 진행되게 되면 무조건 길이 일방통행 아닌가..?

맞다. 이 코드의 큰 문제점은 길이 하나로만 이어진다는 것이다.

그것을 해결하기 위해 복도를 수정하기로 하였다.

복도는 방과는 다르게 어느 방향으로 서로 이어져도 상관이 없다. 작은 방의 입구는 하나뿐이지만 복도는 방과는 다르게 여러 방향으로 이어질 수 있는 것이다.

스폰되어있는 복도들의 값을 어떻게 확인하고 수정하는지는 다음과 같은 방법을 사용하면 된다.

// MapGenerator.cpp

void AMapGeneratorActor::MakingDoor(AChunk* currentChunk, FHitResult upHitResult, FHitResult rightHitResult, FHitResult downHitResult, FHitResult leftHitResult)
{
	if (upHitResult.bBlockingHit)
	{
		if (upHitResult.Actor->IsA<ACorrider>())
		{
			Cast<ACorrider>(upHitResult.Actor)->SetDoor(FString("down"), true);
			currentChunk->SetDoor(FString("up"), true);
		}
	}
	if (rightHitResult.bBlockingHit)
	{
		if (rightHitResult.Actor->IsA<ACorrider>())
		{
			Cast<ACorrider>(rightHitResult.Actor)->SetDoor(FString("left"), true);
			currentChunk->SetDoor(FString("right"), true);
		}
	}
	if (downHitResult.bBlockingHit)
	{
		if (downHitResult.Actor->IsA<ACorrider>())
		{
			Cast<ACorrider>(downHitResult.Actor)->SetDoor(FString("up"), true);
			currentChunk->SetDoor(FString("down"), true);
		}
	}
	if (leftHitResult.bBlockingHit)
	{
		if (leftHitResult.Actor->IsA<ACorrider>())
		{
			Cast<ACorrider>(leftHitResult.Actor)->SetDoor(FString("right"), true);
			currentChunk->SetDoor(FString("left"), true);
		}
	}
}

모든 경우의 수를 확인할 때 네 방향의 액터들의 값을 저장해주었다.

라인트레이스에 맞은 것을 확인하기 위해 bBlockingHit으로 확인하여 주었고, 그 액터가 ACorrider라면 그 액터의 문을 만들어주고 또한 현재 위치의 청크에 문을 만들어주도록 설정하였다.

---

결과 - 완성, 하지만 좀 아쉽다!

완성! 생각했던 대로 랜덤성을 이용한 랜덤 맵이 구성되었다.

하지만 처음에 생각과는 조금 다른 점이 발생하였다.

1. 정말 운에 의해 방이 스폰되지 않는다면 정말 긴 복도만 생성될 수도 있다.
2. root를 활용하여 왼쪽, 아래쪽, 오른쪽을 이엇지만 만약 한쪽으로 몰리게 된다면 맵이 정말 작아질 것이다.
3. root를 생성할 때 마지막 순서에서 복도를 스폰하면 막힌 길이 생성된다.

이 문제점은 차근차근 수정해 볼 예정이다.

---

마치면서 - 아직 멀었다.

처음으로 직접 생각해서 작성해본 알고리즘이였다.

물론 맵 생성을 재귀적으로 구현해보거나, 겹치는 코드들을 캡슐화 작업 및 간단하게 작성해보면 포트폴리오 뿐만 아니라 내 미래에 더 도움이 될 수도 있을 것 같지만 아직 그것뿐만 아니라 고쳐야 할 문제점과 내가 배워야할 점이 많은 것 같았다.

내 게임에서 사용할 수 있는 완벽한 알고리즘이 될 수 있도록 지속적으로 수정해 나갈 필요성을 느꼈다.

 

이 알고리즘은 깃허브에서 지속적으로 수정해보면서 이후 필자가 생각하는 모든 문제점이 해결되면 다시 적어보도록 하겠다.

더 자세한 내용 및 코드는 이 링크에서 확인할 수 있다.

NiffJB_GitHub - Generating_Random_Map

GitHub - RoofMi/Generating_Random_Map: 언리얼4.27을 활용한 맵 랜덤 생성 알고리즘을 제작해 보았습니다.