절차적 생성 던전 동굴 시스템 만들기

많은 사람들에게 절차적 생성은 도달할 수 없는 환상의 개념입니다. 오직 숙련된 게임 개발자만이 레벨을 생성하는 게임을 만드는 법을 압니다. 맞나요? 마법처럼 보일 수도 있겠지만 PCG(절차적 컨텐츠 생성; procedural content generation)은 초급 게임 개발자도 배울 수 있습니다. 이 튜토리얼에서 절차적으로 던전 동굴 시스템을 생성하는 방법에 대해 보여드릴 겁니다.

우리가 다룰 것

이 테크닉으로 생성 가능한 종류의 레벨 레이아웃을 보여주는 SWF 데모를 준비했습니다.

기본을 배우는 것은 일반적으로 많은 구글 검색과 실험을 의미합니다. 문제는 시작하는 방법을 설명하는 간단한 가이드는 거의 없다는 것입니다. 참고로 다음은 제가 공부한 주제에 대한 훌륭한 정보 소스들입니다.

• 완벽한 로그라이크 튜토리얼 (파이썬과 libtcod)
• 격자 기반 던전 생성
• PCG 위키

자세한 것으로 들어가기 전에 문제를 어떻게 풀지 고려해봅시다. 이것을 간단하게 유지하기 위해 사용할 간단한 단계가 있습니다.

1. 생성된 컨텐츠를 게임 월드에 랜덤하게 배치합니다.
2. 컨텐츠가 알맞은 장소에 배치되었는지 확인합니다.
3. 플레이어가 컨텐츠에 접근 가능한지 확인합니다.
4. 레벨이 모두 잘 될 때까지 위 단계를 반복합니다

다음 예제를 통해 작업한 후에는 자신의 게임에서 PCG를 실험하는데 필수적인 스킬을 가질 것입니다. 흥미로운가요?

게임 컨텐츠는 어디에 두어야 할까요?

우선 해야 할 것은 절차적으로 생성된 던전 레벨의 방을 무작위로 배치하는 것입니다.

이것을 따라가기 위해서는 타일 맵이 어떻게 작동하는지에 대한 기본적인 이해를 하는 것이 좋습니다. 빠른 개요나 떠올리기가 필요한 경우라면 이 타일 맵 튜토리얼을 확인하세요. (이것은 플래시로 되어 있지만, 플래시에 익숙하지 않더라도 타일 맵의 요점을 얻는데는 좋습니다.)

던전 레벨에 배치할 방 만들기

시작하기 전에 벽 타일로 타일 맵을 채워야 합니다. 지도의 모든 지점(이상적으로는 2차원 배열)을 반복해가면서 타일을 배치하기만 하면 됩니다.

또한 각 사각형의 픽셀 좌표를 그리드 좌표로 변환해야 합니다. 픽셀에서 그리드 위치로 이동하려면 픽셀 좌표를 타일 너비로 나눕니다. 그리드에서 픽셀로 이동하려면 그리드 좌표에 타일 너비를 곱합니다.

예를 들어 방의 상단 왼쪽 모서리를 그리드의 (5, 8)에 두려고 하고 타일 너비를 8 픽셀로 한다면, 모서리의 픽셀 좌표는 (5 * 8, 8 * 8) 혹은 (40, 64)에 두어야 합니다.

Room 클래스를 만들어봅시다; Haxe 코드에서 이것처럼 보일 수 있습니다:

1

class Room extends Sprite {

2

  // these values hold grid coordinates for each corner of the room

3

	public var x1:Int;

4

	public var x2:Int;

5

	public var y1:Int;

6

	public var y2:Int;

7

8

	// width and height of room in terms of grid

9

	public var w:Int;

10

	public var h:Int;

11

12

	// center point of the room

13

	public var center:Point;

14

15

	// constructor for creating new rooms

16

	public function new(x:Int, y:Int, w:Int, h:Int) {

17

		super();

18

19

		x1 = x;

20

		x2 = x + w;

21

		y1 = y;

22

		y2 = y + h;

23

		this.x = x * Main.TILE_WIDTH;

24

		this.y = y * Main.TILE_HEIGHT;

25

		this.w = w;

26

		this.h = h;

27

		center = new Point(Math.floor((x1 + x2) / 2),

28

			Math.floor((y1 + y2) / 2));

29

	}

30

31

	// return true if this room intersects provided room

32

	public function intersects(room:Room):Bool {

33

		return (x1 <= room.x2 && x2 >= room.x1 &&

34

			y1 <= room.y2 && room.y2 >= room.y1);

35

	}

36

}

우리는 각 방의 너비, 높이, 중심점 위치, 네 모서리의 위치에 대한 값과 이 방이 다른 방과 교차하는지를 알려주는 함수를 가집니다. 또한 x와 y값을 제외한 모든 것은 그리드 좌표계에 있습니다. 이는 방 값에 접근할 때마다 작은 숫자를 사용하는 것이 훨씬 쉽기 때문입니다.

좋습니다. 방을 위한 프레임워크를 갖추었습니다. 이제 어떻게 절차적으로 방을 생성하고 배치해야 할까요? 내장된 난수 생성기 덕분에 이 부분은 그렇게 어렵지 않습니다.

우리가 해야 할 것은 맵 범위 내에서 방에 랜덤한 x와 y 값을 제공하고, 미리 지정된 범위 내에서 랜덤한 너비와 높이 값을 제공하는 것입니다.

무작위 배치가 잘 되었나요?

방에 랜덤한 위치와 크기를 사용하므로 던전을 채울 때 이전에 만들어진 방과 겹치게 됩니다. 이 문제를 해결할 수 있도록 간단한 intersects() 메소드를 만들어두었습니다.

새로운 방을 배치하려고 할 때마다 전체 목록 내의 2개 방마다 intersects()를 호출하기만 하면 됩니다. 이 함수는 Boolean 값을 반환합니다: 방이 겹치면 true, 안 겹치면 false입니다. 우리는 그 값을 사용하여 방금 배치하려고 한 방에 무엇을 할지 결정할 수 있습니다.

1

	private function placeRooms() {

2

		// create array for room storage for easy access

3

		rooms = new Array();

4

5

		// randomize values for each room

6

		for (r in 0...maxRooms) {

7

			var w = minRoomSize + Std.random(maxRoomSize - minRoomSize + 1);

8

			var h = minRoomSize + Std.random(maxRoomSize - minRoomSize + 1);

9

			var x = Std.random(MAP_WIDTH - w - 1) + 1;

10

			var y = Std.random(MAP_HEIGHT - h - 1) + 1;

11

12

			// create room with randomized values

13

			var newRoom = new Room(x, y, w, h);

14

15

			var failed = false;

16

			for (otherRoom in rooms) {

17

				if (newRoom.intersects(otherRoom)) {

18

					failed = true;

19

					break;

20

				}

21

			}

22

			if (!failed) {

23

				// local function to carve out new room

24

				createRoom(newRoom);

25

26

				// push new room into rooms array

27

				rooms.push(newRoom)

28

			}

29

		}

30

	}

여기서 핵심은 failed Boolean 값입니다; 이것은 intersects()의 반환값으로 설정되며 방이 겹칠 때에만 true입니다. 루프를 빠져나가면 이 failed 변수를 확인하고 false라면 새 방을 만들 수 있습니다. 그렇지 않으면 방을 버리고 최대 개수의 방이 될 때까지 재시도합니다.

도달 불가능한 컨텐츠를 어떻게 다루어야 할까요?

절차적으로 생성된 콘텐츠를 사용하는 대다수의 게임은 플레이어가 모든 컨텐츠에 도달 가능하도록 하려고 하지만, 이것이 최고의 디자인적인 결정에 필수적인게 아니라고 믿는 사람이 몇몇 있습니다. 던전 내에 플레이어는 접근하기가 거의 불가능하지만 언제나 볼 수 있는 방이 있다면 어떨까요? 이것은 던전에 흥미로운 것을 추가할 수 있습니다.

당연히 논쟁의 어느 쪽이든지간에 플레이어가 항상 게임을 진행할 수 있도록 확인하는 것이 좋습니다. 게임 던전의 레벨에 도달하고 출구가 막혀있다면 꽤 좌절스러울 것입니다.

대부분의 게임이 100% 도달 가능한 컨텐츠를 고려하므로 우리는 그것에 충실할 것입니다.

도달 여부를 다루어 봅시다

지금까지는 타일 맵을 만들고 다양한 숫자의 방을 다양한 크기로 만들고 배치하는 코드가 있었습니다. 이미 절차적으로 생성된 던전 방을 가지고 있습니다.

이제 목표는 각 방을 연결하여 던전을 통과하면서 결국엔 다음 레벨로 이어지는 출구에 도착할 수 있도록 하는 것입니다. 우리는 방 사이의 복도를 만들어 이를 수행할 수 있습니다.

생성된 각 방의 중앙을 추적기 위해 코드에 point 변수를 추가해야 할 것입니다. 방을 만들고 배치할 때마다 중심을 결정하고 이전 방의 중앙와 연결합니다.

우선 복도를 구현합니다:

1

private function hCorridor(x1:Int, x2:Int, y) {

2

		for (x in Std.int(Math.min(x1, x2))...Std.int(Math.max(x1, x2)) + 1) {

3

			// destory the tiles to "carve" out corridor

4

			map[x][y].parent.removeChild(map[x][y]);

5

6

			// place a new unblocked tile

7

			map[x][y] = new Tile(Tile.DARK_GROUND, false, false);

8

9

			// add tile as a new game object

10

			addChild(map[x][y]);

11

12

			// set the location of the tile appropriately

13

			map[x][y].setLoc(x, y);

14

		}

15

	}

16

17

	// create vertical corridor to connect rooms

18

	private function vCorridor(y1:Int, y2:Int, x) {

19

		for (y in Std.int(Math.min(y1, y2))...Std.int(Math.max(y1, y2)) + 1) {

20

			// destroy the tiles to "carve" out corridor

21

			map[x][y].parent.removeChild(map[x][y]);

22

23

			// place a new unblocked tile

24

			map[x][y] = new Tile(Tile.DARK_GROUND, false, false);

25

26

			// add tile as a new game object

27

			addChild(map[x][y]);

28

29

			// set the location of the tile appropriately

30

			map[x][y].setLoc(x, y);

31

		}

32

	}

이 함수들은 거의 같은 방식으로 작동하지만 하나는 수평, 다른 하나는 수직으로 생성합니다.

이를 위해서는 세가지 값이 필요합니다. 수평 복도의 경우 시작 x 값, 종료 x 값, 현재 y값이 필요합니다.  수직 복도의 경우 시작 y값, 종료 y값, 현재 x값이 필요합니다.

왼쪽에서 오른쪽으로 이동하므로 상응하는 두개의 x 값이 필요하지만 위나 아래로는 움직이지 않으므로 y 값은 하나만 필요합니다. 수직으로 움직일 때 y 값이 필요합니다. 각 함수의 시작 지점에 있는 for 루프 내에서 전체 복도를 생성할 때까지 시작 값 (x나 y)부터 종료 값까지를 반복합니다.

이제 복도 코드가 완성되었으니 placeRooms() 함수를 변경하고 새로운 복도 함수를 호출할 수 있습니다.

1

	private function placeRooms() {

2

	// store rooms in an array for easy access

3

	rooms = new Array();

4

5

	// variable for tracking center of each room

6

	var newCenter = null;

7

8

	// randomize values for each room

9

	for (r in 0...maxRooms) {

10

		var w = minRoomSize + Std.random(maxRoomSize - minRoomSize + 1);

11

		var h = minRoomSize + Std.random(maxRoomSize - minRoomSize + 1);

12

		var x = Std.random(MAP_WIDTH - w - 1) + 1;

13

		var y = Std.random(MAP_HEIGHT - h - 1) + 1;

14

15

		// create room with randomized values

16

		var newRoom = new Room(x, y, w, h);

17

18

		var failed = false;

19

		for (otherRoom in rooms) {

20

			if (newRoom.intersects(otherRoom)) {

21

				failed = true;

22

				break;

23

			}

24

		}

25

		if (!failed) {

26

			// local function to carve out new room

27

			createRoom(newRoom);

28

29

			// store center for new room

30

			newCenter = newRoom.center;

31

32

			if(rooms.length != 0){

33

				// store center of previous room

34

				var prevCenter = rooms[rooms.length - 1].center;

35

36

				// carve out corridors between rooms based on centers

37

				// randomly start with horizontal or vertical corridors

38

				if (Std.random(2) == 1) {

39

					hCorridor(Std.int(prevCenter.x), Std.int(newCenter.x),

40

						Std.int(prevCenter.y));

41

					vCorridor(Std.int(prevCenter.y), Std.int(newCenter.y),

42

						Std.int(newCenter.x));

43

				} else {

44

					vCorridor(Std.int(prevCenter.y), Std.int(newCenter.y),

45

						Std.int(prevCenter.x));

46

					hCorridor(Std.int(prevCenter.x), Std.int(newCenter.x),

47

						Std.int(newCenter.y));

48

					}

49

				}

50

			}

51

		if(!failed) rooms.push(newRoom);

52

		}

53

	}

위의 이미지에서는 첫번째부터 네번째 방까지 빨강, 초록, 파랑 순으로 복도를 만들었습니다. 방 배치에 따라 흥미로운 결과를 얻을 수도 있습니다 - 예를 들어 서로 옆에 있는 두 개의 복도는 두배 넓은 복도를 만듭니다.

우리는 각 방의 중심을 추적하기 위해 변수를 추가했고 두 방의 중심에 복도를 연결했습니다. 이제 겹치지 않는 여러 개의 방과 모든 던전 레벨을 연결하는 복도가 있습니다. 나쁘지 않네요.

던전을 완성시켰습니다. 그렇죠?

처음 절차적으로 생성된 던전 레벨을 만들기 위해 먼 길을 왔습니다. 저는 여러분이 PCG가 절대 죽일 가능성이 없는 마법의 짐승같은 것이 아니라는 것을 깨닫길 바랍니다.

우리는 단순한 난수 생성기로 던전 레벨 주위에 랜덤하게 컨텐츠를 배치하는 방법과 컨텐츠를 적절한 사이즈로 유지하고 적절한 위치에 유지하는데 필요한 몇가지 미리 지정된 범위에 대해 살펴보았습니다. 다음으로 겹치는 방을 확인하여 랜덤한 배치가 말이 되는지 확인하는 아주 간단한 방법을 발견했습니다. 마지막으로 컨텐츠를 도달가능하게 유지하는 장점에 대해 잠시 이야기했고, 플레이어가 던전의 모든 방에 도달할 수 있도록 하는 방법을 발견했습니다.

4단계 과정 중 처음의 세 단계가 완료되었으며, 이는 다음 게임을 위한 멋진 던전의 빌딩 블록이 있다는 것을 의미합니다. 마지막 단계는 당신에게 달려있습니다: 끝없는 리플레이성을 위해 절차적으로 생성된 컨텐츠를 생성하는 방법에 대해 배운 것을 반복해나가야 합니다.

언제나 배울 것은 더 많습니다

이 튜토리얼에서 간단한 던전을 구성하는 메소드는 PCG의 표면을 긁는 정도이며 당신이 쉽게 선택할 수 있는 다른 간단한 알고리즘이 있습니다.

여러분을 위한 저의 도전과제는 여기서 만든 게임의 시작에 대해 실험해보고 던전을 변경하기 위해 더 많음 메소드를 연구해보는 것입니다.

동굴 레벨을 만드는 좋은 방법 중 하나는 셀룰러 오토마타를 사용하는 것입니다. 이것은 던전 레벨을 커스터마이즈할 수 있는 무한의 가능성을 가집니다. 다른 좋은 메소드는 바이너리 공간 파티셔닝(BSP; Binary Space Partitioning)입니다. 이것은 격자 형태의 던전 레벨을 만듭니다.

나는 이것이 당신에게 절차적 컨텐츠 생성의 좋은 시작이 되었기를 바랍니다. 여러분이 가진 질문을 코멘트로 달아주시고, 여러분이 PCG로 만든 예제를 한번 봤으면 좋겠네요.