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

서론

이전 시간에 백 트래킹과 BFS를 사용하여 무려 $O(4^M \cdot M \cdot N^2)$ 이 걸리는 맵 생성 알고리즘을 설명하였다. 이번시간에는 이를 대략 $O(M^2 \cdot N^2)$ 정도로 획기적으로 단축하는 방법을 설명하고자 한다. 기존 방식은 N(=MapSize)과 M(=EndRoom)이 각각 10이라면 대략 10억의 계산량이 발생하지만 새로 고안한 방법은 고작 10000의 계산량 밖에 발생하지 않는다 단순 수치로 보면 대략 100000배 빨라졌으니 이전 방식이 얼마나 비효율적인지 알 수 있다.

---

Solution 2 : Kruskal + BFS

이전에는 EndRoom의 개수만큼 Grid에 랜덤으로 방을 생성하여 해당 점의 방향의 모든 경우의 수를 백트래킹으로 찾아 맵을 생성하였다. 이번에는 방식을 바꿔 EndRoom의 개수만큼 방을 생성하고 방들을 크루스칼 알고리즘을 사용하여 스패닝 트리를 계산하여 연결된 방들 간의 경로 방을 생성하고, 부족한 EndRoom의 개수만큼 경로방에서 추가로 EndRoom을 생성하는 방식으로 바꾸었다.

 

1. EndRoomCount 만큼 EndRoom끼리 이웃하지 않게 3 * 3의 Division으로 구역을 나눠 구역안에서 랜덤으로 EndRoom 후보가 생성되도록 한다.

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

2. Kuskal 알고리즘을 사용 하여 EndRoom 후보 간의 최소 스패닝 트리를 생성한다.

3. 스패닝 트리의 경로(간선)을 일반방으로 할당하고 더이상 EndRoom의 조건을 만족하지 않는 EndRoom 후보를 일반방으로 변경한다. 그 다음 부족한 EndRoom의 개수 만큼 일반방에서 EndRoom을 생성 할 수 있는 방을 랜덤으로 선택해 EndRoom을 추가해 준다.

해당 방식으로 Grid 크기가 100, EndRoom 개수가 100으로 설정하여도 충분한 시간에 맵을 생성할 수 있다.

---

절차적 맵 생성을 프로젝트에 적용해 생성한 Map

+ 개선사항 Prim 알고리즘

 최소 스패닝 트리를 구하는 다른 알고리즘으로 Prim 알고리즘이 존재한다. 본인이 최소 스패닝트리를 배울때 제일 처음 접한 알고리즘이 Kruskal이고 "어처피 같은 결과인데 하나만 알아도 되겠지?" 라는 생각에 Kruskal 알고리즘만 공부를 했었기에 해당 알고리즘을 적용하였지만, 모든 EndRoom간에 간선이 존재한다고 가정하기 때문에 간선이 많은 그래프에서는 Prim 알고리즘이 더욱 빠르다고 한다.