[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘(4) / 미로 준비, Binary Tree 미로 생성, Side Winder 미로 생성

맵 만들기

 

소스코드

    class Board3
    {
        const char CIRCLE = '\u25cf';
        public TileType[,] _tile; // 배열
        public int _size;

        public enum TileType
        { 
            Empty,
            Wall,
        }

        // 배열 초기화
        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;
                }
            }
        }

        // 배열 안의 index값을 비교하여 길 및 벽을 생성한다.
        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;
            }
        }
    }

 

Binary Tree 미로 생성 알고리즘

        public void Initialize(int size)
        {
            if (size % 2 == 0) //size는 홀수가 입력되어야 한다.
                return;

            _tile = new TileType[size, size];
            _size = size;

            // Mazes for Programmes에서 나오는 기본적인 미로 생성 알고리즘 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;
                }
            }
        }

아래 이미지처럼 미로를 세팅하는 코드다. 

 

빨간색 : 벽

초록색 : 길

 

이 상태에서 각 길마다 오른쪽의 길을 뚫어버리거나, 아래로 길을 뚫어버리나 1/2 확률로 길을 뚫으면서 길을 완성해나가는 형태이다.

 

        public void Initialize(int size)
        {
            if (size % 2 == 0) //size는 홀수가 입력되어야 한다.
                return;

            _tile = new TileType[size, size];
            _size = size;

            // Mazes for Programmes에서 나오는 기본적인 미로 생성 알고리즘 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; // 길인 부부만 작업하면 되기에 Continue.

                    _tile[y, x] = TileType.Empty;

                    // 외곽 출구 조건1
                    if (y == size - 2)
                    {
                        _tile[y, x + 1] = TileType.Empty;
                        continue;
                    }
                    // 외곽 출구 조건2
                    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;
                    }
                }
            }
        }

1. Random에서 나오는 값 0, 1 (1/2 확률을 만들기 위해)을 기준으로 각 empty노드의 오른쪽을 뚫을지, 왼쪽을 뚫을지 결정한다.

 

2. 그리고 외곽의 벽에 출구가 여러개 생기지 않도록, 막기 위하여 외곽 출구 조건 1, 2를 작성한다.

일단 empty노드인곳을 기점으로 길을 뚫기에 마지막 노드는 회색으로 가리킨 저 노드가 된다. 저 노드에서 외곽 출구 조건1을 거치기 때문에 무조건 오른쪽으로 길이 뚫린다.

 

 

                    // 마지막 empty 노드에서 길이 안뚫리도록 함.
                    if (y == _size - 2 && x == _size - 2)
                        continue;

외곽 출구조건1 위에 이 코드를 달아주면, 마지막 노드에서 출구가 생기지 않게 된다.

 

 

Binary Tree 미로 알고리즘 단점 

: 이 알고리즘의 단점은 모양이 치우쳐진다. x의 벽의 마지막 전, y의 벽 마지막 전이 일렬로 뚫려있는 것을 볼 수 있다. 물론 테스트 용도로는 상관없음.

 

 

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; // 점의 개수 (요기1)

                for (int x = 0; x < _size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        continue; // 길인 부부만 작업하면 되기에 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;
                        count++; // (요기2)
                    }
                    else
                    {
                        int randomIndex = rand.Next(0, count); // 요기(3)
                        _tile[y + 1, x - randomIndex * 2] = TileType.Empty; // 요기(4)
                        count = 1; // 요기(5)
                    }
                }
            }
        }

코드는 거의 똑같은데, 요기로 주석처리 해놓은 곳이 바뀐 부분이다. 그냥 지나왔던 부분에서 Ramdom때려서 밑에 부분에 길을 뚫는다.

 

바이너리 트리에 비해 좀 괜찮아보이긴한다. 

물론, y-2부분과 x-2이 부분이 초록색으로 다 칠해지는 태생적인 단점이 있긴하다.