[Unity] C#으로 A* 알고리즘 구현하기 (대각선 여부, 코너 여부)

A star 알고리즘

가중치를 이용한 길찾기 알고리즘

 

g(n) = 출발 꼭짓점으로부터 꼭짓점까지의 경로 가중치

h(n) = 꼭짓점 n으로부터 목표 꼭짓점까지의 추정 경로 가중치

f = g + h

타일맵으로 대충 맵과 벽을 그려줍니다. 

길찾기의 시작 지점과, 도착지점을 지정하는 create empty와 밑바닥의 위치와 제일 높은곳의 위치를 찍어줍시다.

 

길찾기 스크립트를 GameManager에 작성해 줄 겁니다.!!

 

코드 리뷰

[System.Serializable]
public class Node
{
    public bool isWall;
    public Node ParentNode;
    public int x, y;
    //G: 시작으로부터 이동했던 거리
    public int G;
    //H: 추정값, 즉 가로 + 세로 장애물을 무시하여 목표까지의 거리
    public int H;
    //F: G + H;
    public int F
    {
        get { return H + G; }
    }

    public Node(bool isWall, int x, int y)
    {
        this.isWall = isWall;
        this.x = x;
        this.y = y;
    }
}

저희는 노드 단위로 알아 볼 겁니다. node라는 이름의 클래스를 파주고, 유니티 씬에서 이에 관한 내용들을 확인할 수 있게 System.Serializable 키워드를 붙여줍니다.

벽인지 확인하는 bool 변수, 부모 노드를 저장하는 Node타입의 부모노드.

좌표를 나타내는 x, y 와 시작으로부터 이동한 거리인 G, 목표까지의 추정값인 H, 이를 합한 F까지 선언해줍니다.

Node는 벽인지 저장한 bool변수와 본인의 x, y 좌표 총 3가지의 정보를 담게 해뒀습니다.

 

public class GameManager : MonoBehaviour
{
    public GameObject Start_pos, End_pos;
    public GameObject BottomLeft_ob, TopRight_ob;

    [SerializeField] private Vector2Int bottomleft, topright, start_pos, end_pos;

    public List<Node> Final_nodelist;

    //대각선을 이용할것인지, 코너를 가로질러 가지 않을 경우 이동중 수직 수평 장애물이 있는지 판단
    public bool AllowDiagonal, dontCrossCorner;

    int SizeX, SizeY;
    Node[,] nodeArray;
    Node Startnode, Endnode, CurNode;

    List<Node> OpenList, CloseList;

GameManager 클래스에서는 위와 같은 부분들을 선언해주었습니다.

inspector창에서 드래그로 넣어줄 Start_pos, End_pos, BottomLeft_ob, TopRight_ob가 있으며, 이를 Vector2값으로 변환할 변수 선언도 해주었습니다.

결과를 저장할 node형식으로 list를 저장하는 친구도 선언해줍니다.

 

대각선이용을 허가 / 불허 하는 변수와 코너를 가로질러가지 않을 때 장애물을 건너뛰는지 아닌지를 판단하는 bool 변수를 선언해주었습니다.

SizeX는 x축의 그리드 개수를, SizeY는 y축 그리드 개수를 나타내며, node를 2차원 배열로 받는 nodeArray와 시작, 마지막, 현재 노드의 노드를 선언해줍니다.

마지막으로 열린 리스트에 있는지, 닫힌 리스트에 있는지를 구별해서 선언해줍니다.

 

 public void SetPosition()
    {
        bottomleft = new Vector2Int((int)BottomLeft_ob.transform.position.x, (int)BottomLeft_ob.transform.position.y);
        topright = new Vector2Int((int)TopRight_ob.transform.position.x, (int)TopRight_ob.transform.position.y);
        start_pos = new Vector2Int((int)Start_pos.transform.position.x, (int)Start_pos.transform.position.y);
        end_pos = new Vector2Int((int)End_pos.transform.position.x, (int)End_pos.transform.position.y);
    }

BottomLeft의 x좌표, y좌표를 Vector2형식으로 바꿔서 저장하고, 4가지 변수를 모두 위와같이 Vector2 형식으로 바꿔줍니다.

 

여기부터 길찾기 알고리즘 식이 계속됩니다.

    public void PathFinding()
    {
        SetPosition();

        SizeX = topright.x - bottomleft.x + 1; //0, 0때문에 +1
        SizeY = topright.y - bottomleft.y + 1;

        nodeArray = new Node[SizeX, SizeY];
        //모든 노드를 담는 과정

        for (int i = 0; i < SizeX; i++)
        {
            for (int j = 0; j < SizeY; j++)
            {
                bool iswall = false;
                foreach (Collider2D col in
                    Physics2D.OverlapCircleAll(new Vector2(i + bottomleft.x, j + bottomleft.y), 0.4f))
                {
                    if (col.gameObject.layer == LayerMask.NameToLayer("Wall"))
                    {
                        iswall = true;
                    }
                }
                nodeArray[i, j] = new Node(iswall, i + bottomleft.x, j + bottomleft.y);
            }
        }

setposition으로 초기화를 시켜준 다음, 시작화면 우측위의 x와 좌측아래의 x값을 빼서 SizeX, SizeY를 넣어줍니다.

nodeArray에 X크기, Y크기만큼의 Node를 담겠다고 선언해줍니다.

x가 0부터 크기까지, Y도 0부터 크기까지 반복하여 iswall은 false로 초기화해주고, overlapCircleAll을 이용해 이를 판단합니다. Vector2의 왼쪽아래 기준부터 시작해 x값과 y값 포지션에서 0.4f만큼의 반경에서 찾아 col의 layer가 wall이면 wall이라고 판단해 true로 바꿔 nodeArray에 값을 저장합니다.

 

        //시작과 끝 노드, 열린 리스트와 닫힌 리스트 최종 경로 리스트 초기화 작업
        Startnode = nodeArray[start_pos.x - bottomleft.x, start_pos.y - bottomleft.y];
        Endnode = nodeArray[end_pos.x - bottomleft.x, end_pos.y - bottomleft.y];

        OpenList = new List<Node>();
        CloseList = new List<Node>();
        Final_nodelist = new List<Node>();

        OpenList.Add(Startnode);

시작노드는 array에서 초기 위치를 뺀 곳의 원소, end는 도착지에서 뺀 곳으로 초기화를 시키며

openlist, closelist, final list를 생성해 openlist에 시작위치를 넣어줍니다.

 

        while (OpenList.Count > 0)
        {
            CurNode = OpenList[0];
            for (int i = 0; i < OpenList.Count; i++)
            {
                //열린 리스트 중 가장 f가 작고 f가 같다면
                //h가 작은 것을 현재 노드로 설정하고 열린 리스트에서 닫힌 리스트로 옮기기
                if (OpenList[i].F <= CurNode.F &&
                    OpenList[i].H < CurNode.H)
                {
                    CurNode = OpenList[i];
                }
            }

            //열린 리스트에서 닫힌 리스트로 옮기기
            OpenList.Remove(CurNode);
            CloseList.Add(CurNode);

            //도착지에 도착했을때
            if (CurNode == Endnode)
            {
                Node targetNode = Endnode;
                while (targetNode != Startnode)
                {
                    Final_nodelist.Add(targetNode);
                    targetNode = targetNode.ParentNode;
                }
                Final_nodelist.Add(Startnode);
                Final_nodelist.Reverse();

                for (int i = 0; i < Final_nodelist.Count; i++)
                {
                    Debug.Log(i + "번 째는 "+Final_nodelist[i].x + " | " + Final_nodelist[i].y);
                }
                return;
            }

            if (AllowDiagonal)
            {
                OpenListAdd(CurNode.x + 1, CurNode.y - 1);
                OpenListAdd(CurNode.x - 1, CurNode.y + 1);
                OpenListAdd(CurNode.x + 1, CurNode.y + 1);
                OpenListAdd(CurNode.x - 1, CurNode.y - 1);
            }

            OpenListAdd(CurNode.x + 1, CurNode.y);
            OpenListAdd(CurNode.x - 1, CurNode.y);
            OpenListAdd(CurNode.x, CurNode.y + 1);
            OpenListAdd(CurNode.x, CurNode.y - 1);
        }
    }

openlist의 개수가 0이 아닌, 즉 검사할 게 있는동안 반복합니다.

현재 노드는 첫번째 열린 노드이며, 열린 리스트중 추정값 + 거리인 F가 작거나 같고, 현재 H보다 작다면 현재 노드를 열린 리스트의 i번째로 설정해 초기화합니다.

열린리스트에서 닫힌리스트로 현재 노드를 옮겨주며, 현재 노드가 도착지라면 targetNode를 만들어 도착지점으로 만들고, 최종 경로를 받아오는 작업을 합니다. target노드가 출발지가 될때까지 반복해, 최종 리스트에 target노드를 넣고, target노드는 부모노드를 따라 올라갑니다.

최종적으로 시작 노드를 넣어주고, 순서가 반대로 되어있기때문에 돌려줍니다.

디버깅을 위한 출력문이 있고, 이를 완료했다면 return으로 종료!

 

만일 대각선을 허용했다면, openlist에 현재의 대각선 친구들을 넣어줍니다. 그 아래는 현재의 상하좌우 친구들을 끌고왔습니다.

    //openList에 추가 방법
    public void OpenListAdd(int checkX, int checkY)
    {
        if (checkX >= bottomleft.x && checkX < topright.x + 1 && //x가 bottom left와 top right 범위 사이
            checkY >= bottomleft.y && checkY < topright.y + 1 &&
            !nodeArray[checkX - bottomleft.x, checkY - bottomleft.y].isWall && 
            !CloseList.Contains(nodeArray[checkX - bottomleft.x, checkY - bottomleft.y])) //close list에 없다면 
        {
            if (AllowDiagonal)
            {
                if (nodeArray[CurNode.x-bottomleft.x, checkY - bottomleft.y].isWall && 
                    nodeArray[checkX - bottomleft.x, CurNode.y - bottomleft.y].isWall)
                {
                    return;
                }
            }
            if (dontCrossCorner)
            {
                if (nodeArray[CurNode.x - bottomleft.x, checkY - bottomleft.y].isWall ||
                    nodeArray[checkX - bottomleft.x, CurNode.y - bottomleft.y].isWall)
                {
                    return;
                }
            }
            Node NeighborNode = nodeArray[checkX - bottomleft.x, checkY - bottomleft.y];
            int moveCost = CurNode.G + (CurNode.x - checkX == 0 || CurNode.y - checkY == 0 ? 10 : 14); //옆이면 10, 대각선이면 14
	         if (moveCost < NeighborNode.G || !OpenList.Contains(NeighborNode))
            {
                NeighborNode.G = moveCost;
                NeighborNode.H = ((NeighborNode.x - Endnode.x) + (NeighborNode.y - Endnode.y));
                NeighborNode.ParentNode = CurNode;

                OpenList.Add(NeighborNode);
            }
        }

    }

openlist에 추가하는 함수이다.

상하좌우 범위도 안벗어나고, 벽도 아니고, 닫힌리스트에 없다면 추가가 가능하다.

if문을 통해 이를 확인해주고, 대각선을 허용했을때에는 대각선을 체크해준다, 코너를 가로지르지 않을시에는 장애물이 둘 다 있지만 않으면 되므로 or로 바꿔준다.

이웃하는 노드를 설정해주고, 이동하는 비용은 현재 G값에 옆이 하나라도 0이면 10 (갈 수 있음), 아니면 대각선으로 가기에 14로 설정한다.

이동비용이 이웃노드보다 작거나 열린 리스트에 이웃 노드가 없다면 부모노드를 설정한 후 열린 리스트에 넣는다.

 

    private void OnDrawGizmos()
    {
        if (Final_nodelist.Count != 0)
        {
            for (int i =0; i < Final_nodelist.Count-1; i++)
            {
                Gizmos.color = Color.red;
                Gizmos.DrawLine(new Vector2(Final_nodelist[i].x, Final_nodelist[i].y) , new Vector2(Final_nodelist[i + 1].x, Final_nodelist[i + 1].y));
            }
        }
    }
}

마지막으로 만들어진 길을 Scene 뷰에서 확인하기 위해 이를 작성해주고, button을 만들어 onclick시 길을 보이게 한다.

 

 

정상작동!