퀘스트 트리 순환 참조 오류를 막는 퀘스트 에디터 설계 규칙

퀘스트 트리는 선행 조건에서 후속 보상으로 향하는 방향 비순환 그래프(DAG, Directed Acyclic Graph) 로 제한하는 것이 가장 안전하다. 에디터는 링크를 만들 때 경로 탐색으로 순환을 즉시 차단하고 저장·빌드 시에도 전체 그래프를 재검증해야 한다.

핵심 요약

퀘스트 A가 퀘스트 B에 의존하고 B가 다시 A에 의존하면 어떤 퀘스트도 시작 또는 완료될 수 없다. 모든 의존성 간선을 추가할 때 to → ... → from 경로가 이미 존재하는지 검사해 차단하고 예외적인 반복 콘텐츠는 일반 퀘스트 트리와 분리된 상태 머신으로 모델링한다.

퀘스트 트리에서 순환 참조는 왜 발생하는가?

퀘스트 데이터는 보통 기획자가 노드와 연결선을 직접 편집한다. 이때 개별 퀘스트의 선행 조건만 읽어서는 전체 의존 관계를 파악하기 어렵다. 특히 아래 상황에서 순환 참조가 자주 생긴다.

분기 퀘스트를 합류시키는 과정에서 이전 퀘스트를 선행 조건으로 다시 연결한 경우
자동 생성된 연계 퀘스트가 원본 퀘스트의 잠금 조건을 수정한 경우
여러 사람이 서로 다른 브랜치에서 퀘스트를 편집한 뒤 데이터를 병합한 경우
반복 퀘스트와 일회성 메인 퀘스트를 같은 의존성 모델로 처리한 경우

예를 들어 Q100 완료 후 Q200이 열리고 Q200 완료 후 Q300이 열리는 구조는 정상이다. 그런데 편집자가 Q300의 보상 수령 후 Q100을 활성화한다는 연결을 선행 조건 간선으로 저장하면 Q100 → Q200 → Q300 → Q100 순환이 된다.

flowchart LR
  Q100[Q100: 마을 조사] --> Q200[Q200: 광산 진입]
  Q200 --> Q300[Q300: 광산 탈출]
  Q300 -.잘못된 선행 조건.-> Q100

이 오류는 단순히 목록 정렬이 꼬이는 수준이 아니다. 서버의 완료 판정이 선행 퀘스트 완료 여부를 재귀적으로 확인한다면 무한 재귀 또는 호출 깊이 초과가 발생할 수 있다. 반대로 재귀를 중단하도록 구현했다면 플레이어에게 영구 잠금 상태를 보여 줄 가능성이 높다.

순환 참조 간선을 추가하려 할 때 에디터가 기존 경로와 차단 이유를 표시하는 화면

순환 참조를 막는 핵심 규칙은 무엇인가?

퀘스트 정의를 그래프로 취급하고 에디터와 런타임 모두 같은 불변식을 지켜야 한다.

규칙	의미	적용 위치	실패 시 처리
방향성 고정	`선행 퀘스트 → 후속 퀘스트`만 간선으로 저장	데이터 모델	반대 방향 입력 거부
자기 참조 금지	`Q → Q` 연결 금지	링크 생성 UI	즉시 차단
DAG 유지	새 간선이 닫힌 경로를 만들면 안 됨	에디터 검증	연결 생성 취소
이중 검증	클라이언트 UI와 저장 API 모두 검증	에디터·서버	저장 거부
반복 분리	재수행은 의존 간선이 아닌 상태 전이로 표현	콘텐츠 모델	별도 반복 정책 사용

가장 중요한 기준은 다음 한 줄로 정리할 수 있다. 새 간선 u → v를 추가하기 전에 이미 v에서 u로 가는 경로가 존재하면 그 간선은 순환을 만들므로 추가하면 안 된다.

퀘스트 에디터에서 순환 검증은 어떻게 구현할까?

1. 데이터 모델의 간선 의미를 하나로 고정한다

prerequisites와 unlocks를 동시에 독립 저장하면 한쪽만 수정되어 불일치가 생기기 쉽다. 원본 데이터는 한 방향만 보관하고 반대 방향 인덱스는 로드 시 계산하는 편이 안전하다.

type QuestId = string;

type Quest = {
  id: QuestId;
  prerequisiteIds: QuestId[];
  repeatPolicy: "once" | "daily" | "weekly";
};

// prerequisiteId -> questId 간선으로 해석한다.
const quests: Quest[] = [
  { id: "Q100", prerequisiteIds: [], repeatPolicy: "once" },
  { id: "Q200", prerequisiteIds: ["Q100"], repeatPolicy: "once" }
];

여러 선행 조건이 모두 필요한지 하나만 충족하면 되는지도 명시해야 한다. 예를 들어 allOf와 anyOf는 완료 조건의 논리식이며 그래프 방향을 바꾸는 이유가 되어서는 안 된다.

2. 새 링크를 만들기 전에 도달 가능성을 검사한다

새 연결 from → to를 추가하려면 기존 그래프에서 to부터 시작해 from에 도달할 수 있는지 DFS 또는 BFS로 검사한다. 도달 가능하면 새 연결을 추가하는 순간 순환이 완성된다.

function wouldCreateCycle(
  graph: Map<QuestId, QuestId[]>,
  from: QuestId,
  to: QuestId
): boolean {
  if (from === to) return true;

  const visited = new Set<QuestId>();
  const stack = [to];

  while (stack.length > 0) {
    const current = stack.pop()!;
    if (current === from) return true;
    if (visited.has(current)) continue;

    visited.add(current);
    for (const next of graph.get(current) ?? []) {
      stack.push(next);
    }
  }

  return false;
}

노드 수를 $V$ , 간선 수를 $E$ 라고 하면 한 번의 DFS/BFS 검증 비용은 다음과 같다.

O(V + E)

일반적인 퀘스트 에디터의 단일 연결 생성에는 충분히 실용적이다. 대규모 라이브 게임처럼 수만 개 노드를 다루는 경우에는 편집 세션에서 위상 순서(topological order)를 캐시하거나 변경된 서브그래프만 재검증할 수 있다. 다만 최적화보다 먼저 저장 API의 전체 검증을 유지해야 한다.

3. 저장 시 전체 DAG 검증을 다시 실행한다

UI 차단만으로는 부족하다. 데이터 임포트, 병합 충돌, 운영 도구 API 호출은 UI를 거치지 않을 수 있다. 서버는 저장 요청마다 Kahn 알고리즘 또는 DFS 색상 표기를 사용해 전체 퀘스트 그래프를 검증해야 한다.

Kahn 알고리즘에서는 진입 차수가 0인 노드를 차례대로 제거한다. 제거된 노드 수가 전체 노드 수보다 작다면 그래프에 순환이 있다는 뜻이다. 남은 노드에는 순환 자체의 노드뿐 아니라 그 순환에 의존하는 후속 노드도 포함될 수 있다.

function hasCycle(graph: Map<QuestId, QuestId[]>): boolean {
  const indegree = new Map<QuestId, number>();

  for (const [id, nextIds] of graph) {
    if (!indegree.has(id)) indegree.set(id, 0);
    for (const nextId of nextIds) {
      indegree.set(nextId, (indegree.get(nextId) ?? 0) + 1);
    }
  }

  const queue = [...indegree]
    .filter(([, degree]) => degree === 0)
    .map(([id]) => id);
  let queueIndex = 0;
  let processed = 0;

  while (queueIndex < queue.length) {
    const id = queue[queueIndex++];
    processed += 1;

    for (const nextId of graph.get(id) ?? []) {
      const degree = indegree.get(nextId)! - 1;
      indegree.set(nextId, degree);
      if (degree === 0) queue.push(nextId);
    }
  }

  return processed !== indegree.size;
}

오류 메시지와 편집 UX는 어떻게 설계해야 할까?

기획자에게 “순환 참조 오류”만 표시하면 수정 지점을 찾는 데 시간이 든다. 에디터는 차단한 연결과 기존 경로를 함께 제시해야 한다.

잘못 추가하려는 간선: Q300 → Q100
기존 경로: Q100 → Q200 → Q300
권장 행동: 해당 관계가 반복 콘텐츠라면 repeatPolicy 또는 재시작 조건으로 옮기기

또한 노드 선택 UI에서 현재 노드의 후손은 선행 퀘스트 후보에서 비활성화하는 것이 좋다. 저장 버튼을 누른 뒤 실패시키는 방식보다 연결을 시도하는 순간 이유를 설명하는 방식이 훨씬 빠르게 문제를 해결한다.

후손 퀘스트가 선행 조건 후보에서 비활성화되고 경고 문구가 표시된 퀘스트 에디터 UI

반복 퀘스트를 순환 간선 없이 표현하려면?

반복 퀘스트는 “다시 시작한다”는 표현 때문에 순환 간선으로 모델링하기 쉽지만 일반 퀘스트 트리의 의존성과는 다른 문제다. 퀘스트 정의 그래프는 DAG로 유지하고 반복 가능 여부는 플레이어별 진행 상태에서 계산한다.

요구사항	잘못된 모델	권장 모델
매일 재수행	완료 노드에서 시작 노드로 연결	`repeatPolicy: daily`와 일일 리셋 시각
특정 평판 이후 재개방	후속 퀘스트가 이전 퀘스트를 다시 해금	평판 임계값 기반 활성화 규칙
시즌 반복	시즌 마지막 퀘스트에서 첫 퀘스트로 연결	시즌 ID와 시즌별 진행 상태 초기화

예를 들어 일일 퀘스트의 활성 조건은 다음처럼 정의할 수 있다. 여기서 lastCompletedAt은 플레이어 상태이고 퀘스트 그래프의 간선이 아니다.

available = prerequisitesMet \land now \geq nextResetAt(lastCompletedAt)

이 분리는 콘텐츠 정의를 예측 가능하게 만들고 운영 중 리셋 정책을 바꿀 때도 선행 관계 데이터에 영향을 주지 않는다.

자주 묻는 질문 (FAQ)

순환 참조가 있어도 런타임에서 방문 집합을 쓰면 충분한가?

아니다. 방문 집합은 무한 루프를 막는 방어 수단일 뿐이다. 플레이어가 진행할 수 없는 콘텐츠를 배포하지 않도록 에디터와 저장 API에서 원인을 차단해야 한다.

선행 조건이 여러 개인 퀘스트도 DAG 검증이 필요한가?

필요하다. allOf, anyOf처럼 조건 결합 방식이 달라도 각 퀘스트 의존 간선 전체가 순환하지 않아야 한다.

병합 충돌로 생긴 순환은 언제 찾아야 하는가?

콘텐츠 저장 시점뿐 아니라 CI의 데이터 검증 단계에서도 찾아야 한다. 배포 후보 데이터 전체를 검사하고 순환에 포함된 퀘스트 ID와 경로를 빌드 로그에 출력하는 것이 좋다.

정리

퀘스트 트리의 순환 참조 방지는 런타임 재귀 제한이 아니라 콘텐츠 작성 규칙의 문제다. 퀘스트 의존성을 DAG로 고정하고 링크 생성 시 경로 탐색으로 막으며 저장·CI에서 전체 그래프를 재검증하자. 반복성은 순환 간선이 아니라 플레이어 상태와 리셋 정책으로 분리하면 퀘스트 에디터의 안전성과 기획 편의성을 함께 확보할 수 있다.