A* 알고리즘 with Unity 02

결과 그림이다. Inspector 창에 Seeker (경로를 찾는 자), Target(경로 도착지)를 설정해준다.

 

 

using System.Collections.Generic;
using UnityEngine;

public class Grid : MonoBehaviour
{
    public LayerMask unwalkableMask;

    Node[,] grid;

    Vector2 gridSize;
    float nodeRadius;              //노드 반지름
    float nodeDiameter;            //노드 지름
    int gridXCount, gridYCount;   //Grid X축 Node 갯수, Grid Y축 Node 갯수

    private void Awake()
    {
        gridSize = new Vector2(40, 40);
        nodeRadius = 0.5f;
        nodeDiameter = nodeRadius * 2f;

        gridXCount = Mathf.RoundToInt(gridSize.x / nodeDiameter);
        gridYCount = Mathf.RoundToInt(gridSize.y / nodeDiameter);

        CreateGrid();

    }
   public List<Node> GetNearByNode(Node currentNode)
    {
        List<Node> NearByNodes = new List<Node>();

        // 해당되는 노드의 붙어있는 노드를 체크하여 List에 담는다.
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                // 본인 자신이면 넘어간다.
                if (x == 0 && y == 0)
                    continue;

                int check_X = currentNode.gridX + x;
                int check_Y = currentNode.gridY + y;
                // 범위내 주변노드가 맞다면 List에 저장한다.
                if ((0 <= check_X && check_X < gridXCount) &&
                    (0 <= check_Y && check_Y < gridYCount))
                    NearByNodes.Add(grid[check_X, check_Y]);
            }
        }
        return NearByNodes;
    }

    private void CreateGrid()
    {
        grid = new Node[gridXCount, gridYCount]; // [40,40]
        Vector3 worldBottomLeft = transform.position - new Vector3((gridSize.x * 0.5f), 0, (gridSize.y * 0.5f));

        for (int x = 0; x < gridXCount; x++)
        {
            for (int y = 0; y < gridYCount; y++)
            {
                Vector3 worldPosition = worldBottomLeft + new Vector3((x * nodeDiameter + nodeRadius), 0, (y * nodeDiameter + nodeRadius));
                bool walkable = !(Physics.CheckSphere(worldPosition, nodeRadius, unwalkableMask));

                grid[x, y] = new Node(walkable, worldPosition, x, y);
            }
        }

    }

    public Node GetNodeFromWorldPosition(Vector3 WP)
    {
        float percen_X = (WP.x + gridSize.x * 0.5f) / gridSize.x;
        float percen_Y = (WP.z + gridSize.y * 0.5f) / gridSize.y;

        percen_X = Mathf.Clamp01(percen_X);
        percen_Y = Mathf.Clamp01(percen_Y);

        int x = Mathf.RoundToInt((gridXCount - 1) * percen_X);
        int y = Mathf.RoundToInt((gridYCount - 1) * percen_Y);

        return grid[x, y];
    }

    
}

 

using UnityEngine;

public class Node
{
	// 이전 Node를 기억해준다.
    public Node parent;

    public bool IsWalkable;
    public Vector3 worldPosition;

    public int gridX, gridY;

    // 노드의 현재까지 움직인 비용.
    public int gCost;
    // 노드가 도착점까지 예상되는 비용.
    public int hCost; 

    //비용의 총합
    public int Fcost { get => gCost + hCost; }

    public Node(bool walkable, Vector3 pos, int x, int y)
    {
        this.IsWalkable = walkable;
        worldPosition = pos;
        gridX = x;
        gridY = y;
    }
}

 

 

using System.Collections.Generic;
using UnityEngine;

public class PathManager : MonoBehaviour
{
    public Transform seeker, target;
    [SerializeField] private Grid grid;
    List<Node> path;
    private void Awake()
    {
        grid = GetComponent<Grid>();
    }
    private void Update() // 실시간
    {
        FindPath(seeker.position, target.position);
    }
    
    private void FindPath(Vector3 seeker, Vector3 target)
    {
        // openSet은 비용적으로 효율적인 Node를 모아 놓는 List이다.
        List<Node> openSet = new List<Node>();
        // closeSet은 여지껏 왔던 Node 중 왔던 길,혹은 비용적으로 비효율적인 Node를 모아 놓은 HashSet이다.
        HashSet<Node> closeSet = new HashSet<Node>();

        Node startNode = grid.GetNodeFromWorldPosition(seeker); // 출발 Node[x,y]
        Node targetNode = grid.GetNodeFromWorldPosition(target); // 도착 Node[x,y]

        openSet.Add(startNode); // 효율적인 Node면 저장해 놓는다.
        while (openSet.Count > 0)
        {
            //openSet List에서 가장 적은 비용의 Node를 찾는다.
            Node currentNode = openSet[0];
            for (int i = 0; i < openSet.Count; i++)
            {
                // 임시로 담겨있는 Node currentNode에서 비용이 작은 Node를 뽑아 그것으로 바꿔준다.
                // 만약 Fcost 비용이 같은 경우 앞으로 갈 비용 중 가장 적은 Node를 우선순위로 둔다.
                if (openSet[i].Fcost < currentNode.Fcost ||
                   (openSet[i].Fcost == currentNode.Fcost && openSet[i].hCost < currentNode.hCost))
                    currentNode = openSet[i];
            }
            // 뽑은 Node는 openSet에 없애주고, CloseSet에 담겨준다.
            openSet.Remove(currentNode);
            closeSet.Add(currentNode);

            //뽑은 노드와 타켓 노드가 같으면 도착했으므로 탐색을 그만둔다.
            if (currentNode == targetNode)
            {
                GetPath(startNode, targetNode);
                break;
            }

            //뽑은 노드의 주변 노드를 List로 받아 확인한다.
            foreach (Node nearByNode in grid.GetNearByNode(currentNode))
            {
                if (closeSet.Contains(nearByNode) || !nearByNode.IsWalkable)
                    continue;

                // 비용 계산
                int newGCost = currentNode.gCost + GetDistance(currentNode, nearByNode);
                //기존 openSet에 있는 노드라면
                if (openSet.Contains(nearByNode))
                {
                    if (newGCost < nearByNode.gCost) // 계산한 gcost가 낮다면
                    {
                        nearByNode.gCost = newGCost; // 갱신시켜준다.
                        nearByNode.parent = currentNode; // 부모 노드를 저장시킨다.

                    }

                }
                else // 처음 접하는 Node일 경우
                {
                    nearByNode.gCost = newGCost;
                    nearByNode.hCost = GetDistance(nearByNode, targetNode);
                    nearByNode.parent = currentNode;
                    openSet.Add(nearByNode);
                }
            }
        }
    }

    int GetDistance(Node Node_A, Node Node_B)
    {
        int dist_X = Mathf.Abs(Node_A.gridX - Node_B.gridX);
        int dist_Y = Mathf.Abs(Node_A.gridY - Node_B.gridY);

        //길이가 짧은 곳을 먼저 대각선으로 간 후,
        //길이가 긴쪽에서 짧은 쪽을 뺀 만큼을 더 직직 이동 시킨다.
        if (dist_X > dist_Y)
            return 14 * dist_Y + 10 * (dist_X - dist_Y);
        else
            return 14 * dist_X + 10 * (dist_Y - dist_X);
    }

    void GetPath(Node startNode, Node targetNode)
    {
        path= new List<Node>();

        Node currentNode = targetNode;

        while(true)
        {
            path.Add(currentNode);

            if (currentNode == startNode)
                break;

            currentNode = currentNode.parent;
        }
    }

    private void OnDrawGizmos()
    {
        if(path !=null)
            foreach (var node in path)
            {
                Gizmos.color = Color.black;
                Gizmos.DrawCube(node.worldPosition, Vector3.one);

            }
    }
}