미로 생성 알고리즘(Binary Tree, Sidewinder)

본 미로 생성 알고리즘 아이디어는 http://www.jamisbuck.org/mazes/ 블로그에 있습니다.

 

미로를 만들기 전 준비단계

미로를 만들기 전에는 벽으로 둘러싸인 격자 Grid를 만들어야 합니다.
여기서 초록색은 갈 수 있는 부분 빨간색은 벽을 말합니다.

void InitBoard()
{
    // 일단 길을 다 막아버림
    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 Algorithm

해당 알고리즘은 미로 생성 알고리즘 중 가장 간단합니다.
이름에서 알 수 있듯이 각 스텝마다 가능한 2가지의 옵션(아래 혹은 오른쪽으로 길을 틈) 중 랜덤으로 선택합니다.
이 방법을 맨 끝줄까지 반복한다면 미로가 완성됩니다.

[ Binary Tree Algorithm ] 코드 구현

public enum Direction
{
    DOWN = 0,
    RIGHT,
}

void GeneratedByBinaryTree()
{
    // 랜덤으로 우측 혹은 아래로 길을 뚫음
    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 (x == _size - 2)
            {
                _tile[y + 1, x] = TileType.Empty;
                continue;
            }

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

            else
            {
                Direction dir = (Direction)rand.Next(0, 2);
                switch (dir)
                {
                    case Direction.DOWN: // 아래
                        _tile[y + 1, x] = TileType.Empty;
                        break;
                    case Direction.RIGHT: // 우측
                        _tile[y, x + 1] = TileType.Empty;
                        break;
                }
            }
        }
    }
}

Binary Tree Algorithm으로 만들어진 미로 - 한쪽으로 치우친 것을 볼 수 있다.

 

2. Sidewinder Algorithm

해당 알고리즘도 미로 생성 알고리즘 중 가장 간단합니다.
이 알고리즘은 위에서 설명한 Binary Tree 알고리즘과 비슷합니다.

Binary Tree 알고리즘처럼 각 스텝마다 가능한 2가지의 옵션(아래 혹은 오른쪽으로 길을 틈) 중 랜덤으로 선택합니다.
오른쪽으로 연속 이동한 횟수를 Count하여 오른쪽 이동 중 아래로 이동하는 옵션이 선택되면 오른쪽 연속으로 이동한  Cell 중 랜덤으로 선택하여 그 Cell에서 아래로 길을 틉니다.
이 방법을 맨 끝줄까지 반복한다면 미로가 완성됩니다.

Sidewinder Algorithm에 대한 설명

[ Sidewinder Algorithm ] 코드 구현

void CreatedBySideWinder()
{
    // 랜덤으로 우측 혹은 아래로 길을 뚫음
    // i) 연속으로 우측으로 길을 뚫다가 아래로 뚫을 경우,
    //    연속으로 뚫은 길 중 한 곳을 골라서 아래로 뚫는다.
    Random rand = new Random();
    for (int y = 0; y < _size; y++)
    {
        int rightCount = 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 (x == _size - 2)
            {
                _tile[y + 1, x] = TileType.Empty;
                continue;
            }

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

            Direction dir = (Direction)rand.Next(0, 2);
            switch (dir)
            {
                case Direction.DOWN: // 아래
                    int randomIndex = rand.Next(0, rightCount);
                    _tile[y + 1, x - randomIndex * 2] = TileType.Empty;
                    rightCount = 1;
                    break;
                case Direction.RIGHT: // 우측
                    _tile[y, x + 1] = TileType.Empty;
                    rightCount += 1;
                    break;
            }
        }
    }
}

Side Winder Algorithm으로 만들어진 미로 - 한쪽으로 치우친 것을 볼 수 있다 

 

오늘의 깨달음

간단한 알고리즘일수록 미로의 퀄리티가 낮아진다는 것을 명심해야 합니다!