Factorio는 이미 찾은 길과 찾지 못한 길을 어떻게 재사용할까요?

길이 없다는 답도 계산 결과입니다

많은 적이 같은 목적지로 이동하면 길 찾기 요청도 반복됩니다. Factorio 개발진은 2015년 기록에서 한 틱에 탐색할 노드 수를 제한해 급격한 프레임 지연을 막았지만, 요청이 쌓이면 적의 반응이 늦어졌다고 설명합니다. 문제는 길 하나의 계산 속도뿐 아니라 비슷한 계산을 얼마나 자주 시작하느냐에도 있었습니다.

가까운 장애물은 간단한 회피로 넘기고, 실패할 때 정식 탐색을 호출하는 방법이 먼저 적용됐습니다. 그러나 호수처럼 큰 장애물을 돌아가는 장거리 이동까지 이 방식으로 해결할 수는 없습니다. 여기서 이미 계산한 경로를 보관하는 캐시가 도움이 됩니다. 아래 내용은 2016년 공식 개발 기록에 소개된 설계 사례이며, 현재 버전의 모든 내부 동작을 설명하는 것은 아닙니다.

처음부터 끝까지 같지 않아도 재사용합니다

이전 방식은 요청의 출발점과 도착점이 저장된 경로의 양 끝에 가까운지 비교했습니다. 개선된 방식은 경로 중간도 후보로 살펴봅니다. 새 출발점에서 기존 경로로 합류하고, 필요한 구간을 따라간 뒤 목적지 쪽으로 빠져나가는 구조입니다.

도식의 A에서 B로 이동한다면 A→X와 Y→B만 새로 찾고, X→Y는 저장된 구간을 사용합니다. 비슷한 방향으로 진격하는 여러 무리가 매번 전체 경로를 다시 계산하지 않아도 되는 셈입니다. 저장 공간은 유한하므로 개발진은 계산 난이도 정보도 함께 보관해 어떤 경로를 비울지 판단했다고 설명합니다.

도착할 수 없었던 요청도 기억합니다

막힌 지형에서 갈 수 없는 목적지를 계속 요청하면 탐색은 실패하더라도 비용을 냅니다. Factorio는 이런 결과도 저장하는 실패 경로 캐시를 소개했습니다. 비슷한 요청이 다시 오면 존재하지 않는 길을 재탐색하는 대신 이전 답을 이용합니다.

다만 이 원리를 다른 프로젝트에 옮길 때는 장애물이 바뀌는 상황을 별도로 설계해야 합니다. 문이 열렸는데 실패 기록을 계속 사용하면 이제 갈 수 있는 길도 막혔다고 판단할 수 있습니다. 이것은 적용 시 고려할 점이며, 해당 개발 기록이 Factorio의 갱신 정책 전체를 공개했다는 뜻은 아닙니다.

작은 격자에서 직접 비교해 봅니다

시험용 격자에 긴 벽과 통로 하나를 만들고, 벽 양쪽에 출발점과 목적지를 여러 개 배치합니다. 먼저 캐시 없이 같은 요청 묶음을 반복한 뒤, 성공 경로를 재사용하는 경우와 실패 결과까지 저장하는 경우를 나누어 비교합니다. 같은 지형과 요청 순서를 유지해야 차이를 해석하기 쉽습니다.

기록할 항목은 탐색 횟수, 방문한 노드 수, 요청 완료까지 기다린 시간입니다. 평균 처리 시간만 보면 소수 요청이 오래 기다리는 문제를 놓칠 수 있으므로 가장 오래 기다린 요청도 확인합니다. 마지막에는 통로를 막았다가 열어 캐시를 무효화한 뒤 결과가 바뀌는지 검사합니다.

이 절차는 원리를 확인하기 위한 실험 제안입니다. 실제 게임의 성능 수치를 재현했다고 주장하는 것은 아닙니다. 중요한 기준은 캐시 적중률 자체보다 반복 계산을 줄이면서도 변경된 지형에 맞는 답을 돌려주는지입니다.

출처

• Factorio FFF #117: 짧은 길 찾기 요청을 줄인 배경
• Factorio FFF #121: 경로 부분 재사용과 실패 경로 캐시

도식은 이 글을 위해 직접 제작했으며 CC BY 4.0으로 제공합니다.