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

예전에 다양한 알고리즘들 중 미로 생성 알고리즘이 떠올라 몇 가지 알고리즘들을 알아보고 개발해보았습니다.

window API를 활용해 진행하였고, 참고했던 자료와 알고리즘 자체가 쉬웠던지라 오랜만에 쓴 API 프레임 워크 수정 외에는 막힘은 없었습니다.

참고로 알고리즘들은 모두 아래 사이트에서 참고하였습니다.
http://www.jamisbuck.org/mazes/

Maze Algorithms

---

전체 코드는 깃허브 링크에 올려두었습니다. 참고 바랍니다.

github
https://github.com/DeveloperKua/Algorithm_Datastructure/tree/master/Algorithm/Maze%20Generator_API

DeveloperKua/Algorithm_Datastructure

알고리즘 구현 코드
MazeGenerator/maze Source/MazeGenerator.cpp
MazeGenerator/maze Source/MazeGenerator.h

실행 로직 코드
MazeGenerator/System.cpp

---

우선 간단한 미로를 그리기 위해 Window API를 활용해 제작하였습니다.
이 글을 보시고 만드시는 여러분들은 unity나 cocos등 편하신 툴/엔진들로 진행하셔도 좋습니다.
혹여나 Window API로 제작된 코드를 참고하시고 싶으시다면 부족한 코드지만 위에 깃허브 링크를 참고해주세요.

첫번째로 만든 알고리즘은 Binary Tree &  Sidewinder 알고리즘 입니다.
두 알고리즘 모두 매우 간단한 알고리즘입니다.

Binary Tree의 로직은 다음과 같습니다.

다음과 같이 모든 벽이 막힌 미로를 기준으로

원하는 셀에서 시작하여 랜덤하게 오른쪽 또는 아래(위 또는 왼쪽도 좋습니다.)
의 벽을 뚫어줍니다.

전 왼쪽 위에서 시작하겠습니다.
랜덤하게 오른쪽 벽을 뚫었습니다. 이제 오른쪽 2번째 셀도 랜덤하게 벽을 뚫어줍니다.
2번째 셀은 아래로 벽을 뚫어줍시다.

이런 식으로 계속해서 반복해줍니다.
그리고 맨 오른쪽에 도달하면 더이상 오른쪽으로 벽을 뚫을 순 없으므로
아래로 벽을 뚫어주게 됩니다.

이제 맨 위쪽 셀들은 전부 생성이 완료되었고 아래 셀들의 왼쪽부터 다시 시작합니다.

그리고 이를 계속 반복합니다.

이제 마지막 줄을 제외한 모든 셀들이 생성에 성공하였습니다.
아까전 맨 오른쪽 셀들이 더이상 오른쪽으로 벽을 뚫을 수 없어 강제로 
아래를 향해 벽을 뚫었듯이
마지막 줄의 셀들도 아래로 벽을 뚫을 수 없기에 강제로 오른쪽을 향해 벽을 뚫습니다.

또한 맨 마지막 셀(오른쪽 아래)는 아래도 오른쪽도 뚫지 않습니다.
이렇게 모든 셀들마다 두 방향중 한 방향을 랜덤하게 지정하여 벽을 뚫어가는
알고리즘이 Binary Tree 알고리즘이라 합니다.

매우 간단하고 쉽지만 여러분들도 보시면 알다시피 최하단과 좌측 셀들은 한 방향으로만
벽을 뚫기에 뭔가 밋밋한 미로가 완성 됩니다. 또한 미로가 커지면 커질수록 오른쪽 또는 아래만
뚫어 진행하였기에 전체적인 미로가 굉장히 오른쪽 아래로 편향적인 모습을 하게 됩니다.

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

 

이론은 여기에서 마치고 구현 코드를 살펴보겠습니다.

void cMaze::MazeGenerator_BinaryTree()
{
	//간단히 이중 for문을 사용해 모든 셀들에 컨택하여 미로 생성
	for (int y = 0; y < mMazeHeight; y++)
	{
		for (int x = 0; x < mMazeWidth; x++)
		{
        		//현재 셀이 우측 최하단 이라면(즉 마지막 셀) 스킵
			if (y == mMazeHeight - 1 && x == mMazeWidth - 1)
				continue;
			//현재 셀이 맨 아래 셀들이라면 오른쪽으로 벽 뚫기
			if (y == mMazeHeight - 1) {
				OpenWall(RIGHT, x, y);
				continue;
			}
			//현재 셀이 맨 오른쪽 셀들이라면 아래쪽으로 벽 뚫기
			if (x == mMazeWidth - 1) {
				OpenWall(BOTTOM, x, y);
				continue;
			}

			//별다른 특이사항인 셀이 아니면 오른쪽 또는 아래 벽 랜덤 뚫기
			if (GetRandom(0, 1) == 0)
				OpenWall(RIGHT, x, y);
			else
				OpenWall(BOTTOM, x, y);
		}
	}
}

별도의 멤버나 함수 설명은 다음과 같습니다.
cMaze - 미로 클래스
mMazeHeight - 미로 높이
mMazeWidth  - 미로 넓이

OpenWall() 미로의 벽 뚫는 함수
GetRandom() 랜덤한 값을 뽑아오는 함수

좀 더 자세한 코드는 상단의 github 링크를 참고해주세요.
대신 github 코드는 시각적인 렌더링을 위해 실제 코드는 조금 수정되어있습니다.

 

다음 포스팅

2 - Binary TreeSideWinder
https://developer-kua.tistory.com/26

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

3 - Binary TreeRecursive_Backtracking
https://developer-kua.tistory.com/27

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