binary-tree-algorithm.md
Binary Tree Algorithm
이 알고리즘은 방마다 오른쪽 혹은 아래쪽을 뚫어서 미로를 만드는 알고리즘이다.
그리드
미로를 만들기 위해 먼저 그리드 모양의 맵을 만든다. 미로는 반드시 홀수 x 홀수 크기여야 한다. 짝수로 하게 된다면, 마지막 줄이 벽으로 막히지 않고 방이 테두리에 그대로 드러난다.
public enum TileType
{
Empty,
Wall,
}
class Board
{
public TileType[,] Tile { get; private set; }
public int Size { get; private set; }
public void Initialize(int size)
{
Tile = new TileType[size, size];
Size = size;
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
{
Tile[y, x] = TileType.Wall;
}
else
{
Tile[y, x] = TileType.Empty;
}
}
}
}
}
Tile[y, x] 가 Wall 이면 벽이고 Empty 면 지나갈 수 있는 칸이다. x 나 y 중 하나라도 짝수면 벽이 되므로, 둘 다 홀수인 칸만 방으로 설정된다. x 가 커질수록 오른쪽, y 가 커질수록 아래쪽이다. Tile[1, 1] 이 왼쪽 위 구석의 방이다.
벽 뚫기
방을 하나씩 돌면서 랜덤으로 오른쪽 혹은 아래쪽 벽을 뚫는다. x 나 y 가 짝수인 칸은 벽이므로 건너뛴다.
private void GenerateBinaryTree()
{
Random rand = new Random();
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (x % 2 == 0 || y % 2 == 0) // current is wall. skip.
{
continue;
}
// dig the right side.
if (rand.Next(0, 2) == 0)
{
Tile[y, x + 1] = TileType.Empty;
}
// dig the bottom.
else
{
Tile[y + 1, x] = TileType.Empty;
}
}
}
}
가장자리
위와 같이 모든 방에서 벽 뚫기를 시도하면, 맨 오른쪽 줄의 방 또는 맨 아랫줄의 방이 뚫려 미로 바깥과 이어진다. 가장자리에 있는 방들은 뚫을 방향을 정해 둬야 한다. Size 가 25라면 마지막 칸 번호는 24이고 그 칸은 테두리 벽이다. 마지막 방의 번호는 Size - 2 인 23이다.
- 맨 아랫줄
y == Size - 2의 방은 오른쪽만 뚫는다. - 맨 오른쪽 줄
x == Size - 2의 방은 아래쪽만 뚫는다. - 오른쪽 아래 구석
(Size - 2, Size - 2)의 방은 어느 쪽도 뚫지 않는다.
private void GenerateBinaryTree()
{
Random rand = new Random();
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (x % 2 == 0 || y % 2 == 0) // current is wall. skip.
{
continue;
}
if (y == Size - 2 && x == Size - 2) // current is destination. skip.
{
continue;
}
if (y == Size - 2) // dig only the right side
{
Tile[y, x + 1] = TileType.Empty;
continue;
}
if (x == Size - 2) // dig only the bottom
{
Tile[y + 1, x] = TileType.Empty;
continue;
}
if (rand.Next(0, 2) == 0)
{
Tile[y, x + 1] = TileType.Empty;
}
else
{
Tile[y + 1, x] = TileType.Empty;
}
}
}
}
맵을 만든 뒤에 GenerateBinaryTree 함수를 호출한다.
public void Initialize(int size)
{
Tile = new TileType[size, size];
Size = size;
// ... fill walls
GenerateBinaryTree();
}
출력
private const char SQUARE = '■';
public void Render()
{
ConsoleColor origin = Console.ForegroundColor;
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
Console.ForegroundColor = Tile[y, x] == TileType.Wall ? ConsoleColor.Green : ConsoleColor.DarkGray;
Console.Write($"{SQUARE} ");
}
Console.WriteLine();
}
Console.ForegroundColor = origin;
}
Board board = new Board();
board.Initialize(25);
board.Render();
특징
- 방마다 벽을 하나씩만 뚫기 때문에, 출발지부터 도착지까지의 경로가 하나뿐이다.
- 도착지에서 뻗어 나가는 두 가장자리는 항상 일직선 통로가 된다.
- 모든 방이 오른쪽 혹은 아래쪽으로만 뚫리기 때문에, 해답 경로가 단순하다.