[길찾기 알고리즘] 1. 미로 준비 (2) Binary Tree 방법

생성 과정

1) 미로 전체를 사방이 막힌 격자 모양으로 초기화

2) 빈 공간에서 오른쪽 또는 아래쪽으로 길 생성(벽을 빈 공간으로 변경)

// 예외 처리

2-1) 가장 오른쪽 벽과 가장 아래쪽 벽은 막힌 채로 유지

2-2) 우측 하단 꼭지점 위 또는 왼쪽은 교차점으로 길로 뚫리지 않게 처리

 

장점 : 단순하고 직관적

단점 : 미로 모양 단순, 오른쪽과 아래쪽에 직선 경로 생성

 

public void Initialize(int size)
{
    // 미로 변의 길이 홀수인지 확인
    if (size % 2 == 0)
        return;

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

    GenerateByBinaryTree();
}
public void GenerateByBinaryTree()
{
    // 바둑판 모양
    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;
        }
    }
    // 빈 공간에서 아래 or 오른쪽으로 길 만들기
    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;
        }
    }
}

* 참고 서적 - Mazes for Programmers

내용 출처 : Inflearn Rookiss님 강의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘

https://www.inflearn.com/course/%EC%9C%A0%EB%8B%88%ED%8B%B0-mmorpg-%EA%B0%9C%EB%B0%9C-part2