[Unity] 유니티 내 길찾기 알고리즘을 넣어보기

개인 기록용으로 적은 글이니
혹시 길찾기 알고리즘을 알아보고 싶으신 분들은 아래 참고 자료를 참고하시는게 좋습니다.

 

개요

 현재 연합동아리에서 제작하고 있는 게임 '뿔 없는 용'. 조선시대 배경으로 이무기가 승천하는걸 모티브로 삼아서 제작하고 있는 게임으로 딱히 길찾기 알고리즘이 들어갈만한 부분이 없는 게임이었습니다.

 그런데 흔히 승천하는 이무기를 맞춰 떨어뜨리는 '지나가던 나그네'에서 이 화살을 유도로 만들면 어떨까? 하는 생각에 오브젝트 풀링으로 화살을 관리하고 각 화살에는 길찾기 알고리즘을 넣어보자는 생각이 들게 되었습니다. 이에 따라 만들고 제작했던 부분들을 한번 써볼려고 합니다.

 

 

길찾기 알고리즘을 위한 Grid 생성

 일단 기존에 알고있는 다익스트라 알고리즘의 경우 이곳에 적합한 방식이 아니라 '그리드 생성 후 BFS 알고리즘으로 찾아보자' 는 생각이 들었습니다. 이에 따라 길찾기 알고리즘을 위한 Grid 생성을 먼저 해 줍니다.

    private void CreateGrid()
    {
        grid = new Node[gridSizeX, gridSizeY];

        Vector2 bottomLeft = (Vector2)transform.position - (Vector2.right * gridWorldSize.x / 2) - (Vector2.up * gridWorldSize.y / 2) + test;
        bottomLeft += gridOffset;
        
        for(int x = 0; x < gridSizeX; x++)
        {
            for(int y = 0; y < gridSizeY; y++)
            {
                Vector2 worldPoint = bottomLeft + Vector2.right * (x * nodeDiameter + nodeRadius) + Vector2.up * (y * nodeDiameter + nodeRadius);
                bool canPass = (Physics2D.OverlapCircle(worldPoint, nodeRadius, groundMask) == null);
                grid[x, y] = new Node(canPass, worldPoint, x, y);
            }
        }
    }

 이전에 흥미용으로 A* 알고리즘 구현을 위해 배웠던 코드를 사용하게 되었습니다. WorldToGrid.cs 스크립트에서 위 함수를 가지고 grid라는 배열에서 이를 관리하는 것입니다. 왼쪽 아래를 기준으로 평범한 2차원 공간좌표를 만들었고 Physics2D의 overlapcircle을 사용해 지나갈 수 있는 지점인지를 판단했습니다.

살짝의 오류들이 있어 판별을 잘 못하는 부분이 있지만 큰 오류 없이 전체적으로 잘 나오고 있습니다.

 

 

BFS로 길 판별하기

 이제 Grid가 2차원 배열을 가지고 있으니 여기에 BFS를 적용하는건 크게 어렵지 않습니다. 그냥 알고리즘 문제대로 풀이하면 되는 것이죠.

    IEnumerator PathFinding(WorldToGrid grid, Vector2 startPos, Vector2 endPos)
    {
        Vector2[] wayPoint = new Vector2[0];
        bool success = false;

        Node startNode = grid.NodeFromWroldPosition(startPos);
        Node targetNode = grid.NodeFromWroldPosition(endPos);

        if(startNode.canWalk && targetNode.canWalk)
        {
            Queue<Node> q = new Queue<Node>();
            bool[,] visit = new bool[grid.GridSizeX, grid.GridSizeY];
            q.Enqueue(startNode);
            Node curNode, nextNode;
            while(q.Count > 0)
            {
                curNode = q.Dequeue();

                if(curNode == targetNode)
                {
                    success = true;
                }

                for(int i = 0; i < 4; i++)
                {
                    int nextX = curNode.gridX + moveX[i];
                    int nextY = curNode.gridY + moveY[i];

                    if(nextX < 0 || nextY < 0 || nextX >= grid.GridSizeX || nextY >= grid.GridSizeY)    continue;
                    if(visit[nextX, nextY]) continue;
                    nextNode = grid.grid[nextX, nextY];

                    if(!nextNode.canWalk)   continue;

                    visit[nextX, nextY] = true;
                    nextNode.parent = curNode;
                    q.Enqueue(nextNode);
                }

                if(!canDiagonalMove)    continue;
                for(int i = 4; i < 8; i++)
                {
                    int nextX = curNode.gridX + moveX[i];
                    int nextY = curNode.gridY + moveY[i];

                    if(nextX < 0 || nextY < 0 || nextX >= grid.GridSizeX || nextY >= grid.GridSizeY)    continue;
                    if(visit[nextX, nextY]) continue;
                    nextNode = grid.grid[nextX, nextY];

                    if(!nextNode.canWalk)   continue;

                    visit[nextX, nextY] = true;
                    nextNode.parent = curNode;
                    q.Enqueue(nextNode);
                }

            }

            yield return null;
            if(success)
            {
                wayPoint = TracePath(startNode, targetNode);
            }
            RequestBFSPathfinding.instance.FinishPathFinding(wayPoint, success);
        }
    }

 옵션에 따라서 4/8방향으로 갈 수 있게 제작을 했는데 위 for문 2개가 이를 뜻합니다. 코드가 길기만 하지 사실 별거없는 BFS 알고리즘을 적용한 모습으로 이후 각 Node의 parent를 거슬러 올라가면서 길을 찾을 수 있는 모습입니다.

 

A* 알고리즘 적용

 BFS 알고리즘의 경우 쉽게 적용할 수 있고 이후의 문제도 크게 없어 보였지만 더 높은 수준의 알고리즘은 어떻게 작용하는지 보고 싶기에 A* 알고리즘을 찾아보게 되었습니다.

A* Pathfinding Tutorial (Unity)

 수많은 예제 자료들이 있었지만 가장 개념을 확실하게 알 수 있는 자료는 위 자료라고 생각이 듭니다. 첫 영상으로 가볍게 개념을 파악한 뒤 실제 적용을 통해서 A* 알고리즘을 알아낼 수 있었습니다. 

 

 

결과물

 이제 실제 인게임 내 결과물을 보면 해당 Path대로 화살이 잘 움직이는 모습을 볼 수 있습니다. 현재는 Grid 크기가 크다 보니 막 자연스러운 움직임이 아닌 뚝뚝 끊기는 모습을 가지고 있지만 이는 이후 최적화 수준에 따라 Grid를 세분화하면 고칠 수 있는 내용이라 괜찮습니다.

 

 이 과정에서 본 애니메이션에서 각 뼈의 각도 조절(위 NPC의 화살 각도)와 Grid Offset 관리, 추가로 화살은 오브젝트 풀링, 길찾기를 수행하는 오브젝트는 1개로 줄여서 Manager 처럼 사용하는 등 여러가지 생각할게 많았던 작업입니다.

 

 

참고자료

A* Pathfinding Tutorial (Unity)

 

소스코드

GitHub - NoHornDragon/NoHornDragon_GameDev: '뿔 없는 용' 개발용 리포지토리입니다.