Unity) [유니티 2D] 프로젝트에 맞도록 A* PathFinding 스크립트 커스텀

 기존 A* 스크립트는 월드 좌표 Vector3.zero 에서만 작동하도록 만들어졌고 해당 기능을 구현하기 위해 Unity 2D의 Vector2 정보를 Node 형식으로 변환하여 Grid로서 관리해야했다. 해당 기능은 상당히 부하가 많이 생기는 작업으로 현재 프로젝트의 넓은 맵을 전부 Node 단위로 쪼개 길 찾기 로직을 수행하기에는 문제가 있었다.그렇기 때문에 플레이어가 진행 중인 던전 룸에 A* 오브젝트를 옮기고 그 룸의 자식 오브젝트로서 로컬 좌표 Vector3.zero 에서 기능하도록 했다. 해당 기능을 구현하기 위해 그리드를 로컬좌표 단위로 저장하고 실제 길찾기를 실행하는 PathFinder가 그 로컬좌표 안에서 길찾기를 수행하도록 변경하였다.

 

/*
 * 커스텀 Node 클래스 입니다.
 * 
 * Grid 안에 들어갈 Node입니다.
 */ 

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

public class Node
{
    public bool walkable;
    public Vector2 localPosiotion;
    public int gridX;
    public int gridY;

    public int gCost;
    public int hCost;
    // 길 되추적을 위한 parent변수.
    public Node parent;

    // F cost 계산 속성.
    public int fCost{ get { return gCost + hCost;} }

    // Node 생성자.
    public Node(bool walkable, Vector2 localPos, int gridX, int gridY)
    {
        this.walkable = walkable;
        this.localPosiotion = localPos;
        this.gridX = gridX;
        this.gridY = gridY;
    }
}

/*
 * 커스텀 Grid 클래스 입니다.
 * 
 * 스크린을 Grid - Node로 분할 합니다.
 */ 

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

public class Grid : MonoBehaviour
{
    public bool displayGridGizmos;
    // 플레이어의 위치
    public Transform player;
    // 장애물 레이어
    public LayerMask OBSTACLE;
    // 화면의 크기
    public Vector2 gridLocalSize;
    // 반지름
    public float nodeRadius;
    Node[,] grid;

    // 격자의 지름
    float nodeDiameter;
    // x,y축 사이즈
    int gridSizeX, gridSizeY;

    public void Init()
    {
        this.player = GameObject.FindGameObjectWithTag("Player").transform;
        this.nodeDiameter = this.nodeRadius * 2;
        this.gridSizeX = Mathf.RoundToInt(this.gridLocalSize.x / this.nodeDiameter);
        this.gridSizeY = Mathf.RoundToInt(this.gridLocalSize.y / this.nodeDiameter);
        // 격자 생성
        this.CreateGrid();
    }

    public void Start()
    {
        this.player = GameObject.FindGameObjectWithTag("Player").transform;
        this.nodeDiameter = this.nodeRadius * 2;
        this.gridSizeX = Mathf.RoundToInt(this.gridLocalSize.x / this.nodeDiameter);
        this.gridSizeY = Mathf.RoundToInt(this.gridLocalSize.y / this.nodeDiameter);
        // 격자 생성
        this.CreateGrid();
    }

    // A*에서 사용할 PATH.
    [SerializeField]
    public List<Node> path;

    // Scene view 출력용 기즈모.
    private void OnDrawGizmos()
    {
        Gizmos.DrawWireCube(this.transform.position, new Vector2(this.gridLocalSize.x, this.gridLocalSize.y));
        if(this.grid != null )
        {
            Node playerNode = NodeFromLocalPoint(this.transform.InverseTransformPoint(this.player.transform.position));
            foreach (Node n in this.grid)
            {
                Gizmos.color = (n.walkable) ? new Color(1, 1, 1, 0.3f) : new Color(1, 0, 0, 0.3f);
                if(n.walkable == false)
                
                if(path != null)
                {
                    if (path.Contains(n))
                        {
                            Gizmos.color = new Color(0, 0, 0, 0.3f);
                            Debug.Log("?");
                        }
                    }
                if (playerNode == n) Gizmos.color = new Color(0, 1, 1, 0.3f);
                Gizmos.DrawCube(n.localPosiotion, Vector2.one * (this.nodeDiameter - 0.1f));
            }
        }
    }

    // 격자 생성 함수
    void CreateGrid()
    {
        this.grid = new Node[gridSizeX, gridSizeY];
        // 격자 생성은 좌측 최하단부터 시작. transform은 월드 중앙에 위치한다. 
        // 이에 x와 y좌표를 반반 씩 왼쪽, 아래쪽으로 옮겨준다.
        Vector2 localBottomLeft = (Vector2)this.transform.position - Vector2.right * this.gridLocalSize.x / 2 - Vector2.up * this.gridLocalSize.y / 2;

        for (int x = 0; x < this.gridSizeX; x++)
        {
            for (int y = 0; y < this.gridSizeY; y++)
            {
                Vector2 localPoint = localBottomLeft + Vector2.right * (x * this.nodeDiameter + this.nodeRadius) + Vector2.up * (y * this.nodeDiameter + this.nodeRadius);
                // 해당 격자가 Walkable한지 아닌지 판단.
                bool walkable = !(Physics2D.OverlapCircle(localPoint, this.nodeRadius, this.OBSTACLE));
                // 노드 할당.
                this.grid[x, y] = new Node(walkable, localPoint, x, y);
            }
        }
    }

    // node 상하 좌우 대각 노드를 반환하는 함수.
    public List<Node> GetNeighbours(Node node)
    {
        List<Node> neighbours = new List<Node>();

        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                if (x == 0 && y == 0) continue;

                int checkX = node.gridX + x;
                int checkY = node.gridY + y;

                if (checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
                {
                    if (!this.grid[node.gridX, checkY].walkable && !this.grid[checkX, node.gridY].walkable) continue;
                    if (!this.grid[node.gridX, checkY].walkable || !this.grid[checkX, node.gridY].walkable) continue;

                    neighbours.Add(this.grid[checkX, checkY]);
                }
            }
        }

        return neighbours;
    }


    // 입력으로 들어온 로컬좌표를 node좌표계로 변환.
    public Node NodeFromLocalPoint(Vector2 localPosition)
    {
        float percentX = (localPosition.x + this.gridLocalSize.x / 2) / this.gridLocalSize.x;
        float percentY = (localPosition.y + this.gridLocalSize.y / 2) / this.gridLocalSize.y;
        percentX = Mathf.Clamp01(percentX);
        percentY = Mathf.Clamp01(percentY);
        int x = Mathf.RoundToInt((this.gridSizeX - 1) * percentX);
        int y = Mathf.RoundToInt((this.gridSizeY - 1) * percentY);
 
        return this.grid[x, y];
    }
}

/*
 * 이 클래스는 화면을 grids로 나누어야 합니다. 이를 위해 커스텀클래스 Grid와 Node class를 사용합니다.
 * 알고리즘 개요
 * OPEN SET : 평가되어야 할 노드 집합
 * CLOSED SET : 이미 평가된 노드 집합
 * 
 * 1. OPEN SET에서 가장 낮은 F코스트를 가진 노드 획득 후 CLOSED SET 삽입
 * 2. 이 노드가 목적지라면, 반복문 탈출
 * 3. 이 노드의 주변 노드들을 CLOSED SET에 넣고, 주변노드의 F값 계산. 주변노드의 G값보다 작다면 F값으로 G값 최신화
 * 4. 1번 반복.
 */ 


using System.Collections;
using UnityEngine.EventSystems;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public partial class PathFinding : MonoBehaviour
{ 
    [Header("Path Finding")]
    public GameObject target;
    // 맵을 격자로 분할한다.
    Grid grid;
    // 남은거리를 넣을 큐 생성.
    public Queue<Vector2> wayQueue = new Queue<Vector2>();
    private Coroutine findPathRoutine;

    public Animator anim;
    public Monster monster;

    //rigidbody
    protected Rigidbody2D rBody2D;

    // 뭔가와 상호작용 하고 있을때는 walkable이 false 가 됨.
    public static bool walkable = true;

    // 플레이어 이동/회전 속도 등 저장할 변수
    public float moveSpeed;
    public float normalMoveSpeed;
    protected float tmpSpeed;
    // 장애물/NPC 판단시 멈추게 할 범위
    public float eyeRange;
    public float attackRange;

    public bool isWalking;

    //타겟과 위치값 비교
    protected float dist;
    protected Vector2 dir;
    protected float dirX; 

    //private void Awake()
    //{
    //    // 격자 생성
    //    this.grid = GameObject.Find("Astar").GetComponent<Grid>();
    //    //grid = GetComponent<Grid>();
    //    walkable = true;
    //    //rigidbody
    //    this.rBody2D = gameObject.GetComponent<Rigidbody2D>();
    //    this.target = GameObject.FindGameObjectWithTag("Player");

    //}

    public virtual void Init(Transform player)
    {
        this.grid = GameObject.Find("Astar").GetComponent<Grid>();
        //grid = GetComponent<Grid>();
        walkable = true;
        //rigidbody
        this.rBody2D = gameObject.GetComponent<Rigidbody2D>();
        this.target = GameObject.FindGameObjectWithTag("Player");
        this.isWalking = false;
        this.tmpSpeed = this.moveSpeed;
    }

    protected virtual void FixedUpdate()
    {
        this.StartFindPath((Vector2)this.transform.position, (Vector2)this.target.transform.position);

        this.dist = Vector2.Distance(this.transform.position, this.target.transform.position);

        //스프라이트 플립
        this.FlipMonster();

        if (this.isKnockBack && !this.noKnockback) 
        {
            this.KnockBack(this.knockBackSpeed);
        } 
    }

    // start to target 이동.
    public void StartFindPath(Vector2 startPos, Vector2 targetPos)
    {
        if (pathSuccess == true)
        {
            // 이동중이라는 변수 ON
            this.isWalking = true;
            // wayQueue를 따라 이동시킨다.
            if (this.wayQueue.Count > 0)
            {
                this.dir = (Vector2)this.wayQueue.First() - (Vector2)this.transform.position;
                //길찾기 조건 - 탐색 범위
                if (this.dist <= this.eyeRange)
                {
                    this.rBody2D.velocity = this.dir.normalized * this.moveSpeed * Time.deltaTime * this.stun;
                }
                if ((Vector2)this.transform.position == this.wayQueue.First())
                {
                    Debug.Log("Dequeue");
                    this.wayQueue.Dequeue();
                }
            }
            // 이동중이라는 변수 OFF
            this.isWalking = false;
        }

        if (this.isFindingPath) return;

        this.isFindingPath = true;

        if (this.findPathRoutine != null) this.StopCoroutine(this.findPathRoutine);
        this.findPathRoutine = this.StartCoroutine(this.FindPath(startPos, targetPos));
    }

    // 길찾기 로직.
    private IEnumerator FindPath(Vector2 startPos, Vector2 targetPos)
    {   
        // start, target의 좌표를 grid로 분할한 좌표로 지정.
        Node startNode = grid.NodeFromLocalPoint(this.grid.transform.InverseTransformPoint(startPos));
        Node targetNode = grid.NodeFromLocalPoint(this.grid.transform.InverseTransformPoint(targetPos));

        // target에 도착했는지 확인하는 변수.
        this.pathSuccess = false;

        if (!startNode.walkable)
            Debug.Log("Unwalkable StartNode 입니다.");

        // walkable한 targetNode인 경우 길찾기 시작.
        if(targetNode.walkable)
        {
            // openSet, closedSet 생성.
            // closedSet은 이미 계산 고려한 노드들.
            // openSet은 계산할 가치가 있는 노드들.
            List<Node> openSet = new List<Node>();
            HashSet<Node> closedSet = new HashSet<Node>();

            openSet.Add(startNode);

            // closedSet에서 가장 최저의 F를 가지는 노드를 빼낸다. 
            while (openSet.Count > 0)
            {
                // currentNode를 계산 후 openSet에서 빼야 한다.
                Node currentNode = openSet[0];
                // 모든 openSet에 대해, current보다 f값이 작거나, h(휴리스틱)값이 작으면 그것을 current로 지정.
                for (int i = 1; i < openSet.Count; i++)
                {
                    if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
                        currentNode = openSet[i];              
                }
                // openSet에서 current를 뺀 후, closedSet에 추가.
                openSet.Remove(currentNode);
                closedSet.Add(currentNode);

                // 방금 들어온 노드가 목적지 인 경우
                if (currentNode == targetNode)
                {
                    // seeker가 위치한 지점이 target이 아닌 경우
                    if(this.pathSuccess == false)
                    {
                       // wayQueue에 PATH를 넣어준다.
                       PushWay(RetracePath(startNode, targetNode) ) ;
                    }
                    this.pathSuccess = true;
                    break;
                }

                // current의 상하좌우 노드들에 대하여 g,h cost를 고려한다.
                foreach (Node neighbour in grid.GetNeighbours(currentNode))
                {
                    if (!neighbour.walkable || closedSet.Contains(neighbour)) continue;

                    // F cost 생성.
                    int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
                    // 이웃으로 가는 F cost가 이웃의 G보다 짧거나, 방문해볼 Openset에 그 값이 없다면,
                    if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
                    {
                        neighbour.gCost = newMovementCostToNeighbour;
                        neighbour.hCost = GetDistance(neighbour, targetNode);
                        neighbour.parent = currentNode;

                        // openSet에 추가.
                        if (!openSet.Contains(neighbour)) openSet.Add(neighbour);
                    }
                }
            }
        }

        this.isFindingPath = false;
        yield return null;

        // 길을 찾았을 경우(계산 다 끝난경우) 이동시킴.
        //if (pathSuccess == true)
        //{
        //    // 이동중이라는 변수 ON
        //    this.isWalking = true;
        //    // wayQueue를 따라 이동시킨다.
        //    while (this.wayQueue.Count > 0)
        //    {
        //        this.dir = this.wayQueue.First() - (Vector2)this.transform.position;
        //        //길찾기 조건 - 탐색 범위
        //        if (this.dist <= this.eyeRange)
        //        {
        //            this.rBody2D.velocity = this.dir.normalized * this.moveSpeed * Time.deltaTime * this.stun;
        //        }
        //        if ((Vector2)this.transform.position == this.wayQueue.First())
        //        {
        //            Debug.Log("Dequeue");
        //            this.wayQueue.Dequeue();
        //        }
        //        yield return new WaitForSeconds(0.02f);
        //    }
        //    // 이동중이라는 변수 OFF
        //    this.isWalking = false;
        //}
    }

    // WayQueue에 새로운 PATH를 넣어준다.
    private void PushWay(Vector2[] array)
    {
        this.wayQueue.Clear();
        foreach (Vector2 item in array) this.wayQueue.Enqueue(item);
    }

    // 현재 큐에 거꾸로 저장되어있으므로, 역순으로 wayQueue를 뒤집어준다. 
    private Vector2[] RetracePath(Node startNode, Node endNode)
    {
        List<Node> path = new List<Node>();
        Node currentNode  = endNode;
        while(currentNode != startNode)
        {
            path.Add(currentNode);
            currentNode = currentNode.parent;
        }
        path.Reverse();
        // Grid의 path에 찾은 길을 등록한다.
        this.grid.path = path;
        Vector2[] wayPoints = SimplifyPath(path);
        return wayPoints;
    }

    // Node에서 Vector 정보만 빼낸다.
    private Vector2[] SimplifyPath(List<Node> path)
    {
        List<Vector2> wayPoints = new List<Vector2>();

        for(int i = 0; i < path.Count; i++)
        {
            //var way = this.grid.transform.parent.TransformPoint(path[i].localPosiotion);
            wayPoints.Add(path[i].localPosiotion);
        }
        return wayPoints.ToArray();
    }

    // custom g cost 또는 휴리스틱 추정치를 계산하는 함수.
    // 매개변수로 들어오는 값에 따라 기능이 바뀝니다.
    private int GetDistance(Node nodeA, Node nodeB)
    {
        int dstX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
        int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);
        // 대각선 - 14, 상하좌우 - 10.
        if (dstX > dstY) return 14 * dstY + 10 * (dstX - dstY);
        return 14 * dstX + 10 * (dstY - dstX);
    }

    //몬스터와 플레이어의 위치의 x값을 비교하여 몬스터를 플립합니다.
    protected virtual void FlipMonster()
    {
        this.dirX = this.transform.position.x - this.target.transform.position.x;
        if (dirX > 0) this.transform.rotation = Quaternion.Euler(0, 180, 0);
        else this.transform.rotation = Quaternion.Euler(0, 0, 0);
    } 
}

 InverseTransformPoint()로 좌표계를 바꿔주어 생각보다 빠르게 문제를 해결할 수 있었다.

 

 

 일단 정상적으로 길찾기가 가능한 상황