binary-tree-algorithm.md

Binary Tree Algorithm

이 알고리즘은 방마다 오른쪽 혹은 아래쪽을 뚫어서 미로를 만드는 알고리즘이다.

그리드

미로를 만들기 위해 먼저 그리드 모양의 맵을 만든다. 미로는 반드시 홀수 x 홀수 크기여야 한다. 짝수로 하게 된다면, 마지막 줄이 벽으로 막히지 않고 방이 테두리에 그대로 드러난다.

public enum TileType
{
    Empty,
    Wall,
}

class Board
{
    public TileType[,] Tile { get; private set; }
    public int Size { get; private set; }

    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;
                }
            }
        }
    }
}

Tile[y, x] 가 Wall 이면 벽이고 Empty 면 지나갈 수 있는 칸이다. x 나 y 중 하나라도 짝수면 벽이 되므로, 둘 다 홀수인 칸만 방으로 설정된다. x 가 커질수록 오른쪽, y 가 커질수록 아래쪽이다. Tile[1, 1] 이 왼쪽 위 구석의 방이다.


벽 뚫기

방을 하나씩 돌면서 랜덤으로 오른쪽 혹은 아래쪽 벽을 뚫는다. x 나 y 가 짝수인 칸은 벽이므로 건너뛴다.

private void GenerateBinaryTree()
{
    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) // current is wall. skip.
            {
                continue;
            }

            // dig the right side.
            if (rand.Next(0, 2) == 0)
            {
                Tile[y, x + 1] = TileType.Empty;
            }
            // dig the bottom.
            else
            {
                Tile[y + 1, x] = TileType.Empty;
            }
        }
    }
}

가장자리

위와 같이 모든 방에서 벽 뚫기를 시도하면, 맨 오른쪽 줄의 방 또는 맨 아랫줄의 방이 뚫려 미로 바깥과 이어진다. 가장자리에 있는 방들은 뚫을 방향을 정해 둬야 한다. Size 가 25라면 마지막 칸 번호는 24이고 그 칸은 테두리 벽이다. 마지막 방의 번호는 Size - 2 인 23이다.

private void GenerateBinaryTree()
{
    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) // current is wall. skip.
            {
                continue;
            }

            if (y == Size - 2 && x == Size - 2) // current is destination. skip.
            {
                continue;
            }

            if (y == Size - 2) // dig only the right side
            {
                Tile[y, x + 1] = TileType.Empty;
                continue;
            }

            if (x == Size - 2) // dig only the bottom
            {
                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;
            }
        }
    }
}

맵을 만든 뒤에 GenerateBinaryTree 함수를 호출한다.

public void Initialize(int size)
{
    Tile = new TileType[size, size];
    Size = size;

    // ... fill walls

    GenerateBinaryTree();
}

출력

private const char SQUARE = '■';

public void Render()
{
    ConsoleColor origin = Console.ForegroundColor;

    for (int y = 0; y < Size; y++)
    {
        for (int x = 0; x < Size; x++)
        {
            Console.ForegroundColor = Tile[y, x] == TileType.Wall ? ConsoleColor.Green : ConsoleColor.DarkGray;
            Console.Write($"{SQUARE} ");
        }
        Console.WriteLine();
    }

    Console.ForegroundColor = origin;
}
Board board = new Board();
board.Initialize(25);
board.Render();

특징