Binary Tree 미로 생성 알고리즘

전체 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    class Board
    {
        public enum TileType
        {
            Empty, // 빈 공간
            Wall,  // 벽
        }
        const char CIRCLE = '\u25cf'; // 유니코드 문자로 ● (검은색 원)을 출력하기 위한 상수. 맵 타일을 표시하는 데 사용됨.
        public TileType[,] _tile; // 2차원 배열로 맵의 각 타일의 상태를 저장.
        public int _size; // 맵의 크기. NxN 크기를 나타냄.
                          // 맵 초기화 메서드. 맵의 크기를 받아 타일을 생성하고 초기화.
        public void Initialize(int size)
        {
            if (size % 2 == 0)
            {
                return;
            }

            _tile = new TileType[size, size]; // 맵의 크기(size x size)만큼의 2차원 배열 생성.
            _size = size; // 맵 크기 설정.

            GenrateByBinaryTree();
        }
        public void GenrateByBinaryTree()
        {
            // mazes for Programmers
            // Binary Tree Algorithm
            // 길을 다 막는 작업
            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 (y == _size - 2 && x == _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;
                    }
                }
            }
        }
        // 맵을 화면에 출력하는 메서드.
        public void Render()
        {
            ConsoleColor prevColor = Console.ForegroundColor; // 현재 콘솔의 글자색을 저장.
            for (int y = 0; y < _size; y++) // 행 순회.
            {
                for (int x = 0; x < _size; x++) // 열 순회.
                {
                    Console.ForegroundColor = GetTileColor(_tile[y, x]); // 현재 타일의 색을 설정.
                    Console.Write(CIRCLE); // ● 문자 출력.
                }
                Console.WriteLine(); // 한 행이 끝나면 다음 줄로 이동.
            }
            Console.ForegroundColor = prevColor; // 이전 색상으로 복원.
        }

        // 타일의 종류에 따라 콘솔 글자색을 반환하는 메서드.
        ConsoleColor GetTileColor(TileType type)
        {
            switch (type)
            {
                case TileType.Empty:
                    return ConsoleColor.Green; // 빈 공간은 초록색.
                case TileType.Wall:
                    return ConsoleColor.Red; // 벽은 빨간색.
                default:
                    return ConsoleColor.Green; // 기본값으로 초록색 반환.
            }
        }
    }
}

1. 미로 초기화 - 모든 길을 막기

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; // 홀수 좌표는 이동 가능한 타일로 설정
    }
}

📌 설명

• _size 크기의 2차원 배열을 만든 후, 모든 셀을 벽(TileType.Wall)으로 설정합니다.
• (x, y) 좌표에서 x 또는 y가 짝수일 경우 벽으로 설정합니다.
• 홀수 좌표만 길(TileType.Empty)이 될 수 있도록 설정합니다.

---

2. 길 뚫기 (Binary Tree 방식)

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)  
        {
            _tile[y, x + 1] = TileType.Empty;  // 오른쪽 벽을 길로 뚫기
        }
        else
        {
            _tile[y + 1, x] = TileType.Empty;  // 아래쪽 벽을 길로 뚫기
        }
    }
}

📌 설명

• (홀수 좌표 기준으로만 진행)
• (x, y)가 홀수인 경우에만 실행
• rand.Next(0, 2)을 사용하여 50% 확률로 오른쪽 또는 아래쪽 벽을 제거
  • 0이면 오른쪽 벽(x+1)을 제거
  • 1이면 아래쪽 벽(y+1)을 제거
• 미로는 좌측 상단에서 시작하여 우측 하단 방향으로 점진적으로 확장됨

---

3. 미로 가장자리 처리

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; // 아래쪽 벽 뚫기
        }
    }
}

📌 설명

• 가장자리를 벽으로 유지하는 로직 추가
  • (x == _size - 2 && y == _size - 2) → 오른쪽 아래 코너에서는 아무 처리도 하지 않음
  • (y == _size - 2) → 아래쪽 가장자리에 있는 경우 오른쪽 벽만 뚫음
  • (x == _size - 2) → 오른쪽 가장자리에 있는 경우 아래쪽 벽만 뚫음
  • 이 처리를 통해 가장자리는 항상 벽으로 유지됨

---

4. 미로 크기 제한 (홀수 크기)

public void Initialize(int size)
{
    if (size % 2 == 0)
        return; // 미로 크기는 홀수여야 함
}

📌 설명

• 미로 크기는 반드시 홀수여야 합니다.
• 이유:
  • 짝수 크기일 경우 경계선이 유지되지 않으며, 랜덤한 벽 제거가 비대칭적으로 이루어질 수 있음.
  • 홀수 크기를 사용하면 경계 벽이 유지되면서도 미로 내부의 길이 균형 있게 생성됨.

---

🚀 Binary Tree 미로 알고리즘 특징

✅ 간단한 구현
✅ 길을 랜덤하게 확장
✅ 모든 칸을 방문하는 보장된 경로 생성
❌ 비효율적인 탐색 (백트래킹이 없어서, 다소 단순한 미로 구조 생성)
❌ 우상향 편향 (경로가 오른쪽/아래쪽으로만 확장됨)

---