좁은 격자 통로에서 두 캐릭터가 서로 마주 보고 이동합니다. 개별 최단 경로만 찾으면 왜 막히며, 도착 시간까지 포함하면 무엇이 달라지나요?

개별 캐릭터의 최단 경로는 다른 캐릭터가 없는 정적 공간에서의 경로일 뿐, 여러 캐릭터가 같은 시간에 움직여도 실행 가능한 계획이라는 뜻은 아닙니다. 한 틱에 셀 하나를 점유하고 서로의 위치를 교환하는 이동도 충돌이라고 전제하면, 두 캐릭터가 좁은 통로에서 각자 가운데 셀을 향할 때 같은 시각에 충돌합니다. 위치만 상태로 저장하지 말고 (셀, 도착 틱)을 상태로 보아 기다림과 순차 통과를 표현해야 합니다. 이 문제를 협력적 경로 탐색(cooperative pathfinding)이라고 부릅니다.

시간까지 포함한 충돌

설명용으로 교차로의 왼쪽 A와 오른쪽 B가 가운데 셀을 향하고, 통과 후 빠져나갈 별도 출구와 양보할 대기 공간이 있다고 하겠습니다. 틱 0에는 서로 다른 셀에 있지만, 둘 다 틱 1에 가운데 셀을 예약하면 셀 충돌입니다. 한쪽이 틱 1에 현재 셀에서 기다리고 다른 쪽이 틱 2에 통과하도록 시간표를 바꾸면 셀 충돌을 피할 수 있습니다. 단, A와 B가 서로의 셀을 동시에 바꾸는 간선 교환, 대각선으로 경로를 교차하는 이동, 한 캐릭터가 여러 셀을 차지하는 경우도 검사해야 합니다. 기다릴 공간이 없는 한 칸 외길에서 양쪽이 이미 마주 보고 있다면 시간 축을 추가해도 해가 생기지 않습니다. 알고리즘이 실패한 것이 아니라 주어진 점유 규칙에서 실행 가능한 해가 없는 것입니다.

예약과 우선순위의 한계

실무에서는 제한된 미래 구간인 reservation horizon만 보고 셀과 시간 슬롯을 예약하는 방식이 현실적입니다. 우선순위가 높은 캐릭터의 경로를 먼저 고정하고 다음 캐릭터가 예약을 피해 탐색하면 계산은 단순하지만, 순서에 따라 가능한 해를 놓치거나 낮은 우선순위 캐릭터가 계속 밀릴 수 있습니다. 이런 방식은 우선순위 기반 계획(prioritized planning)입니다. 고정 우선순위가 불리한 캐릭터에는 나이 증가, 라운드 로빈, 예약 재시도 횟수 상한을 적용할 수 있습니다. 모든 에이전트의 전역 최적 계획을 원하면 시간·공간 그래프의 공동 탐색이 필요하지만, 에이전트 수와 탐색 폭발 비용이 훨씬 커집니다. 예약은 실제 속도와 실행 상태가 바뀌면 갱신해야 합니다. 예약만 해 두고 캐릭터가 멈추거나 목표를 바꾸면 다른 캐릭터가 불필요하게 기다리므로, 점유자·틱·만료를 기록하고 짧은 구간이 끝날 때 재계산합니다.

충돌 확정은 입력 도착 순서가 아니라 재현 가능한 우선순위로 처리해야 서버마다 결과가 달라지지 않습니다. 테스트는 외길, 교차로, 병목, 목표 변경, 속도 차이, 교환 이동, 예약 만료를 포함합니다. 도달률만 보지 말고 교착 시간, 평균·최대 대기, 재탐색량, 특정 캐릭터의 기아를 확인하겠습니다. 공간 최단 경로를 실행 가능한 시간-공간 계획(space-time plan)으로 바꾸는 것이 핵심입니다. 기다림 비용을 0으로 두면 서로 다른 시각의 동률 상태가 끝없이 생겨 탐색이 종료되지 않을 수 있으므로 기다림 비용과 최대 대기 틱을 정해야 합니다. 반대로 비용을 너무 크게 두면 좁은 통로에서 필요한 양보가 사라집니다. 예약표에는 셀뿐 아니라 이동 간선과 에이전트 footprint를 기록하고, 계획이 실제 속도와 다르면 다음 슬롯을 다시 예약하겠습니다. 우선순위 기반 계획은 빠른 근사이지 교착을 자동으로 해결하지 않습니다.

사이클이 발견되면 한 에이전트를 뒤로 물리거나 임시 양보 지점을 목표로 하는 복구 계획을 만들고, 반복 양보로 생기는 기아를 실패 횟수와 마지막 성공 시각으로 완화합니다. 정확한 공동 탐색은 충돌 비용이 큰 병목 구간에만 적용해 예산을 통제할 수 있습니다.