[C#, Unity, 절차적 생성] Recursive Backtracking 알고리즘을 사용한 절차적 미로 생성

■ Recursive Backtracking

Recursive Backtracking은 말 그대로,

1. 재귀(Recursive) 적으로 경로를 탐색하고,
2. 백트래킹(Backtracking), 즉 더 이상 갈 수 없을 때 되돌아가며 다른 경로를 찾는 알고리즘이다.

 

🛠️ 알고리즘 핵심 구조

[과정 - 1]

먼저 임의의 시작 위치로부터 랜덤한 방향을 선택해 두 칸 떨어진 타일로 이동할 수 있는지 확인한다. 이때, 중간에 있는 벽을 허물고 다음 타일까지 길을 만든다.

 

여기서 “두 칸 이동”이 핵심이다. 만약 인접한 타일(1칸 거리)을 곧바로 길로 만든다면, 그 셀이 이미 길인지 아닌지를 구분할 수 없어 모든 타일이 길인 허술한 미로가 만들어진다.

 

• 미로의 구조는 항상 [길] → [벽] → [길] 순서를 따른다.
• 따라서 길을 만들 땐, 중간의 벽을 먼저 허물고 그 다음 셀로 이동해야 한다.

 

[과정 - 2]

새로운 길이 만들어지면, 현재 위치와 다음 위치를 스택에 쌓는다. 그 후, 스택에서 가장 위의 셀을 꺼내 동일한 과정을 반복한다.

• 만약 어떤 위치(B)에서 더 이상 길을 만들 수 없다면, 자연스럽게 이전 위치(S)로 되돌아가 다른 방향을 탐색하게 된다.

이렇게 되돌아가는 과정이 바로 Backtracking이다. 스택이 비게 되면 더 이상 확장할 수 있는 길이 없다는 뜻이고 미로 생성이 완료된다.

 

■ 구현

구현 단계 정리

1. 랜덤한 시작 지점을 선택하여 stack에 삽입한다.
2. stack에서 요소를 꺼냄.
3. 현재 위치에서 랜덤한 방향을 선택하여, 두 칸 건너 뛴 위치가 “길”이 될 수 있는지 확인한다. 3-2. 길을 만들 수 없다면 아래 과정은 건너뛰고 다음 반복으로 넘어간다.
4. 3-1. 길을 만들 수 있다면, 중간의 벽을 허물고 다음 위치까지 통로를 생성한다.
5. 현재 위치와 새 위치를 stack에 삽입한다.
6. stack이 빌 때까지 2~4번의 과정을 반복한다.

알고리즘 자체는 비교적 간단하므로, 필요 변수 선언(1)까지만 참고하고, 나머지는 직접 구현해보는 것을 추천한다.

 

1. 필요 변수 선언

private int[,] SetTileArray()
{
    var tile = new int[height, width];
    var stack = new Stack<(int, int)>();
    
    stack.Push(GetRandomPosition());

    while (stack.Count > 0)
    {

    }

    return tile;
}

타일 정보를 저장할 2차원 배열과 경로 생성을 위한 스택을 선언한다. 그리고 랜덤 위치를 골라 스택에 삽입하며, 이후 과정은 DFS 방식으로 진행된다.

private (int, int) GetRandomPosition()
{
    var pos = (0, 0);

    pos.Item1 = Random.Range(0, (height - 1) / 2) * 2 + 1;
    pos.Item2 = Random.Range(0, (width - 1) / 2) * 2 + 1;

    return pos;
}

위 코드는 랜덤한 시작 위치를 구하는 함수이다. 시작 위치는 반드시 홀수 인덱스여야 하며, 그 이유는 다음과 같다:

• 미로 생성 시, 짝수 인덱스는 벽, 홀수 인덱스는 길로 사용하여 [길] → [벽] → [길] 구조를 유지한다.
• 홀수 인덱스만 길로 설정하면,가장자리는 자동으로 벽으로 둘러싸이게 되어 별도의 가장자리 처리가 필요 없다.

 

2. 임의의 방향 선택

var pos = stack.Pop();
tile[pos.Item1, pos.Item2] = 1;

var nextPos = GetNextPosition(tile, pos);

if (nextPos.Item1 == -1)
{
    continue;
}

stack.Push(pos);
stack.Push(nextPos);

스택에서 타일을 꺼내 해당 위치를 길로 지정하고, 랜덤한 방향을 탐색하여 다음 경로를 결정한다.

private readonly int[] _dx = new[] { 0, 0, -2, 2 };
private readonly int[] _dy = new[] { -2, 2, 0, 0 };

private (int, int) GetNextPosition(int[,] tile, (int, int) pos)
{
    var land = new[] { 0, 1, 2, 3 };
    land = land.OrderBy(_ => Random.value).ToArray();

    foreach (var index in land)
    {
		    // 이동할 위치 계산
        var nextY = pos.Item1 + _dy[index];
        var nextX = pos.Item2 + _dx[index];
	
				// 범위 및 방문 여부 확인
        if (nextY < 1 || nextY >= height - 1 ||
            nextX < 1 || nextX >= width - 1 ||
            tile[nextY, nextX] == 1)
        {
            continue;
        }

				// 사이의 벽 위치 계산 후 허물기
        var wallY = (pos.Item1 + nextY) / 2;
        var wallX = (pos.Item2 + nextX) / 2;

        tile[wallY, wallX] = 1;
        
        // 다음 위치 반환
        return (nextY, nextX);
    }

    return (-1, -1);
}

랜덤한 방향을 탐색하고, 두 칸 떨어진 셀에 길을 만들 수 있는지 판단하여 조건을 만족하면 그 사이의 벽을 허물고 해당 위치를 반환한다.

• 먼저, 상(0), 하(1), 좌(2), 우(3) 순으로 정의된 배열을 랜덤하게 섞는다.
• 이후 다음 순서로 탐색을 진행한다.

1. 이동할 위치를 계산한다.
2. 해당 위치가 미로 범위 내에 있고, 아직 길이 아니면 조건 통과.
3. 현재 위치와 다음 위치 사이의 벽 위치를 계산하고 벽을 제거한다.
4. 새 위치를 반환한다.

[길과 길 사이의 벽 위치]

우리는 길과 길 사이의 벽을 허물기 위해, 이 벽의 위치를 계산해야 한다.

$$ x' = \frac{x_1 + x_2}{2} \ \ y' = \frac{y_1 + y_2}{2} $$

• 시작 위치 $(y_1, x_1) = (4,2)$
• 새 위치 $(y_2, x_2) = (2,2)$ 라면,
• 벽의 위치는 $(y',x') = (3,2)$가 된다.

stack.Push(pos);
stack.Push(nextPos);

마지막으로 시작 위치와 새 위치를 스택에 넣어주면 된다.

 

■ 전체 코드

private readonly int[] _dx = new[] { 0, 0, -2, 2 };
private readonly int[] _dy = new[] { -2, 2, 0, 0 };

private int[,] SetTileArray()
{
    var tile = new int[height, width];
    var stack = new Stack<(int, int)>();

    stack.Push(GetRandomPosition());

    while (stack.Count > 0)
    {
        var pos = stack.Pop();
        tile[pos.Item1, pos.Item2] = 1;

        var nextPos = GetNextPosition(tile, pos);

        if (nextPos.Item1 == -1)
        {
            continue;
        }

        stack.Push(pos);
        stack.Push(nextPos);
    }

    return tile;
}

private (int, int) GetNextPosition(int[,] tile, (int, int) pos)
{
    var land = new[] { 0, 1, 2, 3 };
    land = land.OrderBy(_ => Random.value).ToArray();

    foreach (var index in land)
    {
        var nextY = pos.Item1 + _dy[index];
        var nextX = pos.Item2 + _dx[index];

        if (nextY < 1 || nextY >= height - 1 ||
            nextX < 1 || nextX >= width - 1 ||
            tile[nextY, nextX] == 1)
        {
            continue;
        }

        var wallY = (pos.Item1 + nextY) / 2;
        var wallX = (pos.Item2 + nextX) / 2;

        tile[wallX, wallY] = 1;
        return (nextY, nextX);
    }

    return (-1, -1);
}

private (int, int) GetRandomPosition()
{
    var pos = (0, 0);

    pos.Item1 = Random.Range(0, (height - 1) / 2) * 2 + 1;
    pos.Item2 = Random.Range(0, (width - 1) / 2) * 2 + 1;

    return pos;
}