[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : SideWinder 미로(3)

인트로

C# 콘솔 프로그래밍으로 미로를 만들고 BFS, A* 알고리즘으로 미로의 출구를 찾는 프로그램을 작성하려 한다.

 

Part1에선 2차원 미로를 만들어보려 한다.

 

(+ Visual Studio 기준으로 포스팅을 이어나갈 예정입니다.)

 

[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(1)

[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(2)

[C#] 미로 만들기와 길찾기 알고리즘 Part 2 : Player 만들기

[C#] 미로 만들기와 길 찾기 알고리즘 Part 3 : BFS 길 찾기

 

SideWinder 미로 생성 알고리즘

미로를 만드는 것은 의외로 간단한데 Empty 지역의 동서남북을 Wall로 채우는 것부터 시작한다. 

 

Board 클래스의 InitializeBoard메서드에서 x 또는 y의 좌표가 짝수일 때 바닥을 Wall로 채운다. 참고로 미로의 외벽을 Wall로 채워야 하기에 size가 짝수라면 size를 받지 않도록 한다.

/* Board.cs */
public void InitializeBoard(int size)
{
    if (size % 2 == 0)
        return;

    _size = size;
    _tile = new TileType[_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;
        }
    }
}

사방이 막힌 미로가 생성되었다.

 

 

이제부터 본격적으로 미로를 만들기 시작한다. 랜덤 한 숫자를 하나 뽑아서 숫자가 짝수이면 녹색의 오른쪽 바닥을 Empty로 만들며 길을 뚫어 간다. 

 

만약 두 번 연속 짝수가 나와서 아래 그림처럼 길을 뚫었다고 가정해보자. 이제는 좌표상(1, 5) 지점에서 오른쪽 혹은 아래로 길을 뚫어나갈 텐데 마침 홀수를 뽑아서 아래로 간다고 가정해보자.

여기서부터 SideWinder 알고리즘이 등장한다. SideWinder 알고리즘은 단순히 길을 아래로 뚫는 것이 아닌 지금까지 뚫어왔던 지점 중 랜덤하게 하나를 골라서 아래로 길을 뚫어준다

 

다음과 같이 코드를 수정하면 위 설명과 동일하게 동작한다.

/* Board.cs */
public void InitializeBoard(int size)
{
    if (size % 2 == 0)
        return;

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

    #region Fill 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;
        }
    }
    #endregion

    for (int y = 0; y < _size; y++)
    {
        int count = 1;

        for (int x = 0; x < _size; x++)
        {
            if (x % 2 == 0 || y % 2 == 0)
                continue;

            Random rnd = new Random();

            if (rnd.Next(0, 2) == 0)
            {
                _tile[y, x + 1] = TileType.Empty;
                count++;
            }
            else
            {
                int idx = rnd.Next(0, count);
                _tile[y + 1, x - idx * 2] = TileType.Empty;
                count = 1;
            }
        }
    }
}

그런데 문제는 맨 아래 줄과 맨 우측 줄이 뚫리는 현상이 발생한다.

 

맨 우측과 아래는 길을 뚫지 않게 코드를 작성해 주고 목표 좌표(_size -2, _size-2)는 항상 길을 뚫도록 코드를 추가해 준다.

/* Board.cs */
public void InitializeBoard(int size)
{
    if (size % 2 == 0)
        return;

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

    #region Fill 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;
        }
    }
    #endregion

    #region SideWinder Algorithm
    for (int y = 0; y < _size; y++)
    {
        int count = 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;
            }

            Random rnd = new Random();

            if (rnd.Next(0, 2) == 0)
            {
                _tile[y, x + 1] = TileType.Empty;
                count++;
            }
            else
            {
                int idx = rnd.Next(0, count);
                _tile[y + 1, x - idx * 2] = TileType.Empty;
                count = 1;
            }
        }
    }
    #endregion
}

이제 정상적인 미로의 형태를 갖추게 됐다!

 

마무리

SideWinder 코드를 InitializeBoard 메서드에 작성하는 것보다 별도의 메서드에 정의하고 호출하는 방법으로 구조를 바꾸는 게 맞는 것 같다.

        public void InitializeBoard(int size)
        {
            if (size % 2 == 0)
                return;

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

            GenerateBySideWinder();
        }

        private void GenerateBySideWinder()
        {
            #region Fill 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;
                }
            }
            #endregion

            #region SideWinder Algorithm
            for (int y = 0; y < _size; y++)
            {
                int count = 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;
                    }

                    Random rnd = new Random();

                    if (rnd.Next(0, 2) == 0)
                    {
                        _tile[y, x + 1] = TileType.Empty;
                        count++;
                    }
                    else
                    {
                        int idx = rnd.Next(0, count);
                        _tile[y + 1, x - idx * 2] = TileType.Empty;
                        count = 1;
                    }
                }
            }
            #endregion
        }