아이작에서의 던전 생성 알고리즘

핵심알고리즘 

모든 스테이지에는 항상 상점방(Shop), 보상방(Reward), 보스방(Boss) 최소 3개의 특별방(Special Room)이 있다. 다른 특별방은 랜덤하게 추가된다. 그리고 비밀방(Secret Room)을 제외하면 모든 방에는 순환(Loop)가 없다.

 

게임은 챕터가 진행되면서 방의 갯수가 점차 많아지고, 방의 컨텐츠가 조금씩 바뀌지만, 기본적인 알고리즘은 같다.

 

알고리즘의 진행과정은 간단하다. 먼저 평면도(Floor Plan)을 만든다. 그리고 몇몇방은 특별방으로 지정된다. 마지막으로 방의 인테리어 및 디테일한 부분을 적절한 풀에서 선택한다.

평면도

평면도는 그리드(Grid)의 형태로 되어있고, 모든 칸에는 두자릿수 번호가 있고, 이 번호는 칸의 위치를 의미한다. 칸의 일의자리는 X좌표 십의자리는 Y좌표를 의미한다. 즉, 단순히 +10, -10, +1, -1을 더하는것만으로 인접한 칸에 접근할 수 있다.

 

평면도ㅇ는 단순히 방의 생성과 위치를 결정하고, 방의 컨텐츠는 나중에 결정된다. 먼저 방의 개수는 다음 식의 의해 결정된다.

$$random(2) + 5 + level \times 2.6$$

위 수식에 의해 첫번째 레벨에서는 7개에서 8개의 방으로 시작해 레벨이 진행됨에 따라 2개 혹은 3개씩 늘어난다.

 

이제 35번칸에 시작방(Start Room)을 만들고 시작방을 큐에 넣는다. 큐에 들어간 방을 하나씩 꺼내어 네방향의 인접한 방에대해서 아래와 같은 알고리즘을 수행한다.

 

• 현재 방번호에 +10, -10, +1, -1을 더하여 접근할 칸을 결정한다.
• 만약 인접칸에 이미 방이 만들어져있다면 방을 만들지 않는다.
• 만약 인접칸이 2개이상의 방으로 채워져있는 인접칸을 가지고있다면 방을 만들지 않는다.
• 만약 현재 스테이지에서 만들어야할 방의 개수가 이미 만들어졌다면 방을 만들지 않는다.
• 50%확률로 방을 만들지 않는다.
• 위 조건을 모두 통과한경우 방을 만들고 만들어진 방을 큐에 넣는다.

만약 현재방이 네방향의 인접칸에 모두 방을 만드는데 실패했다면 막다른방(End Room)이라는 배열에 추가한다. 이 배열에 있는 방들은 나중에 특별방으로 지정된다.

 

위 알고리즘은 방을 너비우선탐색(BFS, Breadth-First Search)방식으로 맵구조를 넓혀나간다. 위 알고리즘에서 2번째 조건(만약 인접칸에 이미 방이 만들어져있다면 방을 만들지 않는다)은 맵구조에 순환이 생기는것을 막아준다. 

 

위 과정을 모두 완료한후에 목표로 설정한 방에 갯수가 만들어졌는지, 보스방과 시작방이 멀리 떨어져있는지에 대해 검사하고 그렇지 않다면 평면도를 다시만든다. 보스방을 어떻게 결정하는지는 아래에서 설명한다.

특별방

보스방은 막다른방배열에 마지막 원소에 지정된다. 맵구조는 너비우선탐색방식으로 넓어지기 때문에 막다른방배열에 마지막 원소는 시작방에서 가장멀리 떨어져있는 방을 의미한다.

 

나머지 특별방들은 막다른방중 아무대나 만들면되지만 초반에 언급한 상점방, 보상방은 항상존재해야한다. 하지만 이것은 아이작에서의 경우고 본인이 만들게임에는 본인의 룰을 적용하면된다.

 

아래 GIF는 위 규칙들을 적용하여 만든 던전구조의 결과물이다. 툴은 유니티를 사용했다. 시작방을 기준으로 특별방들이 어디에 생성되는지 보시기 바란다.

위 글은 아래 링크의 내용을 번역 및 정리한것이고, 아이작에서 적용되는 디테일한 규칙/알고리즘을 더 알고싶으면 아래 링크를 참조하십시오.

 

Dungeon Generation in Binding of Isaac