시간·공간 예약은 “갈 수 있는 경로”를 찾는 문제를 “동일한 시각에 같은 자원을 누가 점유하는가”라는 권위 상태와 연결합니다. 계획 후보는 실행 허가가 아니며, 예약 성공도 실제 이동 시점의 충돌·세대·속도 조건을 자동으로 보장하지 않습니다. 따라서 셀·간선·몸체 footprint와 시간 horizon을 같은 좌표계에서 추적하고, 실패하면 안전하게 대기하거나 다시 계획해야 합니다.
개별 최단 경로와 동시 실행 가능성
A와 B가 같은 빈 교차로 C에 다음 틱 도착하려 하면 공간상 경로는 둘 다 있어도 시간 충돌입니다. state를 (cell,arrivalTick)으로 두면 wait·순차 통과를 표현할 수 있습니다. A가 C를 틱1, 출구를 틱2에 쓰고 B가 옆 대기 공간에 틱1까지 머문 뒤 C를 틱2에 쓰는 식입니다. 실제 출구·대기 공간이 있다는 전제가 필요합니다.
| 충돌 | 검사할 예약 |
|---|---|
| 같은 cell·같은 tick | vertex 점유 |
| A→B와 B→A 동시 이동 | 반대 방향 edge swap |
| 대각 중간 교차 | segment/시간 교차 |
| 큰 몸체 | 전체 footprint·이동 sweep |
| 속도 차이 | 여러 시간 slot의 체류 |
위치 하나의 예약만으로 모든 충돌을 막을 수 없습니다. 무한 wait 상태를 만들지 않도록 비용·최대 시간 범위를 정하고 목표 점유가 이후에도 지속되는지 포함합니다.
빈칸 조회와 예약 확정의 원자 경계
한 tick의 상태를 계획 후보 생성 → 결정적 순서 부여 → 전체 footprint 조건 확인 → 원자 예약 → 실행 직전 재검증으로 기록합니다. A와 B가 동시에 같은 cell을 읽어도 순서가 A-B로 정해지면 A만 예약되고 B는 다른 후보를 찾거나 대기합니다. 이후 A가 despawn되어 ID가 재사용되면 generation 검사가 옛 A의 취소가 새 객체의 예약을 지우지 않게 합니다.
두 NPC가 같은 (cell,tick)을 비어 있다고 읽은 뒤 각각 저장하면 둘 다 성공하므로, 조회와 확정 사이를 원자 경계로 묶습니다. 권위 tick owner가 의도를 결정적 순서로 처리하거나 (cell,tick) 조건부 생성과 version 검사를 사용해 한 요청만 확정합니다. 여러 cell/edge를 차지하는 footprint는 필요한 전체 조건을 확인한 뒤 한 번에 예약하고, 준비 상태를 쓰더라도 부분 예약은 이동 허가로 공개하지 않습니다.
그림을 글로 읽기
- 각 NPC의 시간·공간 후보
- tick·aging·안정 tie-break 순서
- cell·edge·footprint 원자 예약
- 현재 세대·충돌·행동 확인 후 이동
- 각 NPC의 시간·공간 후보 → tick·aging·안정 tie-break 순서: 같은 tick 의도
- tick·aging·안정 tie-break 순서 → cell·edge·footprint 원자 예약: 최신 예약 상태
- cell·edge·footprint 원자 예약 → 현재 세대·충돌·행동 확인 후 이동: 조건부 실행권
예약 record에는 owner, entity generation(같은 ID가 재사용돼도 이전 객체와 구분하는 세대), plan/request ID, 대상 tick, 만료 시각을 함께 둡니다. 취소·재접속·실행 실패가 나와도 현재 요청의 세대와 일치하는 예약만 해제하고, 새 owner가 만든 예약은 지우지 않습니다. 만료 처리와 신규 예약이 같은 틱에 겹치면 어느 쪽을 먼저 적용할지도 고정합니다.
짧은 Horizon의 안전한 끝 상태
Horizon의 길이는 탐색 성능만으로 고르지 않습니다. 현재 속도와 제동 거리, 다음 병목의 점유 여부, 계획 실패 시 머물 수 있는 안전 cell을 함께 계산합니다. 예를 들어 H=3에서 tick 3의 목적 cell이 막혀 있는데도 이동을 확정하면 다음 계획이 실패할 때 교차로를 점유한 채 멈출 수 있으므로, 끝 상태 조건에서 그 후보를 제외하거나 안전 대기 상태를 예약해야 합니다.
미래 H틱까지만 예약하면 메모리와 탐색량은 줄지만 H틱 뒤 병목을 미리 보지 못할 수 있습니다. 그래서 horizon 끝에 도착했을 때 안전하게 멈출 위치, 필요한 제동 거리, 다음 구간을 확보했는지를 조건으로 넣습니다. 실제 이동이 늦어져 예정 slot과 어긋나면 후속 slot을 갱신하고 다른 예약과 다시 대조합니다.
모든 NPC가 horizon 끝에서 동시에 재계획하면 주기적 CPU 파도가 됩니다. 시작 phase·계획 budget을 분산하고 실행 중 예약은 필요한 prefix만 보존하면서 미래 부분을 원자 교체합니다. 다음 계획 실패 시 현재 위치에 안전하게 머무를 수 있어야 합니다.
Aging과 공간 부족·교착 해소의 한계
한 cell 폭 외길에서 두 몸체가 마주 보고 있고 서로의 교환을 금지하며 뒤로 물러날 공간도 없으면, 우선순위를 바꾸는 것만으로는 이동 해가 생기지 않습니다. 이때는 누가 누구를 기다리는지 나타내는 wait-for cycle, 마지막으로 진행한 시점, 대기 나이, 실패 횟수를 보고 실제로 비켜설 위치와 후퇴 경로를 찾아야 합니다. NPC와 직접 조작 player에게 강제 후퇴를 적용할 권한과 UX는 다를 수 있습니다.
prioritized planning은 빠르지만 계획 순서에 따라 가능한 해를 놓치고 최적 joint plan을 보장하지 않습니다. 좁은 병목에 제한된 joint search·예약 재배치·양보 목표를 적용할 수 있으나 계산 상한을 둡니다.
우선순위 변경의 Replay 가능성과 결정성
대기 나이는 local wall time이 아니라 합의된 tick·기록된 진행 기준으로 계산하고 동점은 안정 entity ID·라운드 순서로 정합니다. network/thread 도착 우연에만 맡기지 않습니다. 만료된 의도는 승격하지 않고 고우선순위의 계속 유입에도 낮은 작업의 최소 진행을 유지합니다.
같은 입력·tick·정책에서 예약 결과를 재현하고 vertex/edge/다중cell·취소·lease 경계·handoff·해 없는 외길을 시험합니다. 도달률뿐 아니라 최대 대기·교착·재계획·부분 예약·유령 점유를 봅니다. 이 노트는 예약 설계이며 실제 다중 agent planner를 실행한 결과는 아닙니다.