[Unity] 로봇 움직임 구현(1) : A* 알고리즘

요약

A*알고리즘은 길 찾기 알고리즘으로 유명하다. 이러한 A*알고리즘을 상속한 2개의 클래스를 활용하여 플레이어, 몬스터의 움직임을 구현할 것이다.

---

A*알고리즘

A*알고리즘을 구현하고 분석하기 위해 아래 문서를 통해 분석하였다.

2D 타일맵을 위한 A* 길찾기 알고리즘

완벽한 정리는 아니어서 오류는 있지만 단순하게 정리하면

 

1. 노드는 도착지와 출발지 거리, 다음 노드의 이동 비용, 둘을 합한 값 3가지 기준점을 가지고 있다
2. 닫힌 노드는 주위에 열린 노드를 배치한다.
3. 열린 노드 중 3가지 기준으로 가장 좋은 노드를 선택한다.
4. 가장 좋은 노드는 닫힌 노드가 되고 2~4를 반복한다.
5. 닫힌 노드가 목적지에 도달하지 못하면 열린 노드 전체에서 가장 좋은 노드를 선택한다.
6. 목적지에 도달한 닫힌 노드는 부모 노드를 통해 추적되어 길이 된다.

---

활용

코드에서 많은 부분을 수정할 필요는 없었다. 다만 맵의 크기나, 벽의 종류, 시작점과 목적지는 바뀌기 때문에 이를 추가한 정도다.

AStar.cs

public abstract class AStar : MonoBehaviour
{
    ... 생략 ...
    protected void PathFinding(Vector3Int start, Vector3Int target, Vector3Int mapMini, Vector3Int mapMax, List<GameManager.MapObject> wallType)
    {
    startPos = start;
    
    targetPos = target;

    bottomLeft = mapMini;

    topRight = mapMax;

    // NodeArray의 크기 정해주고, isWall, x, z 대입
    sizeX = topRight.x - bottomLeft.x;
    sizeY = topRight.y - bottomLeft.y;
    NodeArray = new Node[sizeX, sizeY];

    for (int indexI = 0; indexI < sizeX * sizeY; indexI++)
    {
        bool isWall = false;
        for (int indexJ = 0; indexJ < wallType.Count; indexJ++)
        {
            if ((int)wallType[indexJ] == GameManager.Instance.Map2D[indexI / sizeY, indexI % sizeY])
            {
                isWall = true;
                break;
            }
        }
        NodeArray[indexI / sizeY, indexI % sizeY] = new Node(isWall, (indexI / sizeY) + bottomLeft.x, (indexI % sizeY) + bottomLeft.y);
    }
    
    ... 생략 ...
}

 

A*를 몬스터와 플레이어에 적용하기 위해 MonsterMovement와 PlayerMovement 클래스로 나누었다. 추후 두 개의 클래스에 대하여 글을 작성할 것이다.