[GameAlgorithm] 미로 생성 알고리즘 _ Binary Tree Maze Algorithm

[목차]

#Binary Tree Maze Algorithm 

#구현

#참고

* 개인적인 공부 내용을 기록하기 위한 용도로 작성된 포스팅 이기에 잘못된 내용이 있을 수 있습니다.

* 인프런 Rookiss 선생님의 PART2 자료구조와 알고리즘 - Binary Tree 미로 생성 알고리즘 내용을 기반으로 정리한 글 입니다.

---

#Binary Tree Maze Algorithm 

Binary Tree Maze Algorithm 이란, 간단한 미로 생성 알고리즘 중 하나로 모든 벽이 막힌 정사각형 모양이 보드판이 있다고 가정할 때 오른쪽 혹은 아래쪽 (위쪽 혹은 왼쪽도 가능) 으로 길을 뚫어 가며 미로를 생성하는 원리의 알고리즘이다.

예를들어 다음과 같은 5X5 타일이 준비되어 있으며, 좌측 상단부터 미로를 생성해 나간다고 생각해 보자.

선택한 블록으로 부터 오른쪽 혹은 아래쪽으로 1/2 의 랜덤확률로 길을 뚫어서 미로를 생성해 나간다.

 

구현이 쉽고 간단하다는 장점이 이지만, 모양이 치우쳐저서 맵이 이쁘게 나오지 않는다는 단점이 있다.

---

#구현

들어가기에 앞서 몇가지 Console 클래스의 메서드를 소개한다. Console 클래스는 콘솔 애플리케이션에 대한 표준 입력, 출력 및 오류 스트림을 나타내는 클래스이다. 

 

Console.CursorVisible : 커서의 깜빡거림을 꺼주는 기능을 수행한다. bool 값을 넣어 주며 true = 킴 false = 끔 상태이다.

Console.setCursorPosition(X,Y) : 커서의 위치를 X, Y 지점으로 옮겨준다.

ConsoleColor : 콘솔의 전경색과 배경색을 정의하는 상수를 지정한다.

Console.ForegroundColor : 콘솔의 전경색을 가져오거나 설정한다. (Default Value : Gray)

더 자세한 내용은  https://docs.microsoft.com/ko-kr/dotnet/api/system.console?view=net-5.0 를 참고 하도록 하자!

 

다음 프로젝트에는 프로그램 메인부분인 Program.cs 와 미로의 출력 및 미로 생성 알고리즘 함수가 정의되어 있는는 Board.cs 2가지 소스파일이 사용 되었다.

// Program.cs
using System;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            Board board = new Board();
            board.Initialize(25);
            Console.CursorVisible = false;

            while (true)
            {
                Console.SetCursorPosition(0,0);
                board.Render();
            }
        }
    }
}

// Board.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    class Board
    {
        const char CIRCLE = '\u25cf';
        public TileType[,] _tile;
        public int _size;

        public enum TileType
        {
            Empty,
            Wall,
        }

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

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

            GenerateByBinaryTree();
        }

        void GenerateByBinaryTree()
        {
            // 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 길뚫기
            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)
                    {
                        _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;
            }
        }
    }
}

 

다른 소스코드 영역은 출력을 담당하는 파트이니, GenerateByBinaryTree 함수를 중점으로 정리 하도록 하겠다. 다음은 초기 맵을 설정하는 코드이다. 붉은색 부분은 enum TileType 에 정의된 Wall 로, 이동 불가능한 지역을 나타내며, 초록색 부분은 enum TileType 에 정의된 Empty 로, 이동 가능한 지역을 나타낸다.

            // 초기 맵 설정
            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;
                }
            }

 

이동 불가능 지역 (Wall) 은 건너 뛰고 (continue) , 이동 가능한 지역 (Empty) 을 기준으로 Random 클래스를 이용해 1/2 확률로 오른쪽 혹은 아래쪽으로 길을 뚫어 나간다.

            // Random 길뚫기
            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;
                    }
                }
            }

 

하지만 약간 문제가 존재한다. 겉 테두리 부분의 일부가 이동 가능 지역으로 바뀌고 만다. 

 

따라서 다음 소스코드를 추가해 약간 보완해 주면 겉 테두리가 모두 이동 불가능 지역으로 설정된다!

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

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

---

#참고

다음 사이트를 참고하면, Binary Tree Maze Algorithm 을 이용해 미로를 만드는 과정을 눈으로 확인할 수 있다. 또 다른 소스코드의 데모 버전도 확인 가능하니 참고하면 좋을것 같다. :)

http://www.jamisbuck.org/mazes/

Maze Algorithms

---