던전 생성의 핵심 과제와 ASP의 도입

액션 어드벤처 게임의 던전은 단순한 공간 배치를 넘어 '잠금과 열쇠'로 얽힌 복잡한 시간적·구조적 의존성을 가짐. 개발자가 의도한 순서대로 아이템을 획득하고 장애물을 극복하게 만드는 논리적 구조를 생성하는 것은 매우 까다로운 작업임. 본 연구는 이를 해결하기 위해 선언적 제약 조건 해결 방식인 **ASP(Answer Set Programming)**를 도입함.

그래프 기반 모델링과 '보스 키' 분석

던전의 구조를 물리적 타일 맵이 아닌 추상적인 그래프 모델로 설계함. 이를 위해 게임 디자인 분석가 마크 브라운(Mark Brown)의 보스 키(Boss Key) 스타일 분석법을 차용함. 이 방식은 공간적 관계와 시간적 진행 순서를 명확하게 분리하여, 플레이어가 특정 시점에 어떤 영역에 접근할 수 있는지 시각적으로 파악하게 해줌.

시스템의 주요 특징

• 제약 조건 만족(Constraint Satisfaction): "열쇠는 반드시 잠긴 문보다 먼저 발견되어야 한다"와 같은 하드 제약 조건을 논리 규칙으로 정의하여 플레이 불가능한 레벨 생성을 원천 차단함.
• 표현 범위 분석: 생성된 던전의 선형성(Linearity), 관대함(Leniency, 안전함의 정도), 중복 경로 등을 정량적으로 측정하여 생성기의 성능을 평가함.
• 유연한 제어: 논리 규칙 몇 줄을 수정하는 것만으로 던전의 전체적인 스타일(선형적 vs 탐험 중심)을 즉각적으로 변경할 수 있음.