통로 안에서 줄을 당긴다

길찾기가 답을 내놨습니다. 그런데 그 답을 그대로 따라 걸으면 이상합니다.

격자에서 나온 경로는 계단처럼 꺾입니다. 빈 들판 한가운데서도 45도씩 각 잡고 돕니다. 내비메시에서 나온 것은 더 이상합니다. 삼각형 가운데를 이어 놓으면 아무 이유 없이 지그재그입니다.

이유는 하나입니다. 탐색은 칸이나 폴리곤 단위로 답하는데, 유닛은 연속된 공간에서 움직입니다. 칸 가운데를 지나야 할 이유가 없고, 삼각형 가운데를 지나야 할 이유도 없습니다.

보이면 가운데를 버린다

가장 간단한 방법부터 봅니다. 한 점에서 앞쪽 점이 곧장 보이면, 그 사이의 점들은 필요 없습니다.

점이 아홉 개에서 네 개로 줄었습니다. 길이는 9.66 에서 9.37 로 3% 남짓 줄었을 뿐입니다. 이 방법의 값어치는 길이보다 점의 수와 모양에 있습니다. 유닛이 프레임마다 확인할 목표점이 줄고, 계단이 사라집니다.

이것을 스트링 풀링(String Pulling) 이라고 부릅니다. 점들을 실로 꿰어 놓고 양 끝을 당기는 그림입니다.

List<Vector2> Pull(List<Vector2> path) {
    var result = new List<Vector2> { path[0] };
    int anchor = 0;

    while (anchor < path.Count - 1) {
        int far = path.Count - 1;
        while (far > anchor + 1 && !LineOfSight(path[anchor], path[far]))
            far--;                      // 안 보이면 한 칸씩 당겨 온다

        result.Add(path[far]);
        anchor = far;
    }
    return result;
}

LineOfSight 가 이 코드의 전부이고, 함정도 거기 있습니다. 시야 판정이 실제 이동 규칙과 같아야 합니다. 대각선으로 벽 모서리를 스치는 것을 막아 놓고 시야 검사는 선분만 본다면, 다듬은 경로가 유닛이 지나갈 수 없는 자리를 지나갑니다. 길찾기는 맞는데 유닛이 벽에 낍니다.

비용은 시야 검사 횟수입니다. 최악이 O(n²) 이고, 검사 하나가 격자 훑기라 싸지 않습니다. 경로가 길수록 다듬는 값이 찾는 값을 넘어서기도 합니다.

통로가 폴리곤이면 더 잘할 수 있다

내비메시 길찾기가 실제로 내놓는 것은 경로가 아니라 지나갈 폴리곤의 목록입니다. 이웃한 두 폴리곤이 맞닿은 변을 포털(portal) 이라고 부르고, 통로는 포털의 줄로 표현됩니다.

이 경우에는 시야 검사를 한 번도 안 하고 그 통로 안에서의 진짜 최단 경로를 뽑을 수 있습니다. 깔때기 알고리즘(Funnel Algorithm) 입니다.

발상은 이렇습니다. 지금 서 있는 점에서 왼쪽으로 볼 수 있는 한계선과 오른쪽 한계선을 들고 갑니다. 포털을 하나씩 보면서 그 두 선을 좁혀 나갑니다. 좁아지기만 하면 계속 갑니다. 한쪽이 반대쪽을 넘어가는 순간, 더는 곧게 갈 수 없다는 뜻이고, 넘긴 쪽 끝점이 꺾이는 자리가 됩니다.

포털 일곱 개를 한 번 훑어서 꺾이는 점 세 개가 나왔습니다. 길이는 655 에서 518 로 21% 줄었습니다.

꺾이는 자리가 전부 포털의 끝점이라는 데 주목할 만합니다. 당연합니다. 장애물이 없는 곳에서 꺾을 이유가 없으니, 꺾인다면 그 자리는 벽의 모서리입니다.

왜 한 번만 훑으면 되나

두 방법의 성질이 꽤 다릅니다.

깔때기가 한 번 훑기로 끝나는 이유는 버린 것을 다시 볼 일이 없기 때문입니다. 왼쪽 선이 좁아졌다는 것은 그만큼의 각도가 영영 막혔다는 뜻입니다. 되돌릴 일이 없습니다. 꺾이는 점이 정해지면 거기서 깔때기를 다시 열고, 그 앞부터 다시 봅니다. 되돌아가는 것처럼 보이지만 이미 확정된 앞부분은 건드리지 않습니다.

// 세 점의 방향을 부호로 본다. 이 함수 하나로 좌우 판정이 끝난다
float Cross(Vector2 a, Vector2 b, Vector2 c)
    => (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);

foreach (var portal in portals) {
    if (Cross(apex, right, portal.right) >= 0) {           // 오른쪽이 안쪽으로
        if (apex == right || Cross(apex, left, portal.right) < 0) {
            right = portal.right;                          // 좁힌다
        } else {
            corners.Add(left);                             // 왼쪽을 넘었다
            apex = left; right = left;                     // 거기서 다시 연다
            RestartFromApex();
            continue;
        }
    }
    // 왼쪽도 똑같이, 좌우만 뒤집어서
}

좌우를 뒤집은 같은 코드가 두 번 나오는 것이 이 알고리즘의 생김새입니다. 한쪽을 짜고 부호와 이름을 뒤집어 복사하면 됩니다.

유닛에는 반지름이 있다

여기까지의 경로는 점 하나가 지나가는 선입니다. 꺾이는 자리가 벽 모서리에 딱 붙어 있습니다. 반지름이 있는 유닛이 그대로 따라가면 어깨가 벽에 낍니다.

두 가지로 처리합니다.

• 포털을 미리 줄인다. 포털 양 끝을 반지름만큼 안쪽으로 당겨 놓고 깔때기를 돌립니다. 통로가 반지름보다 좁으면 그 통로는 못 지나간다는 뜻이고, 그 판정도 여기서 나옵니다
• 꺾이는 점을 밀어낸다. 나온 코너를 모서리에서 반지름만큼 바깥으로 옮깁니다. 간단하지만 두 모서리가 가까우면 밀어낸 점이 다른 벽으로 들어갈 수 있습니다

앞쪽이 안전합니다. 통로를 만들 때 이미 유닛 크기를 아는 경우가 대부분입니다.

곡선으로 만드는 것은 다른 문제다

꺾인 선이 여전히 각져 보인다고 베지어나 캣멀롬으로 둥글리는 경우가 많습니다. 그건 보기 좋게 만드는 일이고, 경로를 짧게 만드는 일과는 다릅니다.

• 곡선은 원래 선보다 길어집니다. 코너를 자르는 게 아니라 코너 바깥으로 부풀기 때문입니다
• 부푼 쪽이 벽이면 벽을 스칩니다. 곡선을 만든 뒤에 다시 검사해야 합니다
• 유닛이 회전 속도를 가진다면 애초에 곡선이 필요 없습니다. 따라가는 쪽에서 부드러워집니다

경로를 곡선으로 바꾸는 대신 유닛의 방향을 서서히 돌리는 쪽이 대개 더 싸고 덜 깨집니다.

다듬어도 안 되는 것

다듬기는 주어진 통로 안에서만 일합니다. 통로 바깥으로 나가지 않습니다.

그래서 탐색이 고른 통로가 멀리 돌아가는 것이었다면, 아무리 당겨도 그 길입니다. 구역 단위로 고른 구간이나 점프 포인트로 이은 구간도 마찬가지입니다. 그것들은 전부 통로를 정하는 단계입니다.

경로가 이상하면 다듬기를 의심하기 전에 통로를 먼저 보세요. 다듬기로 고쳐지는 것은 모양이지 선택이 아닙니다.

정리

길찾기의 답은 지나갈 통로이고, 걷는 선은 거기서 한 번 더 뽑아내는 것입니다.

• 격자나 웨이포인트에서는 보이는 점끼리 이어 가운데를 버립니다. 시야 판정이 이동 규칙과 같아야 합니다
• 내비메시처럼 포털 목록이 있으면 깔때기 알고리즘으로 시야 검사 없이 한 번에 뽑습니다. 그 통로 안에서는 최단입니다
• 꺾이는 자리는 언제나 포털의 끝점, 즉 벽의 모서리입니다
• 유닛 반지름은 포털을 미리 줄여 처리하는 편이 안전합니다
• 곡선으로 만드는 것은 보기 좋게 하는 일이고 경로를 짧게 하는 일이 아닙니다
• 다듬기는 통로 안에서만 일합니다. 통로 선택이 틀렸으면 다듬어도 그 길입니다