1. [Unreal 5 / C++] 2D 절차적 맵 생성 알고리즘 (미로 생성 알고리즘)

절차적 맵 생성

아이작과 같은 로그라이크류 게임에서 새로운 맵을 랜덤으로 생성할 때 특정한 알고리즘을 사용하여 자동으로 맵을 생성하는 알고리즘들을 지칭한다. 여러 맵 생성 알고리즘들이 구글에 널려있지만 정확하게 아이작의 구속의 맵 생성 시스템과 비슷한 결과는 없는 것 같아서 본인이 직접 고심하여 알고리즘을 제작해보았다.

아이작에서의 맵 생성 방식

아이작이 워낙 유명한 게임이다 보니까 모작등을 통해 여러 블로그에서 아이작의 맵 생성 방식을 흉내내는 글이 많았다. 하지만 본인이 원하는 아이작에서 비밀방을 제외한 맵 생성 알고리즘과 정확히 일치하는 알고리즘은 찾지 못하였다. 물론 아이작의 맵생성 알고리즘이 오픈되어 있지 않으니 경험을 토대로 역산할 수 밖에 없는 까닭도 있지만, 최대한 비슷한 결과를 만들기 위해 직접 알고리즘을 제작하였다.

아이작 맵 생성 로직

아이작 맵 성성 로직을 분석한 유튜브를 보면 연결되어 있는 방이 1개인 EndRoom을 기준으로 맵들이 연결되어 있고 EndRoom에 황금방, 보스방과 같은 특수한 방들이 들어간다는 것을 알 수 있다.

---

Solution 1 : 백트래킹 + BFS

우선 가장 먼저 생각했던 방법은 백트래킹으로 EndRoom의 입구 방향을 정하고 방향에 대한 모든 경우의 수를 탐색하여 모든 노드끼리 연결되는 경우의 수를 찾는 방법이었다.

 

1. EndRoom의 위치를 EndRoomCount 만큼 EndRoom끼리 이웃하지 않게 랜덤으로 생성을 한다.

EndRoom 랜덤 생성(MapSize = 6, EndRoom = 4)

2. EndRoom을 기준으로 백트래킹으로 EndRoom의 입구 방향의 모든 경우의 수를 탐색한다. 이때 EndRoom의 입구가 정해지면 EndRoom과 인접한 나머지 노드들은 경로에서 제외한다.

EndRoom이 연결되는 모든 경우의 수

3. 백트래킹으로 EndRoom의 방향이 정해질때마다 EndRoom을 BFS를 사용하여 최단 거리로 연결을 한다. 

연결이 가능한 경우(왼쪽), 연결이 불가능한 경우(오른쪽)

4. 백트래킹으로 찾은 EndRoom간 연결이 가능한 경우에서 거리가 가장 짧은 경우를 맵으로 사용한다.

EndRoom간의 연결이 가장 짧은 경우의 수

---

이 방식의 시간복잡도를 계산해보면 $M = EndRoom, N = MapSize$ 일 때 $O(4^M \cdot M \cdot N^2)$ 이다. 

충분히 원하는 결과를 도출하긴 하지만 MapSize나 EndRoom 개수가 조금만 커져도 시간 복잡도가 기하급수적으로 커지게 된다 (MapSize가 10, EndRoom이 10일 때 대략 10억).

 

따라서 충분히 큰 MapSize 과 EndRoom 에서도 위와 유사한 결과를 내는 다른 방법을 찾아야 했고 찾은 2번째 방법을 다음 게시글에서 다루도록 하겠다.