좀짓막(좀비 집짓고 막기) [#3] - A* 길찾기 알고리즘 R&D

캐릭터와 다른 이동기능이 있는 오브젝트에 A*를 적용하기 위해서 A* R&D를 하기로 했다. A*는 시작노드에서 현재노드까지의 가중치 + 현재노드에서 목표노드까지의 가중치를 더한 값을 바탕으로 길을 찾는 알고리즘으로 다음 노드로 이동할때마다 가중치를 더한 값이 가장 적은 노드로 이동한다. A*의 이해에는 다음 블로그들을 참고 했다.

 

https://recall.tistory.com/40

A* 알고리즘(A star algorithm) grid map 개념 및 구현

https://m.blog.naver.com/pkh879/221734003274

Unity - A* 알고리즘(길찾기) 구현하기(개요) Part 1

 

https://www.youtube.com/watch?v=-L-WgKMFuhE&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW&index=1 

A* 의 동작 원리는 다음과 같다

g(n) : 출발노드에서 현재노드까지 드는 비용

h(n) : 현재노드에서 목표노드까지 드는 비용

f(n) = g(n) + h(n)

 

1. 시작노드를 정하고 열린 리스트에 추가한 뒤 닫힌 리스트로 보낸다.

2. 인접노드를 탐색하고 f(n), g(n), h(n) 비용, 부모노드의 정보를 업데이트 한다.

3. 인접노드를 열린 리스트에 추가함

4. 인접노드 중 f(n)값이 가장 적은 노드를 선택하고 닫힌 리스트로 보냄

5. 선택한 노드가 목표 지점의 노드가 될때까지 2~4번을 반복

 

아래 사이트를 참조하여 노드와 그리드의 코드를 작성해보기로 했다.

https://m.blog.naver.com/pkh879/221734003274

 

그리드의 코드를 보는데 Physics.CheckSphere라는 처음보는 함수가 있어서 API에 검색해봤는데 

position에 정의된 구와 겹치는 충돌체가 있다면 true반환하는 함수라고 한다.

즉 어떤 노드가 있는 특정위치에 어떠한 충돌체도 없다면 bool값을 반환해서 걸을 수 있는지 아닌지 판정하는 함수인가보다.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ANode
{
    public bool isWalkable;
    public Vector3 wolrdPos;

    public ANode(bool isWalkable, Vector3 wolrdPos )
    {
        this.isWalkable = isWalkable;
        this.wolrdPos = wolrdPos;
    }
}

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AGrid : MonoBehaviour
{
    public LayerMask unwalkableMask;
    private ANode[,] grid;
    // Start is called before the first frame update
    void Start()
    {
        grid = new ANode[128, 128];
        Vector3 worldPoint;
        for(int i = 0; i < 128; i++)
        {
            for(int j = 0; j < 128; j++)
            {
                worldPoint = new Vector3(i, 0, j);
                bool walkable = !(Physics.CheckSphere(worldPoint, 0.5f, unwalkableMask));
                Debug.Log(walkable);
                grid[i,j] = new ANode(walkable, worldPoint);
            }
        }
    }

    // Update is called once per frame
    void Update()
    {
        
    }

    private void OnDrawGizmos()
    {
        Gizmos.DrawWireCube(transform.position, new Vector3(128, 1, 128));
        if(grid != null)
        {
            foreach(ANode node in grid)
            {
                Gizmos.color = (node.isWalkable ? Color.yellow : Color.red);
                Gizmos.DrawCube(node.wolrdPos, Vector3.one);
            }
        }
    }
}

근데 문제가 발생했다. 내가 이해한 대로라면 그리드를 생성할때 위에 충돌체가 있는지를 판정해서 그 부분은 빨간색으로 표시되야 하는데 모든 격자가 이동 가능한 노란색으로 표시되었다.

 

근데 보니까 그냥 벽을 unwalkableLayer로 설정하지 않아서 발생한 문제였다 그래서 설정해주었다.

 

unwalkable레이어가 있는 구역이 제대로 설정되었다.

 

그 다음에는 목표지점까지의 path를 구하는 코드를 작성하였다.

 

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ANode
{
    public bool isWalkable;
    public Vector3 worldPos;

    public int gCost;
    public int hCost;
    public ANode parentNode;

    public ANode(bool isWalkable, Vector3 worldPos)
    {
        this.isWalkable = isWalkable;
        this.worldPos = worldPos;
    }

    public int fCost
    {
        get { return gCost + hCost; }
    }
}

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AGrid : MonoBehaviour
{
    public LayerMask unwalkableMask;
    private ANode[,] grid;
    // Start is called before the first frame update
    void Start()
    {
        CreateGrid();
    }


    //private void OnDrawGizmos()
    //{
    //    Gizmos.DrawWireCube(transform.position, new Vector3(128, 1, 128));
    //    if(grid != null)
    //    {
    //        foreach(ANode node in grid)
    //        {
    //            Gizmos.color = (node.isWalkable ? Color.yellow : Color.red);
    //            Gizmos.DrawCube(node.wolrdPos, Vector3.one);
    //        }
    //    }
    //}

    public void CreateGrid()
    {
        grid = new ANode[128, 128];
        Vector3 worldPoint;
        for (int i = 0; i < 128; i++)
        {
            for (int j = 0; j < 128; j++)
            {
                worldPoint = new Vector3(i, 0, j);
                bool walkable = !(Physics.CheckSphere(worldPoint, 0.5f, unwalkableMask));
                grid[i, j] = new ANode(walkable, worldPoint);
            }
        }
    }

    public List<ANode> GetNeighbours(ANode node)
    {
        List<ANode> neighbours = new List<ANode>();
        for(int x = -1; x <1 ; x++)
        {
            for(int y = -1; y <1 ; y++)
            {
                if (x == 0 && y == 0) continue;

                int checkX = (int)node.worldPos.x + x;
                int checkY = (int)node.worldPos.z + y;

                if(checkX >= 0 && checkY >= 0 && checkX < 128  && checkY < 128)
                {
                    neighbours.Add(grid[checkX, checkY]);
                }
            }
        }
        return neighbours;
    }

    public ANode GetNodeFromWorldPoint(Vector3 worldPosition)
    {
        float percentX = worldPosition.x / 128;
        float percentY = worldPosition.z / 128;
        percentX = Mathf.Clamp01(percentX);
        percentY = Mathf.Clamp01(percentY);

        int x = (int)(127 * percentX);
        int y = (int)(127 * percentY);
        return grid[x, y];
    }
}

Node스크립트에는 Cost가 추가되었다. 원래는 그리드의 좌표도 추가해주어야 하지만 내 경우엔 그리드의 좌표가 worldPos와 일치하기 때문에 따로 추가하지 않고 worldPos를 사용하기로 하였다.

GetNeighbours 메서드는 인수로 받은 노드의 팔방향의 노드가 Grid안에 있을때 neighbours 리스트에 넣는다. 

GetNodeFromWorldPoint 메서드는 위치를 받아서 그 위치의 노드를 찾아주는 메서드인데

여기서 처음보는 함수가 나왔다, Mathf.Clamp란 함수이다. API를 뒤져보니 Clamp는 값을 제한하는 함수라고 한다. 여기서는 Clamp01로 작성되었으므로 값을 0부터 1까지 제한한다. 내 경우엔 시작지점인 0,0이 그리드의 중간이 아닌 왼쪽 아래이므로 그걸 고려해서 코드를 작성해주었다.

 

그 후엔 패스를 만들어주는 PathFinding 스크립트를 작성하였다. 원래는 Node에 grid 좌표를 넣지 않았었지만 이러면 계속 월드포스를 수정해서 좌표를 만들어야하기 때문에 그냥 추가해주었다. 그리고 코드를 작성하면서 f(n)값이 같을땐 h(n)값이 작은 쪽을 현재 노드로 선택한다는 것을 깨달았다.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PathFinding : MonoBehaviour
{
    AGrid grid;

    public Transform startObject;
    public Transform targetObject;


    private void Awake()
    {
        grid = GetComponent<AGrid>();
    }

    // Update is called once per frame
    void Update()
    {
        
    }

    private void FindPath(Vector3 startPos, Vector3 targetPos)
    {
        ANode startNode = grid.GetNodeFromWorldPoint(startPos);
        ANode targetNode = grid.GetNodeFromWorldPoint(targetPos);

        List<ANode> openList = new List<ANode>();
        HashSet<ANode> closedList = new HashSet<ANode>();
        openList.Add(startNode);

        while(openList.Count> 0)
        {
            ANode currentNode = openList[0];

            for(int i = 1; i < openList.Count; i++)
            {
                if (openList[i].fCost < currentNode.fCost || openList[i].fCost == currentNode.fCost && openList[i].hCost < currentNode.hCost)
                {
                    currentNode = openList[i];
                }
            }

            openList.Remove(currentNode);
            closedList.Add(currentNode);

            if(currentNode == targetNode)
            {
                RetracePath(startNode, targetNode);
                return;
            }

            foreach(ANode node in grid.GetNeighbours(currentNode))
            {
                if (!node.isWalkable || closedList.Contains(node)) 
                    continue;

                //이웃노드의 g(n)과 h(n)비용과 parent노드 업데이트하고 오픈리스트에 넣어줌
                int newCurrentToNeighbourCost = currentNode.gCost + GetDistanceCost(currentNode,node);
                if(newCurrentToNeighbourCost < node.gCost || !openList.Contains(node))
                {
                    node.gCost = newCurrentToNeighbourCost;
                    node.hCost = GetDistanceCost(node, targetNode);
                    node.parentNode = currentNode;

                    if(!openList.Contains(node))
                    {
                        openList.Add(node);
                    }
                }

            }
        }
    }

    private void RetracePath(ANode startNode ,ANode endNode)
    {
        List<ANode> path = new List<ANode>();
        ANode currentNode = endNode;

        while(currentNode != startNode)
        {
            path.Add(currentNode);
            currentNode = currentNode.parentNode;
        }

        path.Reverse();
        grid.path = path;
    }

    private int GetDistanceCost(ANode nodeA, ANode nodeB)
    {
        int distX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
        int distY = Mathf.Abs(nodeA.gridY - nodeB.gridY);

        if(distX > distY)
            return 14 * distY + 10 * (distX - distY);
        return 14 * distX + 10 * (distY - distX);
    }
}

시작노드를 추가한다음 FindPath메서드에서 값이 작은 이웃노드를 찾는 과정을 반복한다. 현재 노드와 목표 노드가 같아지면 타겟노드의 부모노드를 찾아서 path를 만드는 RetracePath메서드가 실행된다.

 

여기까지 작성하면서 느낀점은 분명 머리로는 과정을 이해했는데 막상 코드로 적을려니까 쉽게 되지 않았다. 특히 모르는 함수나 클래스가 많이 나와서 새로 공부하게 되는 계기가 됐다.

 

그런데 스크립트를 작성해서 넣어줬는데도 패스가 만들어지지 않는다. Debug로 찍어보면서 문제점을 찾아보았더니 GetNeighbours메소드에 for문의 조건을 1보다 작거나 같다가 아니라 작을때 for문이 돌도록 해서 생긴 문제 였다. 고치고 다시 한번 패스를 만들어 보았다.

 

그런데 이번에도 작동하지 않았다! 다시 한번 디버그를 찍으면서 찾아 봤더니

foreach(ANode node in grid.GetNeighbours(currentNode))
            {
                if (!node.isWalkable || closedList.Contains(node)) 
                    continue;
                    
                    .....
            }

if문을 지난 다음부터 Debug가 찍히지 않았다 조건을 잘 살펴보니 노드가 걸을 수 있는 상태일때로 정의되있어서 플레이어 위치를 살펴봤더니 아니나 다를까 이동불가 지역에 둬서 플레이어의 위치를 이동가능한 노드가 있는 곳으로 옮겨주고 다시 한번 패스를 만들어보았다.

 

 

패스가 만들어졌다.