내일배움캠프 61일차 7/11 TIL + A* 알고리즘 길찾기 적용

작업 내용

A* 알고리즘 기반의 유닛 움직임 적용

A* 알고리즘을 만든 것을 기반으로 실제 유닛 움직임에 적용을 하였다.
진행하는 와중에 GridGenerator 코드가 중복된 내용이 있거나 하는 등 코드 정리가 안되어있어 클래스 내에 중복된 함수는 제거하고 정리를 좀 했다.
물론 그보다 중요한건 A* 알고리즘 적용이다.

public bool MoveToTarget(Vector2 target, float speed)
{
    if (Vector2.Distance(target, transform.position) <= speed * Time.deltaTime){
        transform.position = target;
        return false;
    }
    Vector2 direction = (target -  (Vector2)transform.position).normalized;
    transform.Translate(direction * speed * Time.deltaTime, Space.World);
    return true;
}

UserUnitAction 클래스에서 Update마다 불려서 유닛의 움직임을 구현하는 함수의 코드는 위와 같이 바뀌었다.
A* 에 path LinkedList를 기반으로 동작하니 target인 각 리스트 노드에 저장된 위치를 받아와서 해당 위치로 향하는 함수이다.
해당 위치에 도착하면 이전처럼 false를 return해서 다음 노드의 위치를 받아서 이동한다.
가장 간단한 UserUnitMoveState를 우선 설명하자면 다음과 같다.

public override void Enter()
{
    userUnit.Action.IsAlert = false;
    userUnit.Action.IsOnTheMove = true;
    userUnit.Action.IsTracking = false;
    userUnit.Action.IsHold = false;

    targetPos = userUnit.Action.TargetPosition;
    speed = userUnit.Stat.MovementSpeed.TotalValule;
    path = GridGenerator.Instance.FindPath(userUnit.transform.position, targetPos);
    pathNode = path.First;
    GridGenerator.Instance.Grid.SetGridValue(GridGenerator.Instance.Grid.World2Grid(userUnit.Action.MyPosition), true);
    if(pathNode == null)
    {
        Debug.Log("이동 할 수 없는 지역입니다");
        userUnit.StateMachine.ChangeState(userUnit.IdleState);
    }
}

public override void Exit()
{
    userUnit.Action.MyPosition = userUnit.transform.position;
    if(userUnit.Action.MyPosition != targetPos)
    {
        GridGenerator.Instance.Grid.SetGridValue(GridGenerator.Instance.Grid.World2Grid(targetPos), true);
    }
}

public override void Update()
{
    if (!userUnit.Action.MoveToTarget(pathNode.Value, speed))
    {
        if ( pathNode.Next != null)
        {
            pathNode = pathNode.Next;
        }
        else
        {
            userUnit.StateMachine.ChangeState(userUnit.IdleState);
        }
    }
}

시작시 Path를 찾고, 유닛의 현재 지점에 그리드 값을 true로 바꾸어 이동 가능 지역으로 설정한다.
이동 가능 지역은 아무것도 없는 곳을 뜻한다.
만약 Path를 찾지 못하면 Debug로 알리고 state를 Idle로 바꾼다.
Exit으로 State가 바뀔 때는 목적지에 도달 못했을 경우 그 자리를 이동 가능 지역으로 설정해준다.
그리고 Update에서 위에 설명했던 함수를 불러서 pathNode를 돌면서 이동을 한다.
이동이 끝나서 pathNode.Next가 더이상 없을 경우 State를 Idle로 바꾼다.
그리고 목적지를 true로 설정하는 이유는, 유닛끼리의 겹치는 현상을 막기 위해 이동 시작시 해당 목적지를 false로 선점 해두기 때문이다.

    public LinkedList<Vector2> FindPath(Vector2 startPos, Vector2 endPos)
    {
        //시작 지점과 도착 지점을 그리드 좌표로 바꿈
        Vector2Int gridStartPos = Grid.World2Grid(startPos);
        Vector2Int gridEndPos = Grid.World2Grid(endPos);

        // 도착 지점이 이동 불가 지역이면 가까운 다른 지역을 찾고, 해당 지역을 이동 불가 지역으로 선점함
        gridEndPos = FindNearestValidGridPosition(gridEndPos);
        grid.SetGridValue(gridEndPos, false);

        // A* 알고리즘으로 길 찾기
        LinkedList<Vector2Int> gridPath = AStarPathFinding(gridStartPos, gridEndPos);

        // 찾은 길을 World좌표로 변환
        LinkedList<Vector2> worldPath = new LinkedList<Vector2>();
        foreach(Vector2Int path in gridPath)
        {
            worldPath.AddLast(Grid.Grid2World(path));
        }

        return worldPath;
    }

GridGenerator 클래스에서 A* 알고리즘을 실행하기 전 시작지점과 목적지점을 설정하는 함수이다.
둘을 grid 좌표로 바꾸고 혹시라도 목적지가 이동 불가 지역이면 주변에 이동 가능한 다른 지역을 BFS 방식으로 찾는다.
그러고 나서 최종 목적지를 SetGridValue로 선점한다.
이렇게하면 단체 이동이나 한명이 이동 중에 다른 한명이 끼어들어도 서로 겹치는 일은 없는데, 문제는 이렇게 미리 선점해두니 나중에 해제할 때 에러가 발생해서 이를 찾는 중이다.
특히나 적을 자동 추적할 때 매번 적이 이동하여 공격 범위를 벗어나면 새로 path를 찾아줄 때 이런 식으로 update에서 처리하거나, State가 중도에 막 바뀌거나, 이동 중에 유저 마음대로 이동 지점을 바꾸거나, H로 홀드 하는 등 다양한 이유로 목적지에 도달 못하거나 목적지가 바뀌는 경우가 생긴다.
그러다보니 이러한 선점 기능을 잘 풀어주지 못해서 점점 아무도 없는데 이동 불가 지역이 늘어나게 되었다.

public override void Update()
{
    // 적이 죽거나 없으면 Idle로 상태 전환
    // 적을 추적 중이면 사거리 밖으로 나간 적 매번 적의 위치 갱신
    if (userUnit.Action.TargetEnemy == null || userUnit.Action.TargetEnemy.Dead)
    {
        userUnit.StateMachine.ChangeState(userUnit.IdleState);
    }
    else if(Vector2.Distance(userUnit.Action.TargetEnemy.transform.position, userUnit.transform.position) > userUnit.Stat.AttackRange.TotalValule)
    {
        if (!isMoving)
        {
            // 적 위치에서 공격 사정거리 만큼 떨어진 위치로 다음 목적지 갱신
            Vector2 directionToEnemy = (userUnit.Action.TargetEnemy.transform.position - userUnit.transform.position).normalized;
            targetPosition = ((Vector2)userUnit.Action.TargetEnemy.transform.position) - directionToEnemy * (userUnit.Stat.AttackRange.TotalValule - 0.1f);

            path = GridGenerator.Instance.FindPath(userUnit.transform.position, targetPosition);
            pathNode = path.First;
            userUnit.Action.TargetPosition = targetPosition;
            GridGenerator.Instance.Grid.SetGridValue(GridGenerator.Instance.Grid.World2Grid(userUnit.Action.MyPosition), true);
            if (pathNode == null)
            {
                Debug.Log("이동 할 수 없는 지역입니다");
                userUnit.StateMachine.ChangeState(userUnit.IdleState);
            }
            isMoving = true;
        }

        if (!userUnit.Action.MoveToTarget(pathNode.Value, speed))
        {
            if (pathNode.Next != null)
            {
                pathNode = pathNode.Next;
            }
            else
            {
                if (userUnit.Action.MyPosition != targetPosition)
                {
                    GridGenerator.Instance.Grid.SetGridValue(GridGenerator.Instance.Grid.World2Grid(targetPosition), true);
                }
                isMoving = false;
            }
        }
    }
    else
    {
        if (userUnit.Action.MyPosition != targetPosition)
        {
            GridGenerator.Instance.Grid.SetGridValue(GridGenerator.Instance.Grid.World2Grid(targetPosition), true);
        }
        isMoving = false;
    }
}

적 자동 추적 클래스인 UserUnitTrackingState 클래스의 Update문이다.

마무리

오늘 직접 적용을 해보고 나니 이것저것 신경 쓸게 많았다.
특히나 위치가 이동 불가인지 이동 가능인지와 유저가 자유롭게 컨트롤할 때 발생하는 예외사항들을 처리하려니 머리가 아주 아팠다.
그래서 내린 결론은 스타처럼 이동 할 때 마다 그 자리를 선점하고, 이동할 때 노드를 보고 다음 위치를 확인할 때 이동 가능한지 확인을 한 다음, 불가능하면 1초 정도 기다렸다가 다시 확인하고 그래도 불가능하면 새로 path를 찾게 해볼 생각이다.
이번에는 계획대로 잘 되길 바란다.