전체 코드
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithm
{
class Board
{
public enum TileType
{
Empty, // 빈 공간
Wall, // 벽
}
const char CIRCLE = '\u25cf'; // 유니코드 문자로 ● (검은색 원)을 출력하기 위한 상수. 맵 타일을 표시하는 데 사용됨.
public TileType[,] _tile; // 2차원 배열로 맵의 각 타일의 상태를 저장.
public int _size; // 맵의 크기. NxN 크기를 나타냄.
// 맵 초기화 메서드. 맵의 크기를 받아 타일을 생성하고 초기화.
public void Initialize(int size)
{
if (size % 2 == 0)
{
return;
}
_tile = new TileType[size, size]; // 맵의 크기(size x size)만큼의 2차원 배열 생성.
_size = size; // 맵 크기 설정.
//GenrateByBinaryTree();
GenerateBySideWinder();
}
public void GenrateByBinaryTree()
{
// mazes for Programmers
// Binary Tree Algorithm
// 길을 다 막는 작업
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;
}
}
}
// 랜덤으로 우측 혹은 아래로 길을 뚫는 작업
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)
{
continue;
}
if (y == _size - 2 && x == _size - 2)
{
continue;
}
if (y == _size - 2)
{
_tile[y, x + 1] = TileType.Empty;
continue;
}
if (x == _size - 2)
{
_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;
}
}
}
}
// Sidewinder 알고리즘으로 미로를 생성하는 메서드
public void GenerateBySideWinder()
{
// 1. 우선 모든 타일을 벽으로 막고, 홀수 좌표에 빈 공간을 만듦
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
// x 또는 y가 짝수일 경우에는 벽을 설치하고, 나머지에는 빈 공간을 생성
if (x % 2 == 0 || y % 2 == 0)
{
_tile[y, x] = TileType.Wall; // 벽 타일
}
else
{
_tile[y, x] = TileType.Empty; // 빈 공간
}
}
}
// 2. 각 좌표에서 무작위로 오른쪽 또는 아래쪽으로 길을 뚫음
Random rand = new Random(); // 무작위 생성기
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
// 연속된 세로 구역의 길 개수를 세기 위한 변수 (미완성 코드로 보임)
int count = 0;
// 짝수 좌표는 벽이므로 건너뜀
if (x % 2 == 0 || y % 2 == 0)
{
continue;
}
// 미로의 끝 부분에서는 길을 뚫지 않음
if (y == _size - 2 && x == _size - 2)
{
continue;
}
// 마지막 행에서는 오른쪽으로만 길을 뚫음
if (y == _size - 2)
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽으로 길 뚫기
continue;
}
// 마지막 열에서는 아래쪽으로만 길을 뚫음
if (x == _size - 2)
{
_tile[y + 1, x] = TileType.Empty; // 아래로 길 뚫기
continue;
}
// 50% 확률로 오른쪽 또는 아래쪽으로 길을 뚫음
if (rand.Next(0, 2) == 0)
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽으로 길을 뚫음
count++; // 길의 개수 카운트 증가
}
else
{
// 우측으로 길을 뚫지 않은 경우, 아래쪽으로 길을 뚫음
// 특정 구간에서 무작위로 아래쪽으로 길을 뚫음 (아직 완성되지 않은 부분)
int randomIndex = rand.Next(0, count);
_tile[y + 1, x - randomIndex * 2] = TileType.Empty; // 아래로 길을 뚫음
count = 1; // 카운트 초기화
}
}
}
}
// 맵을 화면에 출력하는 메서드.
public void Render()
{
ConsoleColor prevColor = Console.ForegroundColor; // 현재 콘솔의 글자색을 저장.
for (int y = 0; y < _size; y++) // 행 순회.
{
for (int x = 0; x < _size; x++) // 열 순회.
{
Console.ForegroundColor = GetTileColor(_tile[y, x]); // 현재 타일의 색을 설정.
Console.Write(CIRCLE); // ● 문자 출력.
}
Console.WriteLine(); // 한 행이 끝나면 다음 줄로 이동.
}
Console.ForegroundColor = prevColor; // 이전 색상으로 복원.
}
// 타일의 종류에 따라 콘솔 글자색을 반환하는 메서드.
ConsoleColor GetTileColor(TileType type)
{
switch (type)
{
case TileType.Empty:
return ConsoleColor.Green; // 빈 공간은 초록색.
case TileType.Wall:
return ConsoleColor.Red; // 벽은 빨간색.
default:
return ConsoleColor.Green; // 기본값으로 초록색 반환.
}
}
}
}
1. Sidewinder 알고리즘 개요
Sidewinder 알고리즘은 우측 또는 아래 방향으로 무작위로 길을 뚫으며 미로를 생성하는 방식입니다.
🟢 알고리즘 특징
- 각 행(row)에서 한 번에 오른쪽으로 길을 만들다가 랜덤하게 아래쪽으로 연결
- 각 행(row)은 오른쪽 방향으로 확장하면서 무작위로 아래쪽으로 한 개의 연결로 뚫음
- 우측 이동 확률과 아래쪽 연결이 랜덤하게 설정됨
2. 코드 분석
(1) 기본 설정
using System;
using System.Collections.Generic;System네임스페이스를 사용하여 콘솔 입출력을 지원List같은 컬렉션을 사용할 수 있도록System.Collections.Generic포함
namespace Algorithm
{
class Board
{
const char CIRCLE = '\u25cf';
public TileType[,] _tile;
public int _size;Board클래스: 미로 데이터를 관리하는 역할_tile배열: 2차원 배열로 미로를 표현_size: 미로 크기 (정사각형)
(2) 타일 타입 정의
public enum TileType
{
Empty, // 빈 공간
Wall, // 벽
}TileType열거형(enum)으로 빈 공간(Empty)과 벽(Wall)을 구분- 2차원 배열
_tile[,]에서 미로 상태를 저장하는 용도로 사용
3. Sidewinder 알고리즘 구현
(1) 미로 초기화
public void Initialize(int size)
{
if (size % 2 == 0) return; // 크기가 홀수여야 함
_tile = new TileType[size, size];
_size = size;
GenerateBySideWinder(); // Sidewinder 알고리즘으로 미로 생성
}- 미로 크기는 홀수여야 함 (
size % 2 == 0체크) _tile[,]배열을 초기화 후GenerateBySideWinder()호출
(2) 미로 기본 설정 (벽 및 통로 배치)
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; // 홀수 좌표는 빈 공간
}
}- 모든 칸을 벽으로 설정한 후, 홀수 좌표(
x % 2 == 1,y % 2 == 1)만 빈 공간으로 설정 - 이렇게 하면 벽과 빈 공간이 일정한 패턴으로 배치됨
(3) Sidewinder 알고리즘 적용
Random rand = new Random();
for (int y = 0; y < _size; y += 2) // 2칸 단위로 이동 (홀수 행만 처리)
{
List<int> run = new List<int>(); // 우측으로 확장할 경로 저장rand객체를 생성하여 랜덤한 길 뚫기를 수행run리스트는 연속된 오른쪽 길의 그룹을 저장 (아래로 길을 뚫기 위해 필요)y += 2로 홀수 행만 처리 (벽이 있는 행은 제외)
(4) 우측 또는 아래쪽 길 생성
for (int x = 1; x < _size - 1; x += 2) // 2칸 단위로 이동 (홀수 열)
{
_tile[y, x] = TileType.Empty; // 현재 위치를 빈 공간으로 설정
run.Add(x);
bool atEastEdge = (x + 2 >= _size); // 끝 부분인지 확인
bool shouldCloseOut = atEastEdge || (rand.Next(0, 2) == 0);x += 2로 홀수 열만 처리 (벽을 유지하기 위함)- 현재
x, y위치를 빈 공간(Empty)으로 설정 후run리스트에 저장 shouldCloseOut은 우측으로 길을 계속 뚫을지, 아래쪽으로 연결할지 결정- 끝 부분이면(
atEastEdge) 무조건 아래로 뚫음 - 아니면 50% 확률(
rand.Next(0,2))로 아래로 뚫음
- 끝 부분이면(
(5) 아래쪽으로 길 뚫기
if (shouldCloseOut)
{
int randIndex = rand.Next(0, run.Count); // 랜덤한 하나 선택
int randX = run[randIndex]; // 선택한 위치
_tile[y + 1, randX] = TileType.Empty; // 아래쪽으로 길 뚫기
run.Clear(); // 현재 그룹 초기화
}
else
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽으로 길 뚫기
}shouldCloseOut이true이면 run 리스트에서 랜덤한 하나를 선택하여 아래쪽으로 연결false이면 오른쪽으로 길을 계속 확장
4. 미로 렌더링
public void Render()
{
ConsoleColor prevColor = Console.ForegroundColor;
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
Console.ForegroundColor = GetTileColor(_tile[y, x]);
Console.Write(CIRCLE);
}
Console.WriteLine();
}
Console.ForegroundColor = prevColor;
}- 콘솔 화면에 미로를 출력하며 타일 타입에 따라 색상을 다르게 표시
CIRCLE('\u25cf')을 사용하여 미로를 가시화
(1) 타일 색상 반환
ConsoleColor GetTileColor(TileType type)
{
switch (type)
{
case TileType.Empty: return ConsoleColor.Green;
case TileType.Wall: return ConsoleColor.Red;
default: return ConsoleColor.Green;
}
}- 빈 공간(
Empty) → 초록색 (Green) - 벽(
Wall) → 빨간색 (Red)
李家네_공부방