Part 2-3-2. 미로 준비 : 미로 생성 알고리즘 (Binary Tree, Side Winder)

공부/인프런 - Rookiss

Part 2-3-2. 미로 준비 : 미로 생성 알고리즘 (Binary Tree, Side Winder)

셩잇님 2023. 8. 4. 15:12

미로 준비

가장 자리만 벽으로 하는 것이 아닌, 진짜 미로처럼 벽을 배치해 보자.
미로 생성 알고리즘 👉 Binary Tree, Side Winder 두개 말고도 많지만 이 두개만 배운다.

[BinaryTree 방식의 미로]

1️⃣ 가장 자리는 모두 갈 수 없는 벽으로 지정

        public void Initialize(int size)
        {
            _tile = new TileType[size, size];
            _size = size;

            for (int y = 0; y < _size; y++)
            {
                for (int x = 0; x < _size; x++)
                {
                    if (x == 0 || x == _size - 1 || y == 0 || y == size - 1)
                        _tile[y, x] = TileType.Wall;
                    else
                        _tile[y, x] = TileType.Empty;
                }
            }
        }

2️⃣ 짝수번 째 타일은 모두 벽으로 만든다.

        public void Initialize(int size)
        {
            _tile = new TileType[size, size];
            _size = size;

             // 미로 만들기 전, 길을 다 막아버리는 작업
            for (int y = 0; y < _size; y++)
            {
                for (int x = 0; x < _size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0 )
                        _tile[y, x] = TileType.Wall;
                    else
                        _tile[y, x] = TileType.Empty;
                }
            }
        }

이렇게 하면 벽이 아닌 곳(초록 타일들)은 모두 사방의 벽으로 둘러 싸이게 된다. 가장 자리 1️⃣ 도 다 벽으로 막힘 (짝수니까) 이 상태에서 초록 타일을 기준으로 오른쪽 혹은 아래쪽으로 랜덤하게 둘 중 하나의 방향이 있는 벽을 초록색으로 만들어 뚫어 줄 것이다.

[Binary Tree 알고리즘]
갈 수 있는 타일 하나의 입장에서 오른 쪽, 아래 쪽 2 개의 벽 중 하나를 랜덤하게 선택하여 갈 수 있는 타일로서 바꿔준다. 즉, 랜덤하게 두 방향 중 하나를 선택해 길을 뚫어 준다.

            // 미로 만들기 전, 길을 다 막아버리는 작업
            for (int y = 0; y < _size; y++)
            {
                for (int x = 0; x < _size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0 )
                        _tile[y, x] = TileType.Wall;
                    else
                        _tile[y, x] = TileType.Empty;
                }
            }

            // 길을 반반 확률로 뚫는 작업
            Random rand = new Random();
            for (int y = 0; y < _size; y++)
            {
                for (int x = 0; x < _size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        continue;
                    if(rand.Next(0, 2) == 0)  // 0, 1 중 랜덤하게 하나를 뽑음
                    {
                        _tile[y, x + 1] = TileType.Empty;  // 오른쪽 뚫기
                    }
                    else
                    {
                        _tile[y + 1, x] = TileType.Empty;  // 아래 뚫기
                    }
                }
            }

갈 수 있는 타일을 기준으로 하여 오른쪽 아래쪽 벽을 선택 하여 둘 중 하나를 더 이상 벽이 아닌 갈 수 있는 길로서 바꿔 준다. 짝수 행, 짝수 열인 타일은 벽이므로 continue 👉 갈 수 있는 타일의 기준에서 선택해야 하므로.

0, 1 중 랜덤하게 0 을 뽑았다면 👉 현재 타일의 기준에서 오른쪽 벽을 갈 수 있는 길로 뚫는다.

_tile[y, x + 1] = TileType.Empty;

0, 1 중 랜덤하게 1 을 뽑았다면 👉현재 타일의 기준에서 아래 쪽 벽을 갈 수 있는 길로 뚫는다.

_tile[y, x + 1] = TileType.Empty;

완성된 미로

        public void Initialize(int size)
        {
            if (size % 2 == 0)
                return;

바이너리 한 작업이고 가장 자리는 항상 벽이어야 하므로 미로의 크기는 홀수여야 한다. 따라서 미로의 크기가 짝수로 입력 됐다면 Initialize(int size) 함수 그냥 처음부터 종료 시킴.

가장 자리는 항상 벽이어야 한다. 따라서 오른쪽 흰색 선에 위치한 길(x == _size - 2)들은 오른쪽 벽을 길로 뚫어선 안되며, 아래쪽 흰색 선에 위치한 길 (y == _size - 2)들은 아래쪽 벽을 길로 뚫어선 안된다.

            // 길을 반반 확률로 뚫는 작업
            Random rand = new Random();
            for (int y = 0; y < _size; y++)
            {
                for (int x = 0; x < _size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        continue;

                    if (x == _size - 2 && y == _size - 2)
                        continue;

                    if (y == _size - 2)
                    {
                        _tile[y, x + 1] = TileType.Empty;
                        continue;
                    }

                    if (x == _size - 2)
                    {
                        _tile[y + 1, x] = TileType.Empty;
                        continue;
                    }

                    if (rand.Next(0, 2) == 0)
                    {
                        _tile[y, x + 1] = TileType.Empty;  // 오른쪽 뚫기
                    }
                    else
                    {
                        _tile[y + 1, x] = TileType.Empty;  // 아래 뚫기
                    }
                }
            }

위처럼 코딩해주니 오른쪽, 아래쪽 가장자리가 이제 뚫리지 않고 전부 벽으로 막히는 것을 확인할 수 있다.

// 오른쪽 벽이 가장 자리이고 동시에 아래 쪽 벽도 가장자리일 경우엔
// 아무런 처리도 하지 않도록 continue
if (x == _size - 2 && y == _size - 2)
    continue;

// 아래쪽 벽이 가장 자리인 경우엔
// 아래쪽 벽을 뚫지 않도록 오른쪽 벽을 뚫도록 한 후 continue
if (y == _size - 2)
{
    _tile[y, x + 1] = TileType.Empty;
    continue;
}

// 오른쪽 벽이 가장 자리인 경우엔
// 오른쪽 벽을 뚫지 않도록 아래쪽 벽을 뚫도록 한 후 continue
if (x == _size - 2)
{
    _tile[y + 1, x] = TileType.Empty;
    continue;
}

[Side Winder 알고리즘]

        void GenerateBySideWinder()
        {
            // 길을 다 막아버리는 작업
            for (int y = 0; y < _size; y++)
            {
                for (int x = 0; x < _size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        _tile[y, x] = TileType.Wall;
                    else
                        _tile[y, x] = TileType.Empty;
                }
            }

            // 길을 반반 확률로 뚫는 작업
            Random rand = new Random();
            for (int y = 0; y < _size; y++)
            {
                int count = 1;  // 연속해서 몇 개의 오른쪽 벽을 길로 뚫었는지
                for (int x = 0; x < _size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        continue;

                    if (x == _size - 2 && y == _size - 2)
                        continue;

                    if (y == _size - 2)
                    {
                        _tile[y, x + 1] = TileType.Empty;
                        continue;
                    }

                    if (x == _size - 2)
                    {
                        _tile[y + 1, x] = TileType.Empty;
                        continue;
                    }

                    if (rand.Next(0, 2) == 0)
                    {
                        _tile[y, x + 1] = TileType.Empty;  // 오른쪽 뚫기
                        count++;
                    }
                    else
                    {
                        int randomIndex = rand.Next(0, count);
                        _tile[y + 1, x - randomIndex * 2] = TileType.Empty;  // 아래 뚫기
                        count = 1;
                    }
                }
            }
        }

        int count = 1;  // 연속해서 몇 개의 오른쪽 벽을 길로 뚫었는지
        // ...

                    if (rand.Next(0, 2) == 0)
                    {
                        _tile[y, x + 1] = TileType.Empty;  // 오른쪽 뚫기
                        count++;
                    }
                    else
                    {
                        int randomIndex = rand.Next(0, count);  // 0 ~ (count - 1) 에서 랜덤한 정수 뽑기
                        _tile[y + 1, x - randomIndex * 2] = TileType.Empty;  // 아래 뚫기
                        count = 1;
                    }

아래를 뚫어야 하면 해당 타일의 아래 벽을 뚫는 것이 아니라, 오른쪽으로 연속되어 뚫어왔던 벽들 중에서 랜덤으로 하나를 선택한 타일의 아래 벽을 뚫는다.

오른쪽을 뚫기로 했을 땐 count를 증가시킨다.
초기값은 1이며, 연속으로 몇 개의 오른쪽 벽을 뚫었는지를 담게 된다.

아래쪽을 뚫기로 했을 땐 👉 여태까지 오른쪽 벽을 뚫기로 결정해 왔던 초록 타일 중에서 랜덤하게 하나를 선태갛여 그 타일의 아래 벽을 뚫는다.

미로 만들기 전부터 초록색이었던, 즉 벽을 뚫는 기준이 되는 초록 타일들은 벽 하나를 두고 띄엄 띄엄 있으므로 x - randomIndex * 2 열에 위치한 타일의 y + 1 아래 벽을 뚫으면 된다.
count는 다시 1 로 초기화. 지금부터 다시 셈.

그 외의 작업은 다 Binary Tree 알고리즘과 동일

Binary Tree 알고리즘 방식을 베이스로 하여, 아래를 뚫을 땐 랜덤하게 또 고른다는 방식이 추가된 것 같다.

[두 알고리즘의 장/단점]

장점
간단하다. 그저 둘 중 하나를 선택.

단점

모양이 치우쳐진다.

가장 자리를 벽으로 보장하기 위하여 오른쪽 벽이 가장 자리이면 아래 쪽을 뚫고, 혹은 아래 쪽 벽이 가장자리일 경우엔 오른쪽 벽을 뚫기 때문에 x == _size - 2 혹은 y == _size - 2 에 해당하는 타일들은 항상 전부 길로 뚫리는 모양의 미로가 나오게 된다.

'공부 > 인프런 - Rookiss' 카테고리의 다른 글

Part 2-3-4. 미로 준비 : 오른손 법칙 (0)	2023.08.04
Part 2-3-3. 미로 준비 : 플레이어 이동 (0)	2023.08.04
Part 2-3-1. 미로 준비 : 맵 만들기 (0)	2023.08.04
Part 2-2-1. 선형 자료 기초 : 배열, 동적 배열, 연결 리스트 비교 및 구현 (0)	2023.08.04
Part 2-1-2. 환경 설정 (0)	2023.08.04

현재글Part 2-3-2. 미로 준비 : 미로 생성 알고리즘 (Binary Tree, Side Winder)

셩잇님의 잡동사니