A* 알고리즘을 이용한 길찾기

  A*(A star)알고리즘이란 출발점에서 목적지까지의 최단 거리를 찾는 알고리즘이다. 알고리즘을 테스트하기 위해 먼저 바닥과 벽을 씬에 배치했다.

  대충 이런 느낌이다. Hierachy의 A*는 빈 게임 오브젝트로, 여기에 필요한 스크립트를 넣을 예정이다. <Node>라는 이름으로 스크립트를 만들어준다. <Node> 스크립트는 오브젝트에 넣을 게 아니기 때문에 MonoBehaviour를 삭제해 준다.

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

public class Node 
{
    public bool bWalkable;
    public Vector3 WorldPositon;

    public Node Parent;  //현재 노드의 바로 직전 노드
    public int Cost_G;  //출발 노드에서 현재 노드까지 오는 데에 소요된 비용
    public int Cost_H;  //현재 노드에서 목적지까지 가는 데에 소요되는 예상 비용

    public int Grid_x;
    public int Grid_y;
    
    public int Cost_F  //Cost_G와 Cost_H를 더한 값. 이 Cost_F의 비용이 가장 적은 경로가 최단 경로가 된다
    {
        get {
            return Cost_G + Cost_H;
        }
        
    }

    public Node(bool _Walkable, Vector3 _WorldPos, int _gridx, int _gridy)
    {
        bWalkable = _Walkable;
        WorldPositon = _WorldPos;

        Grid_x = _gridx;
        Grid_y = _gridy;
    }
}

  그런 뒤 A*에 <Grid> 스크립트와 <PathFind> 스크립트를 넣어준다.

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

public class Grid : MonoBehaviour
{
    public Transform Player;
    public LayerMask UnWalkableMask;
    public Vector2 GridWorldSize;
    public float NodeRadius;
    Node[,] grid;
    float nodeDiamater;
    int gridSizeX, gridSizeY;

    void Start()
    {
        nodeDiamater = NodeRadius * 2;
        gridSizeX = Mathf.RoundToInt(GridWorldSize.x / nodeDiamater);  //정수 단위로 그리드 생성
        gridSizeY = Mathf.RoundToInt(GridWorldSize.y / nodeDiamater);
        CreateGrid();
    }
    void CreateGrid()
    {
        grid = new Node[gridSizeX, gridSizeY];

        Vector3 worldBottomleft = transform.position - Vector3.right * GridWorldSize.x / 2 - Vector3.forward * GridWorldSize.y / 2; //생성한 그리드의 왼쪽 최하단

        for (int x = 0; x < gridSizeX; x++)
        {
            for (int y = 0; y < gridSizeY; y++)
            {
                Vector3 worldPoint = worldBottomleft + Vector3.right * (x * nodeDiamater + NodeRadius) + Vector3.forward * (y * nodeDiamater + NodeRadius);
                bool Walkable = !(Physics.CheckSphere(worldPoint, NodeRadius, UnWalkableMask)); //막혀 있는지 체크
                grid[x, y] = new Node(Walkable, worldPoint,x,y);  //막힌 곳과 막히지 않은 곳을 구분해서 그리드 생성
            }
        }

    }
    //주변 1칸씩 탐색
    public List<Node> GetNeighbour(Node node)
    {
        List<Node> neighbour = 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.Grid_x + x;
                int checkY = node.Grid_y + y;
                if (checkX >= 0 && checkY < gridSizeX && checkY >= 0 && checkY < gridSizeY)
                {
                    neighbour.Add(grid[checkX, checkY]);
                }
            }
        
        return neighbour;
    }
    //노드의 위치를 월드 좌표로 변환
    public Node NodeWorldPoint(Vector3 worldPos)
    {
        float percentX = (worldPos.x + GridWorldSize.x / 2) / gridSizeX;
        float percentY = (worldPos.z + GridWorldSize.y / 2) / gridSizeY;

        percentX = Mathf.Clamp01(percentX);
        percentY = Mathf.Clamp01(percentY);

        int x = Mathf.RoundToInt((gridSizeX - 1) * percentX);
        int y = Mathf.RoundToInt((gridSizeY - 1) * percentY);

        return grid[x, y];
    }

    public List<Node> path;
    private void OnDrawGizmos()
    {
        Gizmos.DrawWireCube(transform.position, new Vector3(GridWorldSize.x, 0.5f, GridWorldSize.y));
        
        if (grid != null)
        {
            Node playerNode = NodeWorldPoint(Player.position);

            foreach (Node n in grid) {
                Gizmos.color = (n.bWalkable) ? Color.green : Color.red;
                if (path != null)
                    if (path.Contains(n))
                        Gizmos.color = Color.black;

                if (playerNode == n)
                {
                    Gizmos.color = Color.cyan;
                }
                Gizmos.DrawCube(n.WorldPositon, Vector3.one * (nodeDiamater - 0.1f));
            }
        }
    }

}

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

public class PathFind : MonoBehaviour
{
    Grid Grid;
    public Transform Seeker, Target;

    private void Awake()
    {
        Grid = GetComponent<Grid>();
    }
    private void Update()
    {
        FindPath(Seeker.position, Target.position);
    }
    void FindPath(Vector3 startPos, Vector3 TargetPos)
    {
        Node StartNode = Grid.NodeWorldPoint(startPos);
        Node TargetNode = Grid.NodeWorldPoint(TargetPos);

        List<Node> openset = new List<Node>();  //열린 목록(후보 경로)
        HashSet<Node> closeset = new HashSet<Node>(); //닫힌 목록(확정한 경로)

        openset.Add(StartNode);
        
        //openSet의 개수가 0이 될 때까지 반복
        while (openset.Count > 0)
        {
            Node CurrentNode = openset[0];
            //현재 노드의 Cost와 열린 목록의 Cost를 비교해서 Cost가 더 낮은 노드를 닫힌 목록에 저장
            for (int i = 1; i < openset.Count; i++)
            {
                if (openset[i].Cost_F < CurrentNode.Cost_F || openset[i].Cost_F == CurrentNode.Cost_F
                    && openset[i].Cost_H < CurrentNode.Cost_H)
                {
                    CurrentNode = openset[i];
                }
            }
            openset.Remove(CurrentNode);
            closeset.Add(CurrentNode);

            if (CurrentNode == TargetNode) //현재 노드와 TargetNode가 같으면 탐색 종지
            {
                ReTracePath(StartNode, TargetNode);
                return;
            }

            //탐색한 지역은 재탐색하지 않음
            foreach (Node neighbour in Grid.GetNeighbour(CurrentNode)) {
                if (!neighbour.bWalkable || closeset.Contains(neighbour))
                {
                    continue;
                }

                int newMovementCostToNeighbour = CurrentNode.Cost_G + GetDistance(CurrentNode, neighbour);
                if (newMovementCostToNeighbour < neighbour.Cost_G || !openset.Contains(neighbour))
                {
                    neighbour.Cost_G = newMovementCostToNeighbour;
                    neighbour.Cost_H = GetDistance(neighbour, TargetNode);
                    neighbour.Parent = CurrentNode;

                    if (!openset.Contains(neighbour))
                        openset.Add(neighbour);
                }

            }
        }
    }

    //현재 위치가 바뀔 때마다 경로를 새로 계산한다
    void 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 = Path;
    }

    int GetDistance(Node nodeA, Node nodeB)
    {
        int dstX = Mathf.Abs(nodeA.Grid_x - nodeB.Grid_x);
        int dstY = Mathf.Abs(nodeA.Grid_y - nodeB.Grid_y);

        if (dstX > dstY)
            return 14 * dstY + 10 * (dstX - dstY);
        return 14 * dstX + 10 * (dstY - dstX);
    }
}

  그런 뒤 A*의 인스펙터 창에서 Seeker와 Target에 각각 target과 Player를 넣으면 된다.