세 번째 미니게임 미로 탈출 개발 일지 1

세 번째 미니게임 선정

세 번째 미니게임은 3D에 적은 아트 리소스로 개발 가능한 것으로 만들고 싶었다.

그러던 중 생각난 게임은 [미로 탈출]이었다!

단순히 큐브 오브젝트로 만들어도 괜찮은 퀄리티가 나올거 같아 선정했다.

단순한 미로 탈출에 게임적 요소를 잔뜩 넣어서 만들어야지🤓

미로 생성 알고리즘

우선 가장 중요한 미로 생성 알고리즘에 대해 알아보았다.

 

기본적으로 미로는 벽과 통로로 구성되어 있다.

2차원 배열로 표현하면 홀수 좌표는 통로, 짝수 좌표는 벽이 된다.

■ ■ ■ ■ ■
■ □ ■ □ ■
■ □ ■ □ ■
■ □ □ □ ■
■ ■ ■ ■ ■

 

👉 즉, 통로는 벽 사이에 1칸 이상 간격을 두고 배치되어야 함.

 

미로를 생성하는 알고리즘은 DFS 백트래킹으로 정했다.

 

1. 미로를 2차원 배열로 표현 (홀수 칸은 벽, 짝수 칸은 통로)
2. 시작 지점에서 인접한 요소 중 방문하지 않은 요소를 랜덤하게 하나 선택
3. 벽을 하나 제거하고 다음 요소로 이동
4. 더 이상 이동할 수 없으면 되돌아감 (백트래킹)
5. 모든 요소를 방문할 때까지 반복

Fisher-Yates 알고리즘

Fisher-Yates 알고리즘이란 배열이나 리스트와 같은 데이터 집합을 무작위로 섞는 알고리즘이다.

동작 방식은 배열의 뒤에서부터 앞으로 하나씩 선택하면서 현재 인덱스까지 중 무작위 인덱스를 뽑고 서로 교환한다.

매우 간단하지만 편향없는 무작위성을 부여할 수 있는 굉장히 효율적인 알고리즘이다.

매번 새로운 모양의 미로를 만들기 위해 방문하지 않은 요소를 랜덤하게 하나 선택할 때 사용하였다.

코드 살펴보기

public class GameManager : MonoBehaviour
{
    // 벽 + 통로 + 벽 형태가 되어야 하기 때문에 미로 크기는 홀수로 지정
    [Header("미로 크기")]
    public int width = 21;
    public int height = 21;

    [Header("프리팹 설정")]
    public GameObject wallPrefab;
    public GameObject floorPrefab;
    public GameObject exitPrefab;
    public GameObject playerPrefab;

    private int[,] maze;

    // 상, 하 , 좌, 우
    private readonly int[] dx = { 0, 0, -2, 2 };
    private readonly int[] dy = { -2, 2, 0, 0 };

    private void Start()
    {
        GenerateMaze();
        BuildMaze();
        SpawnPlayer();
        SpawnExit();
    }

    private void GenerateMaze()
    {
        maze = new int[width, height];

        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                maze[x, y] = 1; // 전부 벽으로 초기화
            }
        }

        DFS(1, 1); // 시작점 (1, 1)
    }

    private void DFS(int x, int y)
    {
        maze[x, y] = 0; // 통로 설정

        List<int> dir = new List<int> { 0, 1, 2, 3 };
        Shuffle(dir // 무작위 방향 결과

        foreach (int i in dir)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (IsInMaze(nx, ny) && maze[nx, ny] == 1)
            {
            	// 중간 벽 허물기
                maze[x + dx[i] / 2, y + dy[i] / 2] = 0;
                DFS(nx, ny);
            }
        }
    }

    // 미로에 오브젝트 배치
    private void BuildMaze()
    {
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                if (maze[x, y] == 1)
                {
                    Instantiate(wallPrefab, new Vector3(x, 0, y), Quaternion.identity, transform);
                }
                else
                {
                    Instantiate(floorPrefab, new Vector3(x, -0.45f, y), Quaternion.identity, transform);
                }
            }
        }
    }

    // 플레이어 배치
    private void SpawnPlayer()
    {
        Instantiate(playerPrefab, new Vector3(1, 0.1f, 1), Quaternion.identity);
    }

    // 출구 배치
    private void SpawnExit()
    {
        int ex = width - 2;
        int ey = height - 2;

		// 만약 출구 위치가 벽이라면, 통로로 생성
        if (maze[ex, ey] == 1)
        {
            maze[ex, ey] = 0;
        }

        Instantiate(exitPrefab, new Vector3(ex, 0.1f, ey), Quaternion.identity);
    }

    // 미로 경계 확인
    private bool IsInMaze(int x, int y)
    {
        return x > 0 && x < width && y > 0 && y < height;
    }

    // Fisher-Yates 알고리즘
    private void Shuffle(List<int> list)
    {
        for (int i = list.Count - 1; i > 0; i--)
        {
            int rand = Random.Range(0, i + 1);
            int temp = list[i];
            list[i] = list[rand];
            list[rand] = temp;
        }
    }
}

결과

시작과 탈출 위치는 고정이고 매번 새로운 미로가 생성되는 것을 확인할 수 있다.