Grid 기반 경로 탐색 및 선택 유틸리티

Grid 기반 건축 시스템에서는 단일 셀에 오브젝트를 배치하는 기능뿐 아니라 여러 셀을 연결하여 구조물을 배치하는 기능도 필요하다.

대표적인 예로 벽, 울타리, 도로와 같은 구조물은 시작 위치와 끝 위치를 지정하면 그 사이의 Grid 셀을 따라 연속적으로 배치되어야 한다.

이러한 기능을 구현하기 위해서는 단순히 두 좌표 사이의 범위를 계산하는 것만으로는 충분하지 않다.

‍

건축 시스템에서 사용하는 좌표 체계는 월드 좌표가 아니라 Grid 좌표이다.

건축 프리뷰, 배치 판정, 실제 설치 로직은 모두 정수 기반 셀 좌표를 기준으로 동작한다.

따라서 경로 계산 역시 동일한 좌표 체계 위에서 수행되어야 하며, Grid 좌표를 기반으로 셀 간 이동 경로를 계산할 수 있어야 한다.

‍

또한 경로 탐색 과정에서는 이론적으로 존재하는 모든 Grid 좌표를 사용할 수 있는 것이 아니라 실제로 배치 가능한 셀만을 대상으로 탐색해야 한다.

Grid 상에는 이미 구조물이 존재하거나, 배치가 불가능한 셀이 존재할 수 있기 때문이다.

따라서 경로 계산은 단순한 격자 탐색이 아니라 현재 건축 데이터 상태를 반영한 탐색이어야 한다.

이를 위해 GridSelectionHelper는 PlacementGridData와 연결되어 실제 데이터에 존재하는 셀만을 대상으로 경로 탐색을 수행하도록 설계하였다.

‍

경로 계산 결과 역시 단순히 셀 좌표 목록만 반환하는 것으로 끝나지 않는다.

건축 시스템에서는 벽, 울타리, 펜스처럼 방향성이 있는 구조물이 많기 때문에 각 셀이 어떤 방향을 향해야 하는지에 대한 정보도 함께 계산되어야 한다.

따라서, 이 시스템은 시작 셀과 목표 셀이 주어졌을 때, 현재 Grid 상태를 고려하여 이동 가능한 셀만 따라 경로를 계산하고, 필요할 경우 해당 경로를 기반으로 구조물의 방향 정보까지 생성하는 계산 유틸리티 계층이어야 한다.

- Grid 기반 경로 탐색 기능 제공

- PlacementGridData 기반 유효 셀 탐색 구조 구성

- Grid 환경에 맞는 단순화된 A* 알고리즘 적용

- 경로 방향 기반 회전값 계산 기능 제공

- 건축 시스템에서 재사용 가능한 정적 Helper 구조 설계

[시작 Grid 좌표 / 목표 Grid 좌표 입력]

           ↓

    [목표 셀 유효성 검사]

           ↓

      [Open List 초기화]

           ↓

     [비용 기준 노드 선택]

           ↓

       [이웃 셀 탐색]

           ↓

[PlacementGridData에 존재하는 셀만 후보 추가]

           ↓

     [부모 노드 정보 저장]

           ↓

    [목표 도달 시 역추적]

           ↓

        [경로 완성]

           ↓

   [경로 기반 회전값 계산]

‍

이 시스템의 흐름은 시작 좌표에서 목표 좌표까지 직접 이동하는 단순한 직선 계산이 아니라, 현재 Grid 상태를 고려하여 실제로 사용 가능한 셀만 따라가며 경로를 계산하는 구조로 이루어진다.

‍

먼저 시작 Grid 좌표와 목표 Grid 좌표가 입력되면, 탐색을 시작하기 전에 목표 셀이 실제 Grid 데이터에 존재하는지 검사한다.

목표 셀이 유효하지 않은 경우에는 경로 탐색을 수행할 필요가 없기 때문에 탐색을 시작하지 않고 바로 빈 결과를 반환한다.

‍

이후 탐색 후보 노드를 관리하는 Open List를 초기화하고, 비용이 가장 낮은 노드를 기준으로 탐색을 진행한다.

각 노드에서는 주변 이웃 셀을 확인하고, 실제 Grid 데이터에 존재하는 셀만 다음 탐색 후보로 추가한다.

이 과정에서 부모 노드 정보를 함께 저장하여 이후 경로 복원이 가능하도록 한다.

‍

탐색 과정에서 목표 셀에 도달하면 부모 노드를 따라 역추적을 수행하여 최종 경로를 완성한다.

완성된 경로는 필요에 따라 방향 벡터로 변환되고, 이를 기반으로 오브젝트의 회전값을 계산할 수 있다.

4.1. Grid 범위 순회 유틸리티

public static IEnumerable<int> MoveMinToMaxInclusive(int minVal, int maxVal, int step)
{
    for (int i = minVal; i <= maxVal; i += step)
    {
        yield return i;
    }
}

public static IEnumerable<int> MoveMaxToMinInclusive(int minVal, int maxVal, int step)
{
    for (int i = maxVal; i >= minVal; i -= step)
    {
        yield return i;
    }
}

이 두 함수는 Grid 범위를 순서대로 순회하기 위한 보조 함수다.

하나는 작은 값에서 큰 값으로 이동하고, 다른 하나는 큰 값에서 작은 값으로 이동한다.

이름에 Inclusive가 들어간 이유는 시작값과 끝값을 모두 포함해서 순회하기 때문이다.

‍

여기서 중요한 C# 기능은 IEnumerable<int>와 yield return이다.

IEnumerable<T>는 컬렉션 전체를 한 번에 만들어 반환하는 것이 아니라, 필요할 때마다 값을 하나씩 꺼내 쓸 수 있게 해주는 열거 가능한 시퀀스 타입이다.

yield return은 이 시퀀스를 만드는 문법으로, 반복문 안에서 값을 하나씩 반환하면서도 함수 상태를 유지할 수 있게 해준다.

‍

이 방식을 사용한 이유는 단순하다.

만약 List<int>를 만들어 반환하면, 먼저 리스트를 전부 채운 뒤 반환해야 한다.

하지만 yield return은 값을 즉시 하나씩 내보낼 수 있기 때문에, 범위 순회 같은 단순 반복에는 더 가볍고 의도가 분명하다.

즉, 이 함수들은 숫자 범위를 전부 저장하는 함수가 아니라, 필요한 순서대로 숫자를 흘려보내는 함수로 설계된 것이다.

‍

또한 '최소값 → 최대값', '최대값 → 최소값' 두 방향을 각각 분리한 이유는 Grid 선택 시 드래그 방향에 따라 순회 순서가 달라질 수 있기 때문이다.

예를 들어, 왼쪽에서 오른쪽으로 선택할 수도 있고, 반대로 오른쪽에서 왼쪽으로 선택할 수도 있다.

이런 경우 단순한 한 방향 함수만으로는 호출부에서 조건 분기를 추가로 해야 한다.

현재 구조는 그 분기를 Helper 안에 흡수하여, 호출하는 쪽이 더 단순하게 사용하도록 한 설계다.

‍

‍

4.2. A* 기반 Grid 경로 탐색

public static List<Vector3Int> AStar(Vector3Int startPos, Vector3Int endPos, PlacementGridData placementData)
{
    List<Vector3Int> path = new();
    List<Vector3Int> openList = new();
    Dictionary<Vector3Int, Vector3Int> childParentDictionary = new();
    Dictionary<Vector3Int,int> costDictionary = new();

    openList.Add(startPos);
    costDictionary[startPos] = ManhattanDistance(startPos, endPos);

    Vector3Int currentPosition = startPos;

    if(placementData.IsCellAt(endPos) == false)
        return new List<Vector3Int>();

    while(openList.Count > 0)
    {
        openList = openList.OrderBy(x => costDictionary[x]).ToList();
        currentPosition = openList[0];
        openList.RemoveAt(0);

        if (currentPosition == endPos)
        {
            while (currentPosition != startPos)
            {
                path.Add(currentPosition);
                currentPosition = childParentDictionary[currentPosition];
            }
            path.Add(startPos);
            path.Reverse();
            break;
        }

        List<Vector3Int> neighbours = FindNeighbours(currentPosition, placementData);
        foreach (var neighbourposition in neighbours)
        {
            if (costDictionary.ContainsKey(neighbourposition))
                continue;
            childParentDictionary[neighbourposition] = currentPosition;
            costDictionary[neighbourposition] = ManhattanDistance(neighbourposition, endPos);
            if (openList.Contains(neighbourposition) == false)
                openList.Add(neighbourposition);
        }
    }
    return path;
}

AStar 함수는 GridSelectionHelper의 핵심이다.

이름 그대로 A* 알고리즘을 사용해 시작 Grid 좌표에서 목표 Grid 좌표까지의 경로를 계산한다.

기본 구조는 A* 알고리즘을 기반으로 하지만, 일반적인 A* 알고리즘의 g + h 비용 구조를 완전히 구현한 형태는 아니다.

현재 프로젝트에서는 모든 이동 비용이 동일한 Grid 환경이라는 점을 고려하여 목표 지점까지의 Manhattan Distance만을 기준으로 탐색 우선순위를 결정하는 단순화된 방식을 사용하였다.

‍

먼저 path, openList, childParentDictionary, costDictionary 네 개의 자료구조를 만든다.

path는 최종 경로를 저장하는 리스트이고, openList는 앞으로 탐색할 후보 노드를 저장하는 리스트다.

childParentDictionary는 특정 셀에 도달했을 때, 그 셀로 오기 직전의 부모 셀을 저장하는 딕셔너리다.

이 정보가 있어야 나중에 목표 지점에서 시작점까지 경로를 역추적할 수 있다.

costDictionary는 각 셀의 비용 값을 저장한다.

이 구조에서 사용된 Dictionary<TKey, TValue>는 C#에서 키-값 형태로 데이터를 빠르게 조회할 수 있는 자료구조다.

여기서는 Grid 좌표(Vector3Int)를 키로 사용해, 해당 좌표의 부모 노드나 비용을 저장한다.

A*처럼 이 좌표를 이미 방문했는가, 이 좌표의 비용은 얼마인가 를 자주 검사해야 하는 알고리즘에서는 딕셔너리가 매우 유용하다.

초기화 단계에서 startPos를 openList에 추가하고, 시작점의 비용을 ManhattanDistance(startPos, endPos)로 설정한다.

‍

그 다음 중요한 부분이 placementData.IsCellAt(endPos) 검사다.

if(placementData.IsCellAt(endPos) == false)
    return new List<Vector3Int>();

이 코드는 목표 셀이 실제로 배치 가능한 Grid 데이터 안에 존재하는지를 먼저 확인한다.

목표 지점 자체가 유효하지 않다면 경로를 찾는 것은 의미가 없기 때문에, 아예 빈 리스트를 반환하고 탐색을 시작하지 않는다.

이런 조기 반환은 불필요한 탐색 연산을 줄이는 데 유리하고, 잘못된 입력에 대한 방어 코드 역할도 한다.

이후 while (openList.Count > 0) 루프에서 본격적인 탐색이 시작된다.

현재 구현에서는 openList를 비용 기준으로 정렬한 뒤 가장 앞의 노드를 꺼내는 방식으로 다음 탐색 대상을 결정한다.

‍

openList = openList.OrderBy(x => costDictionary[x]).ToList();
currentPosition = openList[0];
openList.RemoveAt(0);

경로 탐색 과정에서는 Open List를 사용하여 탐색 후보 노드를 관리하고, 각 셀의 부모 노드 정보를 Dictionary 구조에 저장하여 이후 경로 복원이 가능하도록 한다.

또한 특정 셀이 이미 탐색된 적이 있는지 빠르게 확인하기 위해 비용 정보를 저장하는 Dictionary를 방문 여부 검사 용도로도 함께 사용하였다.

탐색 루프에서는 비용이 가장 낮은 노드를 기준으로 다음 탐색을 진행한다.

이 구현에서는 LINQ의 OrderBy를 사용하여 Open List를 비용 기준으로 정렬한 뒤 가장 앞의 노드를 선택하는 방식으로 구현하였다.

일반적인 경로 탐색 시스템에서는 Priority Queue를 사용하는 것이 시간 복잡도 측면에서 더 효율적이다.

그러나 본 시스템은 건축 Grid 범위가 제한적이고 경로 길이도 비교적 짧기 때문에 구현 단순성과 코드 가독성을 우선하여 LINQ 기반 정렬 방식을 선택하였다.

‍

여기서 사용된 OrderBy는 LINQ 기능이다.

C#의 LINQ(Language Integrated Query)는 컬렉션을 정렬, 필터링, 변환할 수 있게 해주는 문법 집합이다.

OrderBy(x => costDictionary[x])는 openList 안의 각 좌표를 costDictionary 값 기준으로 오름차순 정렬한다는 의미다.

‍

장점은 코드가 매우 직관적이라는 점이다.

비용이 가장 작은 노드를 먼저 꺼낸다는 알고리즘 의도를 그대로 코드로 보여준다.

단점은 매 반복마다 리스트 전체를 다시 정렬한다는 점이다.

노드 수가 많아지면 성능 비용이 커질 수 있다.

실무적으로는 우선순위 큐(Priority Queue)를 쓰는 것이 더 효율적이지만, 현재 프로젝트 규모에서는 구현 단순성과 가독성을 우선한 선택으로 볼 수 있다.

현재 위치가 목표 지점에 도달하면 경로를 역추적한다.

‍

while (currentPosition != startPos)
{
    path.Add(currentPosition);
    currentPosition = childParentDictionary[currentPosition];
}
path.Add(startPos);
path.Reverse();

이 부분은 A* 구현에서 매우 중요한 구간이다.

탐색 도중 저장해 둔 childParentDictionary를 사용해 현재 위치에서 부모 노드를 따라 시작점까지 거꾸로 이동한다.

이렇게 하면 경로는 '끝점 → 시작점' 순서로 쌓이기 때문에, 마지막에 path.Reverse()를 호출해 '시작점→끝점' 순서로 뒤집는다.

List<T>.Reverse()는 리스트의 순서를 뒤집는 C# 기본 메서드다.

경로 탐색에서는 역추적이 자연스럽게 끝점부터 시작되기 때문에, 이런 뒤집기 과정이 자주 사용된다.

목표에 도달하지 않았다면, 현재 위치의 이웃 셀을 찾아 계속 탐색한다.

‍

List<Vector3Int> neighbours = FindNeighbours(currentPosition, placementData);
foreach (var neighbourposition in neighbours)
{
    if (costDictionary.ContainsKey(neighbourposition))
        continue;
    childParentDictionary[neighbourposition] = currentPosition;
    costDictionary[neighbourposition] = ManhattanDistance(neighbourposition, endPos);
    if (openList.Contains(neighbourposition) == false)
        openList.Add(neighbourposition);
}

여기서는 먼저 FindNeighbours를 통해 현재 위치 주변의 유효한 셀을 가져온다.

그리고 이미 costDictionary에 등록된 셀은 건너뛴다.

이 코드는 사실상 이미 방문 처리된 셀은 다시 확장하지 않는다는 의미다.

방문 여부를 별도의 closedSet으로 관리하지 않고, costDictionary.ContainsKey를 방문 여부 판정으로 재사용하고 있다는 점도 현재 구현의 특징이다.

부모 노드는 현재 셀로 저장하고, 비용은 목표 지점까지의 Manhattan Distance로 계산한다.

아직 openList에 없는 셀만 추가함으로써 다음 탐색 후보로 넘긴다.

즉, 이 함수는 유효한 Grid 셀만 따라가면서, 비용이 낮은 방향부터 탐색하고, 목표 지점에 도달하면 부모 정보로 경로를 복원하는 구조라고 정리할 수 있다.

‍

‍

4.3. 이웃 셀 탐색

private static List<Vector3Int> FindNeighbours(Vector3Int currentPosition, PlacementGridData placementData)
{
    List<Vector3Int> neighbours = new();
    foreach (var direction in Directions)
    {
        Vector3Int tempPos = currentPosition + direction;
        if (placementData.IsCellAt(tempPos))
        {
            neighbours.Add(tempPos);
        }
    }
    return neighbours;
}

이 함수는 현재 Grid 좌표를 기준으로 이동 가능한 이웃 셀을 찾는다.

핵심은 단순히 사방 셀을 무조건 반환하는 것이 아니라, placementData.IsCellAt(tempPos)를 통해 실제로 Grid 데이터에 존재하는 셀만 반환한다는 점이다.

‍

여기서 foreach는 컬렉션을 순회하는 C# 반복문이다.

Directions 리스트에 정의된 방향값을 하나씩 가져오고, 현재 위치에 더해 새로운 후보 좌표를 만든다.

Vector3Int는 Unity에서 정수 기반 3차원 좌표를 표현하는 구조체인데, Grid 좌표처럼 소수점이 필요 없는 위치 표현에 적합하다.

장점은 구조가 매우 단순하고 읽기 쉽다는 점이다.

방향 목록만 바꾸면 대각선 이동 허용 같은 규칙 변경도 비교적 쉽게 할 수 있다.

단점은 현재 구현이 상하좌우 4방향만 지원하기 때문에, 8방향 이동이 필요한 시스템에는 그대로 사용할 수 없다는 점이다.

하지만 이 프로젝트는 Grid 기반 건축 시스템이고, 대부분 직교 방향 이동이 전제되기 때문에 현재 구조가 더 적절하다.

‍

‍

4.4 Manhattan Distance 계산

private static int ManhattanDistance(Vector3Int startPoint, Vector3Int endPoint)
{ 
    return Mathf.Abs(startPoint.x - endPoint.x) + Mathf.Abs(startPoint.z - endPoint.z);
}

이 함수는 두 Grid 좌표 사이의 Manhattan Distance를 계산한다.

Manhattan Distance는 격자 기반 이동에서 흔히 사용하는 거리 계산 방식으로, 가로 거리 차이와 세로 거리 차이를 더해 계산한다.

여기서는 Mathf.Abs를 사용해 각 축 차이의 절댓값을 구한다.

Mathf.Abs는 Unity 수학 유틸리티 함수로, 값의 부호를 제거하고 절댓값을 반환한다.

‍

왜 유클리드 거리(직선거리)가 아니라 Manhattan Distance를 썼는지가 중요하다.

이 시스템은 대각선 이동이 아니라 상하좌우 방향만 이동하기 때문에, 직선거리보다 Manhattan Distance가 실제 이동 비용과 더 잘 맞는다.

예를 들어 (0,0)에서 (3,2)까지 갈 때, 이 시스템에서는 오른쪽 3번과 위쪽 2번 이동이 필요하므로 총 이동량은 5다.

Manhattan Distance는 바로 이 값을 계산한다.

즉, 이 함수는 단순한 거리 계산이 아니라, Grid 기반 4방향 이동 규칙에 맞는 휴리스틱 함수 역할을 수행한다.

‍

‍

4.5. 경로 방향 기반 회전값 계산

internal static List<Quaternion> CalculateRotation(List<Vector3Int> gridPositions)
{
    List<Quaternion> returnValues = new();
    for (int i = 0; i < gridPositions.Count-1; i++)
    {
        Vector3Int direction = gridPositions[i+1] - gridPositions[i];
        returnValues.Add(Quaternion.Euler(0,Mathf.RoundToInt(Vector3.SignedAngle(Vector3.right, direction,Vector3.up)),0));
    }
    return returnValues;
}

이 함수는 계산된 경로를 따라 각 셀이 어느 방향을 바라봐야 하는지를 회전값으로 변환한다.

경로 자체만 있으면 어디를 지나가는가는 알 수 있지만, 벽이나 방향성 있는 오브젝트를 배치할 때는 어느 방향을 향하는가도 필요하다.

이 함수는 바로 그 방향 정보를 Quaternion 리스트로 반환한다.

‍

먼저 인접한 두 Grid 좌표의 차이를 계산해 이동 방향 벡터를 얻는다.

Vector3Int direction = gridPositions[i+1] - gridPositions[i];

즉 현재 셀에서 다음 셀로 얼마나 이동했는지를 통해 방향을 구하는 방식이다.

그 다음 Vector3.SignedAngle을 사용한다.

Vector3.SignedAngle(Vector3.right, direction, Vector3.up)

SignedAngle은 두 벡터 사이의 부호 있는 각도를 계산하는 Unity 함수다.

기준축을 Vector3.up으로 두었기 때문에, Y축 회전 기준으로 오른쪽(Vector3.right)에서 현재 방향(direction)까지 몇 도 회전했는지를 계산한다.

왜 Quaternion.LookRotation 대신 이 방식을 썼는지도 설명할 수 있다

LookRotation은 3D 방향 전체를 바라보게 만드는 데 유리하지만, 현재 시스템은 Grid 기반의 직교 방향 회전만 필요하다.

즉, 정확한 3차원 회전보다는 오른쪽 기준 몇 도 돌았는가를 계산하는 방식이 더 명확하고 단순하다.

‍

계산된 각도는 Mathf.RoundToInt로 반올림해서 정수 각도로 정리한 뒤, Quaternion.Euler로 회전값을 만든다.

Quaternion.Euler(0, ..., 0)

Quaternion.Euler는 오일러 각도를 기반으로 Quaternion 회전을 생성하는 Unity 함수다.

Unity 내부에서는 회전을 Quaternion으로 관리하는 것이 일반적이기 때문에, 최종 결과를 Quaternion으로 반환하는 것이 자연스럽다.

결과적으로 이 함수는 '경로 좌표 목록 → 각 구간의 진행 방향 → 오브젝트 회전값 목록' 으로 변환하는 역할을 한다.

‍

‍

4.6. 이동 방향 정의

public static List<Vector3Int> Directions = new()
{
    new Vector3Int(1,0,0),
    new Vector3Int(-1,0,0),
    new Vector3Int(0,0,1),
    new Vector3Int(0,0,-1)
};

이 리스트는 Grid 시스템의 기본 이동 방향을 정의한다.

오른쪽, 왼쪽, 앞, 뒤 네 방향만 포함되어 있으며, 대각선 방향은 포함하지 않는다.

이 구조의 장점은 방향 규칙이 코드 곳곳에 흩어지지 않고 한 곳에 모여 있다는 점이다.

즉 FindNeighbours 같은 함수는 구체적인 방향 값을 직접 알 필요 없이, Directions를 순회하기만 하면 된다.

이렇게 하면 향후 방향 체계가 바뀌더라도, 방향 리스트만 수정하면 된다.

또한, public static으로 선언했기 때문에 객체를 생성하지 않아도 클래스 차원에서 바로 접근할 수 있다.

GridSelectionHelper 자체가 상태를 저장하는 객체가 아니라 기능 모음 역할의 정적 유틸리티 클래스이므로, 이 방향 리스트도 정적으로 두는 것이 구조적으로 자연스럽다.

GridSelectionHelper는 Grid 기반 건축 시스템에서 반복적으로 사용되는 좌표 계산과 경로 탐색 로직을 하나의 Helper 클래스로 정리하기 위해 만든 유틸리티 계층이다.

이 클래스의 핵심은 단순히 좌표를 계산하는 데 있지 않다.

범위 순회, 이웃 셀 탐색, Manhattan Distance, A* 탐색, 경로 방향 회전 계산처럼 Grid 시스템에서 자주 반복되는 공통 연산을 한 곳에 모아, 건축 로직 본체가 더 단순하게 유지되도록 만드는 데 목적이 있다.

또한 현재 구현은 엄밀한 일반형 A*보다는 프로젝트 규모와 목적에 맞게 단순화된 형태를 사용하고 있다.

경로 계산의 정확성보다도, Grid 기반 건축 시스템에서 필요한 수준의 빠르고 직관적인 경로 계산을 제공하는 데 초점을 맞춘 구조다.

비용 계산을 단순화하고, Open List 정렬에 LINQ를 사용한 것도 같은 맥락이다.

즉, 최적 성능보다는 코드의 가독성과 구조 이해를 우선한 구현이라고 볼 수 있다.

결과적으로 GridSelectionHelper는 Grid 기반 건축 시스템에서 좌표 계산, 경로 탐색, 방향 계산을 공통으로 지원하는 계산 유틸리티 계층으로 기능하도록 설계되었다.