A* 알고리즘을 사용한 길찾기 구현

오늘의 구현

A* 알고리즘을 사용한 길 찾기 구현

 

A* 알고리즘이란 최단 경로 탐색 알고리즘으로 시작점과 도착점 사이의 최단 경로를 찾는 데 사용됩니다.

BFS 알고리즘을 알고 있다면 이해하기가 더 쉬울꺼라 생각합니다.

 

두 알고리즘의 차이점이라면 BFS 는 너비우선 탐색이고 A* 알고리즘은 각 노드의 비용을 계산해 최단 경로를 찾습니다. 경로 찾는데 효과적이지만 탐색 속도가 느릴 수 있습니다.

 

A* 알고리즘의 코스트 계산은 F = G+H 로 

F는 예상비용 , G는 경로 비용,

H는 경로 평가 함수로, 일반적으로 노드 사이의 거리, 장애물 유무 등을 고려해 계산함으로, 이 경로 평가 함수 설정에 따라 알고리즘의 성능이 결정됩니다. 여기서는 단순하게 출발 지점과 도착지점 사이의 직선거리로 계산할 것입니다.(맨헤튼 휴리스틱)

 

1. 탐색 방향을 먼저 정해봅니다.

탐색방향은 상하좌우 4방향 또는 대각선을 포함한 8 방향을 선택합니다. 저는 8 방향으로 구현했으며 밑변 높이 1인 직각삼각형의 빗변은  루트 2의 길이를 가지므로 대각선을 이동할 땐 코스트를 더 주도록 합니다.

        int[] moveX = new int[] {-1, 0 , 1 , 0 , 1 ,  1 , -1 , -1 };
        int[] moveY = new int[] { 0,-1 , 0 , 1 , 1 , -1 , -1 ,  1 };
        int[] cost = new int[] { 10, 10, 10, 10, 14, 14 , 14 , 14 };

 

2.while문

bfs랑 비슷하게 시작합니다.

큐에서 경로를 꺼내올 것이고, 꺼내면 방문처리를 해줍니다. (닫힌목록에 넣는다라고도 합니다)

큐에서 꺼낸 요소의 위치값이 도착지점과 같다면 반복을 멈춥니다.

        while(qDot.Count > 0)
        {
            Dot node = qDot.Dequeue();
            close[node.x, node.y] = true;
            
            if (node.x == endX && node.y == endY)
            {
                break;
            }

         }

 

3. 구현

열린 목록을 만들어 줍니다. 

포문으로 8방향을 확인하면서, 보드판의 범위를 넘지 않고 방문하지 않은 dot만 열린 목록에 넣어줄 것입니다.

 

IsValidPosition() 함수로 보드판의 유효범위를 확인해 줍니다.

• 대각선으로 이동할때 장애물을 대각선으로 지나쳐 지나가지 않게 로직을 추가해 줬습니다.

               List<Dot> openList = new List<Dot>();
            
                for (int i = 0; i< moveX.Length; i++)
                {
                    int nextX = node.x + moveX[i];
                    int nextY = node.y + moveY[i];

                    if( IsValidPosition(nextX,nextY) && !close[nextX,nextY])
                    {
                      

                    }

                }

 

4. 예상 코스트 구하기, parent 설정

현재노드에 이동코스트를 더해줍니다.

맨헤튼 휴리스틱으로 h 값을 구해줍니다.

이동했을때 f 값이 현재 노드의 f값 보다 크다면 현재 노드가  도착지점으로부터 더 가깝기때문에 이동했을때의 dot을 열린 목록에 넣을 필요가 없습니다.

해당 dot의 g,h값이 제대로 반영됬는지 확인하기위해 dot의 g,h를 설정해줬습니다.

위 알고리즘에서 가장 중요하다고 생각하는 부분으로 Parent를 설정하는 것 입니다.

현재 위치에서 이동할수 있는 8방향을 탐색하면서 이동했을때 어느 방향에서 왔는지를 설정해 주는 것 입니다. 최종적으로 도착지점에 도착했을때 도착지점으로 부터 역순으로 parent를 탐색하면서 최단경로를 뽑아낼 것입니다.

 int g = node.g + cost[i];
 int h = 10 * (Mathf.Abs(nextX - endX) + Mathf.Abs(nextY - endY));

 if (open[nextX,nextY] > g + h)
 {
  open[nextX, nextY] = g + h;
  dotArray[nextX, nextY].GetComponent<Dot>().SetMoveCost(g, h);
  dotArray[nextX, nextY].GetComponent<Dot>().SetParent(node.x, node.y);
  openList.Add(dotArray[nextX, nextY].GetComponent<Dot>());
 }

포문으로 8방향을 다 탐색했으면 오픈목록에서 f 값이 가장 작은 노드부터 큐에 넣어 위 과정을 반복해줍니다.

            var list = openList.OrderBy(x => x.GetComponent<Dot>().f).ToArray();

            foreach(var item in list)
            {            
                qDot.Enqueue(item);
            }

ReverseParent(dotArray[endX, endY].GetComponent<Dot>());

while문이 끝나면 도착지점으로 부터 역순으로 parent를 탐색해 parent라는 리스트에 넣어 줍니다.

제대로 최단경로를 찾았는지 확인을 해봅니다.

    void ReverseParent(Dot endDot)
    {
        Dot current = endDot;

        while(true)
        {
            if(current.x == startX && current.y == startY)
            {
                break;
            }

            parent.Add(current);
            current = dotArray[current.parentX, current.parentY].GetComponent<Dot>();
        }

        parent.Reverse();

        foreach (Dot dot in parent)
        {
            Debug.Log("Path: " + dot.x + ", " + dot.y);
        }
     }

 

parent의 dot을 하나씩 꺼내 시작지점의 Dot을 최단경로로 이동시켜봅니다.

  IEnumerator GoCo()
    {
        foreach(Dot dot in parent)
        {
            dotArray[startX, startY].GetComponent<Dot>().transform.position = new Vector3(dot.x, dot.y);
            yield return new WaitForSeconds(.1f);
        }
    }