[UE Team Project/Issac 3D] 2. 랜덤 맵 생성 - 1

개요

이번 포스팅에서는 랜덤한 맵을 생성하는 방법에 대해 제가 구현했던 방법을 토대로 정리해보려고 합니다.

랜덤 맵 생성 아이디어

처음 팀원들과 협의한 결과, 아이작의 맵 구성 방식 대신 던전 앤 파이터와 같은 스타일의 레벨을 제작하기로 결정했습니다. 이 방식이 기한 내에 더 나은 퀄리티를 달성할 수 있다고 판단했기 때문입니다.

 

방의 크기가 다르면 카메라의 촬영 반경이 달라지기 때문에, 이번 프로젝트에서는 방과 방이 맞닿은 형태의 맵을 구성하기로 했습니다. 아이작 스타일의 미니맵과는 다른 던전앤파이터 스타일의 미니맵을 목표로 삼았습니다.

(좌) 아이작 미니맵, (우) 던전앤파이터 미니맵

 

목표를 설정한 후, 다른 사람들이 어떤 방식으로 랜덤 맵을 제작하는지 조사해본 결과 이미 다양한 알고리즘들이 존재한다는 것을 알게 되었습니다.

 

다음 링크에서 확인해보면 미로를 생성하는 여러 알고리즘을 확인할 수 있습니다.

https://www.jamisbuck.org/mazes/

Maze Algorithms

 

이 자료에서는 여러 가지 미로 생성 알고리즘을 소개하고 있었고, 저는 그 중에서 프림 알고리즘을 사용하기로 결정했습니다.

간단한 알고리즘 소개

프림 알고리즘은 원래 최소 신장 트리(MST)를 찾는 알고리즘으로, 간단히 설명하면, 시작 지점에서 출발해 주변 방을 하나씩 연결하며 랜덤하게 새로운 방을 추가하고, 이 과정을 반복하면서 전체 맵이 완성되는 방식입니다.

Dungeon Generator Component - Room Info

먼저, 랜덤 맵 생성 알고리즘을 여러 곳에서 재사용할 수 있도록 Actor Component를 상속받아 Dungeon Generator Component로 설계했습니다. 이렇게 하면 어떤 액터에도 쉽게 추가할 수 있고, 다른 프로젝트에서도 쉽게 가져다 쓸 수 있게 됩니다.

 

던전 생성 과정에서 중요한 것은 각 Room이 어느 방향으로 연결되었는지를 체크하는 것입니다.

이를 효율적으로 처리하기 위해 저는 비트 플래그를 생각하게 되었고, 이를 위해 Enum 클래스를 정의하여 해당 Room의 연결 상태를 저장하도록 했습니다.

 

위와 같은 상황에서 왼쪽과 오른쪽이 열려있다면 OpenDir은 0011(3)이 되며, 4방향이 전부 열려있다면 1111(15)가 됩니다.

즉, 숫자 하나로 4개의 방향을 처리할 수 있게 되며 저는 해당 방식으로 룸을 관리하게 되었습니다.

Dungeon Generator Component - Random Map Generator

맵을 스폰하기 위한 정보를 생성하는 과정은 다음과 같습니다.

 

1. 입력받은 Height와 Width를 기준으로 배열을 초기화합니다.

 

2. 체크 가능한 임시 방 목록을 생성하고, 시작위치에 대해서만 초기화를 진행합니다.

 

3. 모든 방이 체크가 될 때까지 반복해서 길을 연결해주도록 합니다.

// 3. 모든 방이 체크가 될 때까지 반복해서 미로 생성하기
while (CheckCnt != DungeonMaps.Num())
{
	// 랜덤한 방 뽑기
	int32 RandIdx = TempRooms[FMath::RandRange(0, TempRooms.Num() - 1)];

	// 해당 방 방문처리
	DungeonMaps[RandIdx].bIsVisited = true;
	// 카운트 증가
	CheckCnt++;
	// 해당 방 임시 방 목록에서 제거
	TempRooms.Remove(RandIdx);

	// 해당 방으로부터 상하좌우 체크하여 연결해줄 방을 구해줍니다.
	EOpenDir ConnectDir = CheckDir(RandIdx);

	// 만약 연결할 수 있는 방이 존재한다면?
	if (ConnectDir != EOpenDir::EOD_NONE)
	{
		// 해당 방향과 이어주도록 합니다.
		// * 현재 방
		DungeonMaps[RandIdx].OpenDir |= static_cast<uint8>(ConnectDir);

		// * 연결한 방
		switch (ConnectDir)
		{
		case EOpenDir::EOD_LEFT:
			DungeonMaps[RandIdx - 1].OpenDir |= static_cast<uint8>(EOpenDir::EOD_RIGHT);
			break;

		case EOpenDir::EOD_RIGHT:
			DungeonMaps[RandIdx + 1].OpenDir |= static_cast<uint8>(EOpenDir::EOD_LEFT);
			break;

		case EOpenDir::EOD_UP:
			DungeonMaps[RandIdx - Width].OpenDir |= static_cast<uint8>(EOpenDir::EOD_DOWN);
			break;

		case EOpenDir::EOD_DOWN:
			DungeonMaps[RandIdx + Width].OpenDir |= static_cast<uint8>(EOpenDir::EOD_UP);
			break;
		}
	}

	// 해당 방의 상하좌우를 체크하여 방문되지 않은 방들을 배열에 추가합니다.
	if (DungeonMaps.IsValidIndex(RandIdx - Width) && DungeonMaps[RandIdx - Width].bIsVisited == false) TempRooms.Add(RandIdx - Width);
	if (DungeonMaps.IsValidIndex(RandIdx + Width) && DungeonMaps[RandIdx + Width].bIsVisited == false) TempRooms.Add(RandIdx + Width);
	if ((RandIdx / Width) == ((RandIdx + 1) / Width) && DungeonMaps.IsValidIndex(RandIdx + 1) && DungeonMaps[RandIdx + 1].bIsVisited == false) TempRooms.Add(RandIdx + 1);
	if ((RandIdx / Width) == ((RandIdx - 1) / Width) && DungeonMaps.IsValidIndex(RandIdx - 1) && DungeonMaps[RandIdx - 1].bIsVisited == false) TempRooms.Add(RandIdx - 1);
}

---

EOpenDir UDungeonGeneratorComponent::CheckDir(int32 CurrentIdx)
{
	// 여기서는 현재 인덱스에서 인접한 이미 방문한 방 하나를 랜덤으로 찾아서 반환해야 합니다.
	// * 상하좌우 체크를 진행합니다.
	TArray<EOpenDir> Indexs;

	// 위쪽
	if (DungeonMaps.IsValidIndex(CurrentIdx - Width) && DungeonMaps[CurrentIdx - Width].bIsVisited)
	{ 
		Indexs.Add(EOpenDir::EOD_UP);
	}
	// 아래쪽
	if (DungeonMaps.IsValidIndex(CurrentIdx + Width) && DungeonMaps[CurrentIdx + Width].bIsVisited)
	{
		Indexs.Add(EOpenDir::EOD_DOWN);
	}
	// 오른쪽
	if ((CurrentIdx / Width) == ((CurrentIdx + 1) / Width) && DungeonMaps.IsValidIndex(CurrentIdx + 1) && DungeonMaps[CurrentIdx + 1].bIsVisited)
	{
		Indexs.Add(EOpenDir::EOD_RIGHT);
	}
	// 왼쪽
	if ((CurrentIdx / Width) == ((CurrentIdx - 1) / Width) && DungeonMaps.IsValidIndex(CurrentIdx - 1) && DungeonMaps[CurrentIdx - 1].bIsVisited)
	{
		Indexs.Add(EOpenDir::EOD_LEFT);
	}

	// 만약 찾은 인덱스가 존재한다면?
	if (Indexs.Num())
	{
		// 랜덤으로 값을 추출합니다.
		return Indexs[FMath::RandRange(0, Indexs.Num() - 1)];
	}
	else
	{
		// 모두 연결이 불가능한 경우 -1을 반환합니다.
		return EOpenDir::EOD_NONE;
	}
}

위와 같은 과정을 거치면 Width * Heigh 크기의 미로가 제작됩니다. 스폰과 스폰할 Room 클래스에 대해서는 다음 포스팅에서 진행하도록 하겠습니다.