AStar Algorithm (에이스타 알고리즘)

길 찾기에서 흔히 사용되는 AStar 알고리즘 입니다.

 

간단히 요약해보자면

 

용어 설명

openList = 갈 수 있는 길

closeList = 이미 지나간 길

current = 현재 위치

NeighborNode = 탐색한 길

이동비용 = 도착지점까지의 거리라고 생각하면 된다.

가중치 = 일반적으로 직선 : 10, 대각선 : 14

 

1. CreateNode : 맵을 만든다.

2. SetTargetLocation : 시작지점과 도착지점을 구한다.

3. PathFinding : 길 찾기 알고리즘을 한다.

- 시작지점을 openList에 담는다.

- openList 중에 이동 비용이 낮은 길을 찾아 current에 담는다.

- current를 openList에서 지우고 closeList에 담는다.

- current를 기준으로 4개 방향에 대해 탐색한다.

(일반적으로는 8개 방향인데 현재 코드는 사선으로 움직이지 못하는 코드라서 4개의 방향만 탐색한다.)

(4개의 방향 중 막다른길, openList, closeList에 포함하는 경우 탐색하지 않는다.)

- 이동 비용을 계산한다.

(이동 비용 : current의 G + 가중치)

- current의 이동비용이 NeighborNode의 이동 비용보다 작으면 NeighborNode의 이전 길은 current로 설정해준다.

- NeighborNode는 openList에 담는다.

4. 위와 같은 방법을 반복하여 목표지점을 찾는다.

 

요약이 어려우셨다면 주석으로 설명을 해놓았으니 아래 코드블록을 보시면 됩니다.

public class AStarNode
{
    public bool isWall;
    public AStarNode ParentNode;

    // G : 시작노드부터 이동하려는 위치 거리
    // H : 시작노드부터 목표지점까지 거리(타일 칸 수)
    // F : G + H
    public int x, y, G, H;

    public int F
    {
        get
        {
            return G + H;
        }
    }

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

using System.Collections.Generic;
using UnityEngine;

public class AStarLogic : MonoBehaviour
{
    private AStarNode[,] nodes;
    private AStarNode startNode;
    private AStarNode endNode;
    private AStarNode currentNode;
    private List<AStarNode> openList = new List<AStarNode>();
    private List<AStarNode> closeList = new List<AStarNode>();

    public Vector2Int TestStartLocation;    // 시작 위치
    public Vector2Int TestEndLocation;      // 도착 위치
    public int TestXSize;       // 맵 X크기
    public int TestYSize;       // 맵 Y크기

    [ContextMenu("테스트")]
    public void Test()
    {
        CreateNode(TestXSize, TestYSize);
        SetTargetLocation(TestStartLocation, TestEndLocation);
        PathFinding();
    }

    /// <summary>
    /// x,y 크기에 맞는 노드 배열을 만든다.
    /// </summary>
    public void CreateNode(int xSize, int ySize)
    {
        nodes = new AStarNode[xSize, ySize];

        for (int x = 0; x < xSize; x++)
        {
            for (int y = 0; y < ySize; y++)
            {
                bool isWall = false; // 벽 여부 (막힌 길)
                nodes[x, y] = new AStarNode(isWall, x, y);
            }
        }
    }

    /// <summary>
    /// 시작 지점과 목표 지점
    /// </summary>
    public void SetTargetLocation(Vector2Int startLocation, Vector2Int endLocation)
    {
        startNode = nodes[startLocation.x, startLocation.y];
        endNode = nodes[endLocation.x, endLocation.y];
    }

    /// <summary>
    /// 길 찾기 알고리즘
    /// </summary>
    public void PathFinding()
    {
        openList.Clear();   // 갈 수 있는 길 목록
        closeList.Clear();  // 한번 들른 곳 목록

        // 맨 처음에는 시작 지점부터
        openList.Add(startNode);

        while (openList.Count > 0)
        {
            // 갈 수 있는 길 중에 가중치가 낮은 길을 찾는다.
            currentNode = openList[0];
            for (int i = 1; i < openList.Count; ++i)
            {
                if (openList[i].F <= currentNode.F &&
                    openList[i].H < currentNode.H)
                {
                    currentNode = openList[i];
                }
            }

            // 찾은 길은 갈 수 있는 곳 목록에서 지운다.
            // 한번 들른 곳 목록에 넣어준다.
            // 이로써 한번 갔던 길을 중복으로 검색하는 일은 없어진다.
            openList.Remove(currentNode);
            closeList.Add(currentNode);

            // 목적지에 도착했는지 체크한다.
            if (currentNode == endNode)
            {
                //for (int i = 0; i < closeList.Count; i++)
                //    Debug.Log(i + "번째는 " + closeList[i].x + ", " + closeList[i].y);
                return;
            }

            // 갈 수 있는 길을 찾아서 목록에 넣어준다.
            // 순서는 일반적으로 위 -> 오른쪽 -> 아래 -> 왼쪽 순이다.
            OpenListAdd(currentNode.x, currentNode.y + 1);
            OpenListAdd(currentNode.x + 1, currentNode.y);
            OpenListAdd(currentNode.x, currentNode.y - 1);
            OpenListAdd(currentNode.x - 1, currentNode.y);
        }
    }

    void OpenListAdd(int checkX, int checkY)
    {
        // 상하좌우 범위를 벗어났다면 빠져나온다.
        if (checkX < 0 || checkX >= nodes.GetLength(0) || checkY < 0 || checkY >= nodes.GetLength(1))
            return;

        // 한번 들른 곳이면 빠져나온다.
        if (closeList.Contains(nodes[checkX, checkY]))
            return;

        // 벽인 경우 빠져나온다.
        if (nodes[checkX, checkY].isWall)
            return;

        // 이동 비용을 구한다.
        // 직선 : 현재 위치의 G + 10 (현재 위치 - 확인할 위치를 계산하여 x,y중 하나라도 0인 경우)
        // 대각선 : 현재 위치의 G + 14 (현재 위치 - 확인할 위치를 계산하여 x,y 둘 다 0이 아닌 경우)
        // 직선의 비용은 10
        // 대각선의 비용은 14
        AStarNode NeighborNode = nodes[checkX, checkY];
        int MoveCost = currentNode.G + (currentNode.x - checkX == 0 || currentNode.y - checkY == 0 ? 10 : 14);

        // 이동 비용이 확인할 위치의 G보다 작거나
        // 갈 수 있는 길 목록에서 현재 확인하려는 위치가 없다면
        if (MoveCost < NeighborNode.G || !openList.Contains(NeighborNode))
        {
            // 이동비용, 거리, 현재 위치를 담는다.
            NeighborNode.G = MoveCost;
            NeighborNode.H = (Mathf.Abs(NeighborNode.x - endNode.x) + Mathf.Abs(NeighborNode.y - endNode.y)) * 10;
            NeighborNode.ParentNode = currentNode;

            // 위와 같은 방법을 통해 parentNode가 시작점과 이어지게 된다.
            // 예)
            // 시작점 : x:0,y:0
            // 도착점 : x:2,y:0
            // 도착점(2,0) -> 이전(1,0) -> 시작점(0,0)으로 연결 되어 있다.

            openList.Add(NeighborNode);
        }
    }
}

 

 

 

다람쥐와 포동포동이

 

 

RememberCook 9월 28일 정식 출시!