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

Sidewinder 알고리즘은 지난번 Binary Tree와 비슷한 부분이 많습니다.
구현도 쉽고 빠르며 로직도 조금 유사하죠.

그림과 함께 sidewinder의 진행 과정을 살펴봅시다.

이번에도 왼쪽 위 (0,0)에서 시작합니다.

이제 현재 셀을 기준으로 오른쪽 또는 위로 뚫을지 랜덤 하게 지정합니다.
허나 현재 셀이 맨 위인지라 위를 뚫으면 안되므로 첫 번째 행은 전부 오른쪽으로 뚫어줍니다.

이제 현재 행의 왼쪽부터 오른쪽으로 뚫을지 말지를
랜덤 하게 정해줍니다.

오른쪽으로 뚫었다면 뚫은 셀을 기억하고 있어야 합니다.

랜덤 하게 정해진 값이 오른쪽으로 뚫지 않게 되면 위에서 기억하고 있는
셀들 중 하나를 지정해 위로 뚫어줍니다.

만약 현재 행에서 오른쪽으로 연속적으로 뚫어 총 3칸이 뚫렸다 했을 때

현재 어두운 회색의 셀들 중 랜덤한 하나의 셀 위쪽을 뚫어줍니다.

위 작업을 반복해줍니다.

반복 도중 만약 마지막 열에 도달하면 더 이상 오른쪽으로
뚫을 수 없으므로 위로 뚫어주어 한 행을 마무리합니다.

남은 행도 이와 같이 반복해줍니다.

마지막 행까지 반복을 완료하면 미로 생성 완료입니다.

지난번 Binary Tree처럼 쉽고 간단하며
더군다나 완성된 미로가 덜 편향적이고 각 마지막 행,열 둘 다 일자로
뚫지 않고 이번엔 첫 행만 일자로 뚫려 있어 조금 더 나은 미로가 완성되었습니다.

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

 

이제 구현 코드를 살펴보겠습니다.

void cMaze::MazeGenerator_SideWinder()
{
	for (int y = 0; y < mMazeHeight; y++)
	{
		int count = 0;//뚫은 셀들을 기억하기 위한 카운트 변수
		for (int x = 0; x < mMazeWidth; x++)
		{
			//맨 위 행 처리
			if (y == 0) {
				if(x == mMazeWidth - 1) continue;
				OpenWall(RIGHT, x, y);
				continue;
			}
			//현재 열이 맨 마지막이거나 오른쪽으로 뚫지 않게 될 경우
			if (GetRandom(0, 1) == 0 || x + 1 == mMazeWidth) {
				//현재 기억하고 있는 뚫은 셀들 중 하나를 랜덤으로 지정
				int RandomX = GetRandom(x - count, x);
				count = 0;
				OpenWall(TOP, RandomX, y);
			}
			//오른쪽으로 뚫기
			else if(x + 1 < mMazeWidth){
				OpenWall(RIGHT, x, y);
				++count;
			}
		}
	}
}

 

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

 

이전 포스팅

1 - Binary Tree
https://developer-kua.tistory.com/25

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

다음 포스팅

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

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