미로 생성 알고리즘(3) Recursive_Backtracking

이전 두 알고리즘 모두 간단하고 빠르게 구현이 가능한 알고리즘이였지만 알고리즘 자체의 한계로 미로가 편향적이고
일직선으로 뻥 뚫린 부분이 많았습니다.
그런 아쉬운 부분들을 조금 보안해줄 수 있는 새로운 알고리즘은 Recursive_Backtracking
알고리즘에 대해 알아보겠습니다.
Recursive_Backtracking 또한 구현과 이해가 쉬운 알고리즘 입니다.
이전 알고리즘들에 비해 메모리 효율은 아쉬운 단점이 있습니다. 이는 알고리즘 설명과 함께 이어 나가겠습니다.
지난번 두 알고리즘처럼 왼쪽 위를 시작점으로 잡고 그림을 통해 알고리즘 로직을 살펴봅시다.
(시작점이 어디든 상관은 없습니다)

먼저 시작 셀을 현재 셀로 저장합니다
(현재 셀은 파란색 셀 입니다.)
현재 셀의 이웃한 셀들중 하나를 랜덤으로 선택합니다.
랜덤으로 선택할 때 이미 방문한 적 있는 셀이 아닌 경우에만
선택할 수 있습니다.
랜덤으로 아래쪽 셀이 선택되었다고 가정해봅니다.
다음으로 현재 셀을 스택에 push합니다.
(push된 셀은 연한 회색 셀 입니다)

현재 셀과 랜덤으로 선택된 셀 사이의 벽을 뚫고 선택된 셀을 현재 셀로 새롭게 갱신해줍니다.

그리고 위 과정을 반복해줍니다.

과정을 반복하다 보면 다음과 같이 현재 셀의 이웃한 모든 셀이 이미 방문한 상태인 경우가 생깁니다.

이제 이 알고리즘의 이름이 왜 Recursive_Backtracking인지 알수 있습니다.
위의 반복에서 지금까지 방문한 거쳐온 셀들은 모두 스택에 푸시해왔습니다.
그로 인해 스택에는 미로를 생성하며 지나온 셀들의 정보가 순서대로 남아있습니다.
그러므로 지나온 셀들을 다시 뒤돌아가며 아직 방문하지 않은 셀을 찾을 수 있습니다.

그리고 뒤돌아온 길은 막다른 길임을 알기 때문에 다시 한번 갈 필요가 없습니다.
그러기 위해 되돌아 가면서 방문하는 셀을 스택에서 pop해주어 갱신해줍니다.
아래 그림을 보신다면 이해가 더 쉬울 것 입니다.
(pop 된 셀은 하얀색 입니다.)

아래 사진은 제가 만든 프로그램에서 20x20 크기의 미로를 Recursive_Backtracking으로 생성한 결과입니다.

구현 코드

void cMaze::MazeGenerator_RecursiveBacktracking() { //다음 타일 랜덤 선정(checkNeighborTiles) curTile->bIsVisited = true; cTile * nextTile = this->checkNeighborTiles(*curTile); if (visitedCellCount < mMazeWidth * mMazeHeight) { if (nextTile != nullptr) { nextTile->bIsVisited = true; //stack push tileStack.push(curTile); //벽 제거 OpenWall(curTile, nextTile); //현재 타일 갱신 curTile = nextTile; //알고리즘 종료 여부 확인을 위한 카운트 visitedCellCount++; } else if (!tileStack.empty()) { curTile = tileStack.top(); tileStack.pop(); } } this->Render(); curTile->drawCurrentTileRect(); }

이전 포스팅
1 - Binary Tree
https://developer-kua.tistory.com/25

미로 생성 알고리즘(1) Binary Tree

2 - Sidewinder
https://developer-kua.tistory.com/26

미로 생성 알고리즘(2) SideWinder