길찾기가 조용히 실패할 때

1. 쿼리마다 23만 칸을 지우고 있었다

A* 구현에서 가장 흔한 성능 함정이다. 탐색에는 셀마다 두 가지 상태가 필요하다 — 시작점에서의 최소 비용(gScore)과 이미 확정됐는지 여부(closed). 쿼리를 새로 시작할 때 이걸 초기화해야 하므로, 자연스럽게 이렇게 쓴다.

gScore.fill(Infinity);
closed.fill(0);

320m 맵에서는 셀이 25,600개라 이 두 줄이 무시할 만했다. 960m에서는 230,400개가 된다. 경로 요청 한 건마다 46만 번의 쓰기가 탐색을 시작하기도 전에 일어난다. 웨이브가 스폰되면서 수십 기가 동시에 경로를 요청하면 이것만으로 프레임이 무너진다.

해결책은 배열을 지우지 않는 것이다. 대신 세대 스탬프를 둔다. 값 배열과 나란히 같은 크기의 Uint32Array를 두고, 거기에 "이 값이 몇 번째 쿼리에서 쓰였는지"를 기록한다.

let navGen = 1;                      // 쿼리마다 1 증가
const gAt = (i) =>
  gScoreGen[i] === navGen ? gScore[i] : Infinity;

스탬프가 현재 세대와 다르면 그 칸의 값은 이전 쿼리의 잔여물이므로 읽는 쪽에서 Infinity로 취급한다. 쓸 때만 스탬프를 갱신한다. 초기화 비용이 O(셀 수)에서 O(1)로 떨어진다 — navGen을 하나 올리는 것이 전부다.

한 가지 함정이 있다. Uint32Array는 언젠가 넘친다. 42억 번째 쿼리에서 navGen이 0으로 돌아가면 아직 0인 채로 남아 있던 칸들이 갑자기 "현재 세대"로 읽힌다. 실전에서 도달할 일은 거의 없지만, 도달하면 원인을 절대 못 찾는 종류의 버그다. 한 줄로 막을 수 있으면 막는 게 맞다.

if (++navGen === 0xffffffff) {
  gScoreGen.fill(0); closedGen.fill(0); navGen = 1;
}

2. 반복 상한이 만든 조용한 거짓말

이게 더 나쁜 쪽이었다. A*에는 보통 반복 상한을 둔다 — 막힌 목표를 향해 무한히 탐색하다 프레임을 잡아먹는 것을 막기 위해서다. 이 프로젝트의 상한은 14,000 반복이었다.

160×160 = 25,600칸 그리드에서 14,000은 전체의 55%다. 넉넉하다. 480×480 = 230,400칸에서 14,000은 6%다. 맵을 절반쯤 횡단하는 경로는 상한에 먼저 걸린다.

문제는 상한에 걸렸을 때의 동작이었다. 실패하면 경로를 못 찾았다고 알리는 게 아니라 직선 이동으로 폴백했다. 그게 원래 의도였다 — 짧은 거리에서 A*가 실패하면 대개 목표가 살짝 막힌 경우이고, 직선으로 밀어붙이면 물리 충돌이 알아서 처리한다.

그런데 960m에서는 이 폴백이 정상 경로가 되어버렸다. 맵을 횡단하는 모든 명령이 조용히 직선 이동으로 바뀌었다. 유닛은 성벽으로 걸어가 부딪히고, 호수로 걸어 들어갔다. 로그도 예외도 없다. 그냥 AI가 멍청해 보인다.

교훈: 폴백은 그것이 폴백임을 세어야 한다. "실패 시 대충 동작"은 실패율이 낮을 때만 합리적이고, 실패율은 조건이 바뀌면 변한다. 폴백 카운터가 있었다면 이건 1분 안에 찾았다.

3. 2계층 구조: 개략 라우팅 + 국소 정밀

상한을 올리는 건 답이 아니다. 그러면 장거리 경로 하나가 23만 칸을 다 뒤질 수 있게 되고, 비용은 상한이 막아주던 그 문제로 돌아간다. 필요한 건 탐색 공간 자체를 줄이는 것이다.

정밀 그리드는 2m 셀이다. 그 위에 4×4를 묶은 8m 개략 그리드를 얹었다. 셀 수가 1/16로 줄어드니 480² 대신 120², 14,400칸이다. 맵 전체를 뒤져도 상한 안에 들어온다.

직선거리 90m를 넘는 요청은 두 단계로 처리한다.

1. 개략 경로를 8m 그리드에서 먼저 찾는다 — 어느 회랑을 지날지만 정한다.
2. 그 회랑 안에서 정밀 A*를 돌린다 — 실제 장애물을 피하는 것은 여기서.

개략 셀을 "막힘"으로 판정하는 기준이 중요하다. 하나라도 막힌 정밀 셀이 있으면 막힘으로 치면, 나무 한 그루가 8m 회랑 전체를 닫아버린다. 그러면 개략 경로가 존재하지 않는다고 나오고 실제로는 지나갈 수 있는 길을 포기한다.

반대로 하나라도 뚫려 있으면 통과로 치면, 개략 경로가 실제로는 못 지나가는 회랑을 지시한다. 그러면 정밀 단계에서 다시 실패한다.

절충으로 16칸 중 55% 이상(9칸)이 막혔을 때만 개략 셀을 막힘으로 판정했다. 이 임계값은 이론적으로 도출한 게 아니라, 숲 밀도와 성벽 두께를 놓고 양쪽 실패 모드를 다 보면서 맞춘 값이다. 이런 상수는 정직하게 "튜닝값"이라고 적어두는 게 낫다.

4. 목적지를 공유하는 무리에는 흐름장이 맞다

웨이브는 특별한 성질이 있다. 스폰된 전원이 같은 곳을 향한다. 40기가 각자 A*를 40번 돌리는 것은 같은 계산을 40번 하는 것이다.

이럴 때는 유닛당 경로 대신 흐름장(flow field)이 맞다. 목적지에서 시작해 그리드 전체에 대해 "여기서는 어느 방향으로 가야 하는가"를 한 번 계산해 두면, 그 스쿼드의 모든 유닛이 자기 위치의 셀만 읽으면 된다. 스폰당 1회 계산, 전원 공유. 유닛이 늘어도 계산량은 늘지 않는다.

대신 흐름장은 목적지가 바뀌면 전체를 다시 계산해야 하므로, 플레이어가 개별 명령을 내리는 아군 유닛에는 맞지 않는다. 아군은 목적지가 제각각이고 자주 바뀌기 때문이다. 같은 문제에 두 알고리즘을 쓰는 게 맞을 때가 있다 — "무리가 한 곳으로"와 "개인이 제각각"은 실은 다른 문제다.

5. 측정

맵을 횡단하는 경로 요청 한 건의 비용은 320m에서 0.21ms, 960m에서 1.73ms였다. 8.2배 — 면적 배율 9배와 거의 같다. 이게 청킹으로 숨길 수 없는 종류의 비용이라는 증거다. 렌더링은 보이는 것만 그리면 되지만, 길찾기는 보이지 않는 지형도 지나가야 한다.

정상상태 시뮬레이션 비용은 유닛 약 280~315기에서 p50 0.4ms, p95 1.7ms로 측정됐다. 다만 이 측정에는 주의할 점이 있었다. 처음 계측에서 p95가 7.7ms로 나왔는데, 원계열을 보니 앞쪽 3개 샘플만 5ms대이고 나머지는 0.3~0.4ms였다. 측정 루프의 워밍업 구간이 백분위수를 오염시킨 것이다. 백분위수는 분포가 정상상태일 때만 의미가 있다.

6. 정리

• 쿼리마다 배열을 초기화하지 마라. 세대 스탬프로 O(1)이 된다.
• 반복 상한은 그리드 크기에 대한 비율로 생각하라. 절대값은 맵이 커지면 의미가 변한다.
• 폴백은 세어라. 조용한 폴백은 조용한 버그가 된다.
• 탐색 공간을 줄여라. 상한을 올리는 것은 문제를 미루는 것이다.
• 목적지를 공유하는 무리는 다른 문제다. 흐름장이 맞다.