[유니티]A* 알고리즘(에이스타 알고리즘)을 통해서 길찾기[구현]

https://sharp2studio.tistory.com/42

A* 알고리즘(에이스타 알고리즘)을 통해서 길찾기 구현(이론)

앞선 포스팅에서 A* 알고리즘이 어떤건지에 대해서 알아보았다. 이어서 실제 게임에서 적용되는 모습을 보이도록 하겠다.

 

 

우선 클릭한 위치로 이동해주는 간단한 함수를 만들어 준다.

잘 되는데?

 

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

public class Player : MonoBehaviour
{

    Vector3 mousePosition;
    Animator anim;
    void Start()
    {
        anim = GetComponent<Animator>();
    }

         void Update()
        {
            if (Input.GetMouseButtonDown(0))
            {
                mousePosition = camera.ScreenToWorldPoint(Input.mousePosition);
                mousePosition = new Vector3(mousePosition.x, mousePosition.y, 0);
                anim.SetBool("Run", true);
            }
            if (transform.position != mousePosition)
            {
            transform.position = Vector3.MoveTowards(transform.position, mousePosition, Time.deltaTime*3);
                if (transform.position.x < mousePosition.x)
                {
                transform.localScale = new Vector3(-1, 1, 1);
                }
                else if(transform.position.x>mousePosition.x)
                {
                transform.localScale = new Vector3(1, 1, 1);
                }
                if (transform.position == mousePosition)
                {
                    anim.SetBool("Run",false);
                }           
            }
        }
  }

mousePosition을 입력 받아서, 그 위치로 이동시키고 해당 위치가 내 위치와 같다면 이동을 멈춰주는 간단한 스크립트이다.

하지만 이렇게 짜면, 중간에 장애물이 있어도 인지하지 못하게 되는데

뭐든지 다 뚫어버린다.

따라서 이러한 상황에서는 길찾기 알고리즘을 통해 내가 갈 수 있는 길, 갈 수 없는 길을 구분하는것이 중요한데 여기서 A*알고리즘이 쓰일 것이다.

 

가장 처음에 할 것은 게임 속 화면을 그리드화 시키는 과정이다.

Grid.cs 파일과 Node.cs파일을 만들어 주도록 한다.

Node.cs파일은 특정 노드에 대한 정보를 담을 것이며, Grid.cs파일은 노드 전체를 관리하는 형태로 진행될 것이다.

먼저 Node.cs파일이다.

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

public class Node 
{
    public bool canWalk;
    public Vector3 myPos;
    public int myX;
    public int myY;
    public int gCost;
    public int hCost;

    public Node par;
    public Node(bool walk,Vector3 pos,int X,int Y)
    {
        canWalk = walk; //지나갈 수 있는 노드인지
        myPos = pos; //노드의 게임 내 vector값
        myX = X;  //노드의 x좌표 값
        myY = Y;  //노드의 y좌표 값
    }
    public int fcost
    {
        get { return gCost + hCost; }
    }
   
}

빈 오브젝트를 만들어 주고 Grid.cs 스크립트를 넣어준다.
게임 상 가장 하단 왼쪽을 (0,0)좌표로 두고 시작을 하면 보다 간편하게 노드들의 위치를 구할 수 있다.

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

public class Grid : MonoBehaviour
{
    public Vector2 worldSize; //게임 상 맵의 크기
    public float nodeSize; //노드의 크기
    [SerializeField]Node[,] myNode; //전체 노드를 관리할 배열
    int nodeCountX; //노드의 X방향 개수
    int nodeCountY; //노드의 Y방향 개수
    [SerializeField] LayerMask obstacle; //장애물인지 아닌지 구분해 줄 LayerMask
     public List<Node> path; //예상 경로


    private void Start()
    {
        nodeCountX = Mathf.CeilToInt(worldSize.x / nodeSize); //노드의 크기에 따라서 개수가 달라진다.
        //노드가 커지면 개수가 작고,정확도는 낮지만 계산이 빨라지고
        //반대로 노드가 작아지면 개수가 많아져서 정확도는 올라가지만 계산속도가 느려진다.
        nodeCountY = Mathf.CeilToInt(worldSize.y / nodeSize);
        myNode = new Node[nodeCountX, nodeCountY];
        for(int i = 0; i < nodeCountX; i++)
        {
            for(int j = 0; j < nodeCountY; j++)
            {
                Vector3 pos = new Vector3(i * nodeSize, j * nodeSize); //노드의 좌표
                Collider2D hit = Physics2D.OverlapBox(pos, new Vector2(nodeSize/2, nodeSize/2), 0, obstacle);
                bool noHit = false;
                if (hit == null)  noHit = true;
                myNode[i, j] = new Node(noHit, pos,i,j); //노드를 생성해준다.
            }
        }      
    }
  }

 

 

 

 

Collider2D hit = Physics2D.OverlapBox(pos, new Vector2(nodeSize/2, nodeSize/2), 0, obstacle);
bool noHit = false;
if (hit == null)  noHit = true;

이 부분은 노드가 지나갈 수 있는지 없는지 구분해주는 부분인데, 이를 위해서

장애물들의 Layer들을 모두 obstacle이라는 Layer로 바꿔주도록 한다.

 

즉 해당 노드에 obstacle이라는 layermask가 감지된다면, 이는 지나갈 수 없는 노드로 판단이 될 것이다.

이어서 시각적으로 지나갈 수 없는 노드와 지나갈 수 있는 노드를 구분하도록 grid.cs에 새로운 함수를 만들어 준다.

private void OnDrawGizmos()
      {
          Gizmos.DrawWireCube(transform.position, new Vector3(worldSize.x, worldSize.y, 1));
          if (myNode != null)
          {
              foreach(Node no in myNode)
              {
                  Gizmos.color = (no.canWalk) ? Color.white : Color.red;
                  Gizmos.DrawCube(no.myPos, Vector3.one * (nodeSize/2));
              }
          }
      }

MyNode에 있는 모든 노드에 cube를 그릴건데, 만약 canwalk상태라면 white 큐브를,canwalk가 아니라면 red 큐브를 그려준다.

grid.cs에 해당 함수까지 넣고 실행을 하면 

Scene화면

내가 지나갈 수 있는 길과 장애물이 섞인 길을 구분을 할 수 있게 된다.

 

이제 출발점과 도착점을 입력 받아서 경로를 찾아내는 pathfinding.cs라는 스크립트를 만들어 주도록 한다.

또한 grid.cs 스크립트에 새로운 함수 두가지를 추가할건데, 특정 노드에 도착하면 주변 노드들을 불러와주는 SearchNeightborNode와, 마우스로 특정 좌표를 클릭했을 때 그 좌표가 어떤 노드에 포함되어있는지 알려주는 GetNodeFromVector함수이다.

public List<Node> SearchNeightborNode(Node node)
    {
        
        List<Node> nodeList = new List<Node>();
        for(int i = -1; i < 2; i++) 
        {
            for(int j = -1; j < 2; j++)
            {
                if (i == 0 && j == 0) continue; //9가지 방향 중 (0,0)방향은 자기 자신이기때문에 생략

                int newX = node.myX + i;
                int newY = node.myY + j;

                if (newX >= 0 && newY >= 0 && newX < nodeCountX && newY < nodeCountY)
                {
                    nodeList.Add(myNode[newX,newY]);
                }
            }
        }
        return nodeList;
    }

    public Node GetNodeFromVector(Vector3 vector) 
    {
        int posX = Mathf.RoundToInt(vector.x / nodeSize); //반올림해서 어디 노드인지 확인
        int posY = Mathf.RoundToInt(vector.y / nodeSize);
        return myNode[posX,posY];
    }

이제 Pathfinding.cs 스크립트이다. 위 스크립트도 Grid 스크립트를 넣은 오브젝트와 같은 오브젝트에 넣어주도록 하자.

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

public class Pathfinding : MonoBehaviour
{
    Grid grid;
    private void Start()
    {
        grid = GetComponent<Grid>();
    }
    public List<Node> PathFind(Vector3 startPos,Vector3 endPos) //출발점과 도착점을 받는다.
    {
        List<Node> openList = new List<Node>();
        HashSet<Node> closedList = new HashSet<Node>(); //closedlist는 포함되어있는지만 확인하기 때문에 hashset으로
        Node startNode = grid.GetNodeFromVector(startPos); //위에서 만들었던 함수이다.
        Node endNode = grid.GetNodeFromVector(endPos);
        openList.Add(startNode); //openList에 시작점을 넣고
        while (openList.Count > 0)
        {
            Node curNode = openList[0];//curNode를 openList의 첫 노드로
           
            for(int i = 1; i < openList.Count; i++) //만약 openList에 다른 노드가 더 있다면, 비교해서 최선의 노드를 찾는다.
            {
                if (openList[i].fcost < curNode.fcost || openList[i].fcost == curNode.fcost)
                { //최적의 노드를 탐색하는 과정. fcost가 가장 낮은 노드가 curNode가 된다.
                 
                    curNode = openList[i]; 
                }
            }
            openList.Remove(curNode); 
            closedList.Add(curNode);  //closedList에 탐색을 한 현재 노드를 넣는다.    
            if(curNode==endNode)
            {   //현재노드가 도착지라면 탐색을 종료하고 endNode부터 역방향으로 탐색을 시작한다.
                 return Retrace(startNode, curNode);             
            }       
            foreach (Node neightborNode in grid.SearchNeightborNode(curNode))
            {
             //주변 노드들을 불러오는 함수
                if (neightborNode.canWalk && !closedList.Contains(neightborNode))
                {     //주변 노드중에 접근이 가능하고, closedList에 없는 노드만 접근한다.
                    int x = curNode.myX - neightborNode.myX;
                    int y = curNode.myY - neightborNode.myY;
                    int newCost = curNode.gCost + GetDistance(neightborNode, curNode);
                   //getDistance라는 함수는 노드 사이의 거리를 잴 때 사용
                    if (newCost < neightborNode.gCost || !openList.Contains(neightborNode))
                    { //오픈리스트에 위 노드가 없거나,있어도 새로 구한 gcost 가 더 작을경우엔
                    //gcost를 다시 계산한 값으로 넣어준다. 또한 par노드 또한 변경해준다.
                        neightborNode.gCost = newCost;
                        neightborNode.hCost = GetDistance(neightborNode, endNode);
                        neightborNode.par = curNode;
                        
                        if (!openList.Contains(neightborNode)) {openList.Add(neightborNode); }
                    }
                }
            }
        }
        return null; //만약 모든 노드를 탐색했는데 목적지를 찾지 못 하면 null값을 반환
    }
    List<Node> Retrace(Node start,Node end) //목적지 노드를 방문했을 때 호출되는 함수
    {
        List<Node> path = new List<Node>();
        Node curNode = end;
        while (curNode != start)
        {
  //각각의 par들을 계속해서 방문해주고,리스트에 넣은다.      
            path.Add(curNode);
            curNode = curNode.par;
        }
        path.Reverse();
        //그 후 완성된 리스트를 역정렬 해주면 출발점부터 도착점까지가 된다.
        grid.path = path;
        return path;
    }
    int GetDistance(Node aNode,Node bNode) //두가지 노드가 주어지면 거리 가중치를 계산하는 함수이다.
    {
        int x = Mathf.Abs(aNode.myX - bNode.myX);
        int y = Mathf.Abs(aNode.myY - bNode.myY);
        //절대값으로 계산을 해주고, 절대값이 더 작은만큼은 대각선으로 이동하는게 합리적이고,초과치는 직선으로 이동한다. 
        if (x > y) return 14 * y + 10 * (x - y);
        return 14 * x + 10 * (y - x);
    }
}

 

이제 grid 스크립트와 Player스크립트를 약간 수정해서 구해진 경로를 눈에 보이게 해보자.

.gird 스크립트의 OnDrawGizmos 함수를 다음과 같이 수정해준다.

 private void OnDrawGizmos()
      {
          Gizmos.DrawWireCube(transform.position, new Vector3(worldSize.x, worldSize.y, 1));
          if (myNode != null)
          {
              foreach(Node no in myNode)
              {
                  Gizmos.color = (no.canWalk) ? Color.white : Color.red;
                if (path != null) 
                {
                    if (path.Contains(no)) //경로에 포함이 된 노드는 검정색큐브로 표시
                    {
                        Gizmos.color = Color.black;
                    }
                }
                  Gizmos.DrawCube(no.myPos, Vector3.one * (nodeSize/2));
              }
          }
      }

Player.cs는 다음과같이 수정해준다.

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

public class Player : MonoBehaviour
{

    Vector3 mousePosition;
    Animator anim;
   [SerializeField] Pathfinding path;
   
    void Start()
    {
        anim = GetComponent<Animator>();
    }

         void Update()
        {
            if (Input.GetMouseButtonDown(0))
            {
                mousePosition = camera.ScreenToWorldPoint(Input.mousePosition);
                mousePosition = new Vector3(mousePosition.x, mousePosition.y, 0);
                anim.SetBool("Run", true);
                path.PathFind(transform.position, mousePosition);
            }
            if (transform.position != mousePosition)
            {
           
                if (transform.position.x < mousePosition.x)
                {
                transform.localScale = new Vector3(-1, 1, 1);
                }
                else if(transform.position.x>mousePosition.x)
                {
                transform.localScale = new Vector3(1, 1, 1);
                }
                if (transform.position == mousePosition)
                {
                    anim.SetBool("Run",false);
                }           
            }
        }
  }

이렇게 수정하면, 클릭 시 path.PathFind함수가 작동해서 직선으로 가는 방법이 아닌 새로운 path를 찾아서 보여준다.

또한 이동 로직도 완전히 바뀔예정이기 때문에 이동을 담당하는 movetowards부분도 없애주도록 하자.

오른쪽 게임 뷰에서 마우스 클릭을 해주면, 해당 노드까지의 동선이 검은색으로 표시되는 모습을 볼 수 있다.

이제 표시된 동선을 따라서 이동을 해주는 것까지 구현을 하기위해 Player.cs 스크립트를 수정해주자.

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

public class Player : MonoBehaviour
{

    Vector3 mousePosition;
    [SerializeField] Camera camera;
    [SerializeField] Pathfinding path;
   
    Animator anim;
    List<Node> myWay;
    Node targetNode;
    void Start()
    {
        anim = GetComponent<Animator>();
    }

        

    void Update()
    {
        if (Input.GetMouseButtonDown(0))
        {
            mousePosition = camera.ScreenToWorldPoint(Input.mousePosition);
            mousePosition = new Vector3(mousePosition.x, mousePosition.y, 0);         
            List<Node> newWay=path.PathFind(transform.position, mousePosition);
            if (newWay != null) //path를 찾아오지 못하면 이동하지 않는다.
            //즉, 이동 불가능한 곳 클릭 시 아예 이동하지 않도록 설정이 되어있는데,
            //이는 게임마다 다르기 때문에 본인이 원하는 방식으로 수정을 하면 된다.
            {
                StopCoroutine("move");
                anim.SetBool("Run", true);         
                myWay = newWay;
                StartCoroutine("move"); 
                if (transform.position.x < mousePosition.x)
                {
                    transform.localScale = new Vector3(-1, 1, 1);
                }
                else if (transform.position.x > mousePosition.x)
                {
                    transform.localScale = new Vector3(1, 1, 1);
                }
            }

        }

    }
    IEnumerator move()
    {
        int idx = 0;
        targetNode = myWay[0]; //시작 점
        while (true)
        {
            if (transform.position == targetNode.myPos) //내위치가 타켓 노드까지 왔다면,
            //새로운 타겟 노드를 설정해줘야한다.
            {
                idx++; //인덱스 값을 올려서 다음 경로의 노드 탐색
                if (idx >= myWay.Count) //만약 인덱스값이 경로의 개수와 같아진다면, 도착했음을 뜻함
                {
                    anim.SetBool("Run", false);
                    yield break; //빠져나와준다.
                }
                targetNode = myWay[idx];
                if (transform.position.x < targetNode.myPos.x)
                {
                   transform.localScale = new Vector3(-1, 1, 1);
                }
                else if (transform.position.x >targetNode.myPos.x)
                {
                    transform.localScale = new Vector3(1, 1, 1);
                }
            }
            transform.position = Vector2.MoveTowards(transform.position, targetNode.myPos,Time.deltaTime*3);
           //타겟 노드까지 이동해준다.
           yield return null;
        }
    }

}

 

이제 적용된 모습을 보도록 하자.

완성!!

 

 

 

 

 

 

[참고]

https://www.youtube.com/watch?v=nhiFx28e7JY&t=864s 

 

 

 

자세한 코드들은 깃허브에 업로드 했습니다.

https://github.com/raetic/A-algorithm-With-Unity

GitHub - raetic/A-algorithm-With-Unity: 유니티 엔진 내에서 A* 알고리즘을 구현한 공부용 토이 프로젝트