Grid System (2) - 미로 만들기 (Maze Algorithm)

2020/05/10 - [Unity & C#] - Grid System - (1) 격자 구조 만들기

Grid System - (1) 격자 구조 만들기

 

지난 포스트에서 만든 Grid System과 Board로 미로를 만들어보자.

 

 

미로를 생성하는 알고리즘은 매우 다양하다.

간단히 시도해 볼 수 있는 Recursive Backtracking으로 해보려 한다.

 

 

Recursive Backtracking

말그대로 재귀적으로 탐색하는 방법이며, 깊이우선탐색(DFS)의 알고리즘이다.

Recursive Backtracking - www.jamisbuck.org/mazes/

 

아래 순서로 구현하면 될 것 같다.

1. 시작 노드를 방문한다. (시작 노드는 현재 노드가 된다.)

2. 현재 노드에서 이동가능한 방향 중 한 곳을 랜덤으로 선택하여 이동한다.

3. 이동 가능한 방향이 없을 때까지 2를 반복한다.

4. 이동 가능한 방향이 없을 경우 이전 노드로 돌아간다.

5. 2부터 다시 시작

6. 모든 노드를 방문하면 종료.

 

 

public class Board 
{
    private void RecursiveBacktracking()
    {
        // 모든 노드 방문, 탐색 종료
        if (_tracks.Count <= 0) return;
        
        // 현재 노드에서 이동가능한 방향 중 한 곳을 랜덤으로 선택하여 이동한다.
        var currentTile = _tracks[_tracks.Count - 1];
        var nextTile = GetRandomNeighbourTile(currentTile);
        
        if (nextTile != null)
        {
            VisitTile(currentTile, nextTile);
        }
        else
        {
            // 이동 가능한 방향이 없을 경우, 되돌아간다.
            _tracks.RemoveAt(_tracks.Count - 1);
        }

        // 재귀탐색
        RecursiveBacktracking();        
    }

    // 네 방향 중 방문 가능한 곳(방문한 적 없는 곳)을 랜덤으로 반환한다.
    private Tile GetRandomNeighbourTile(Tile tile)
    {
        var upTile = GetTile(tile.x, tile.y + 1);
        var downTile = GetTile(tile.x, tile.y - 1);
        var leftTile = GetTile(tile.x - 1, tile.y);
        var rightTile = GetTile(tile.x + 1, tile.y);

        var neighbourTiles = new List<Tile>();
        if (upTile != null && !upTile.IsVisited()) neighbourTiles.Add(upTile);
        if (downTile != null && !downTile.IsVisited()) neighbourTiles.Add(downTile);
        if (leftTile != null && !leftTile.IsVisited()) neighbourTiles.Add(leftTile);
        if (rightTile != null && !rightTile.IsVisited()) neighbourTiles.Add(rightTile);

        if (neighbourTiles.Count <= 0) return null;

        return neighbourTiles[Random.Range(0, neighbourTiles.Count)];
    }


    // 다음 타일을 방문하고, 만나는 방향을 열어준다.
    private void VisitTile(Tile currentTile, Tile nextTile)
    {
        if (currentTile.x < nextTile.x)
        {
            currentTile.right = true;
            nextTile.left = true;
        }

        if (currentTile.x > nextTile.x)
        {
            currentTile.left = true;
            nextTile.right = true;
        }

        if (currentTile.y < nextTile.y)
        {
            currentTile.up = true;
            nextTile.down = true;
        }

        if (currentTile.y > nextTile.y)
        {
            currentTile.down = true;
            nextTile.up = true;
        }

        currentTile.SetWall();
        nextTile.SetWall();
        
        _tracks.Add(nextTile);      
        
        nextTile.OnClick();
    }
    
    
    private Tile GetTile(int x, int y)
    {
        if (x >= 0 && x < width &&
            y >= 0 && y < height)
        {
            return _tiles[x, y];
        }


        return null;
    }
}

 

public class Tile : MonoBehaviour
{
    public int x, y;
    public bool up, down, left, right;
    public GameObject upWall, downWall, leftWall, rightWall;

...
  
    // 열린 방향에 따라 벽을 켜고 끈다.
    public void SetWall()
    {
        upWall.SetActive(!up);
        downWall.SetActive(!down);
        leftWall.SetActive(!left);
        rightWall.SetActive(!right);
    }


    // 방문한 적이 있는가
    public bool IsVisited()
    {
        return up || down || left || right;
    }
}

 

 

결과

 

생성 과정을 시각적으로 보기 위해 방문할 때 빨간 색, 돌아올 때 회색으로 칠했다.

 

 

 

Recursive Backtracking은 구현이 간단하다.

또한 선형적인 알고리즘 특성상 다른 미로 알고리즘에 비해 시각적으로 익숙한(?) 미로가 생성되는 편이다.

(미로에 어울리지 않는 짧은 길이 적게 나온다.)

100 x 100

 

 

다만 Board 사이즈가 커질수록 퍼포먼스가 급격하게 떨어진다. 

위와 같은 100x100을 생성하는데 수초의 시간이 걸린다.

이때는 미로를 생성하는 Line의 갯수를 늘려주면 해결된다.

 

각 Line은 Recursive Backtracking의 기본적인 알고리즘을 그대로 따르고,

각자 방문했던 track 기록을 유지한다.

서로 다른 Line이 만났을 경우 한 쪽으로 합쳐지며 같은 Line이 되고, 

track 기록이 합쳐진다. (직접 구현은 다음에.. )

Recursive Backtracking Parallel Seeds - www.jamisbuck.org/mazes/

 

 

 

<참고>

다양한 미로 알고리즘은 아래 사이트에서 테스트해 볼 수 있다.

https://www.jamisbuck.org/mazes/

Maze Algorithms