[Maze] 미로 게임 만들기

Gemini 형과 함께 Maze 게임을 만들었다.

1. 게임 해보기
http://www.chobocho.com/game/maze/index.html

Chobocho's 미로 생성기 V0.2

 

2. 미로 생 로직 소개 (Written by Gemini)

🧠 미로를 만드는 핵심 원리: DFS와 백트래킹 이 코드에서 사용할 핵심 기법은 깊이 우선 탐색(DFS, Depth-First Search) 기반의 백트래킹(Backtracking)입니다. 이름은 거창하지만 원리는 아주 단순합니다. 일단 갈 수 있는 방향 중 하나를 무작위로 골라 벽을 부수고 전진합니다. 지나온 길은 '수첩(Stack)'에 기록해 둡니다. 사방이 다 막혀있거나 이미 방문한 곳뿐이라면(막다른 길), 수첩을 보고 직전에 있었던 갈림길로 되돌아갑니다. (이것이 백트래킹!) 수첩에 적힌 모든 기록을 지우고 출발지로 돌아오면 미로 완성! 이제 이 원리가 코드로 어떻게 구현되는지 단계별로 살펴보겠습니다.   💻 코드 파헤치기 1. 꽉 막힌 방들로 이루어진 판 만들기 (초기화) 먼저 미로의 뼈대가 될 격자(grid)를 만듭니다. 처음에는 모든 칸의 사방(상, 하, 좌, 우)에 벽이 쳐져 있는 상태로 시작합니다. 2. 탐험 준비 및 시작 가장 왼쪽 위 [0][0]을 출발점으로 잡고 탐험을 시작합니다.  3. ✨핵심 포인트: 가장 먼 종료 지점 찾기 보통 미로를 만들면 습관적으로 가장 반대편인 우측 하단([size-1][size-1])을 도착점으로 둡니다.  하지만 미로의 길이 꼬불꼬불하다면, 물리적인 거리와 상관없이 실제로 가장 많이 걸어야 하는'가장 난이도가 높은 칸'은 다른 곳일 수 있습니다. 우리는 stack의 길이를 이용해 이 문제를 해결합니다.  탐험 중 stack에 쌓인 데이터의 개수는 곧 '출발지로부터 현재 위치까지 꺾어 들어온 거리'를 의미하기 때문입니다. 4. 무작위로 벽 부수며 전진하기 이제 인접한 칸 중 아직 안 가본 곳(neighbors)을 찾습니다. 갈 곳이 있다면 무작위로 하나를 골라 현재 칸과 다음 칸 사이의 벽(wall, opp)을 모두 false로 만들어 길을 뚫습니다.  갈 곳이 없다면 막다른 길이므로 수첩에서 현재 위치를 지우고(stack.pop()) 뒤로 물러납니다. let neighbors = [];     for (let d of directions) {         let nx = current.x + d.dx;         let ny = current.y + d.dy;         if (nx >= 0 && nx < size && ny >= 0 && ny < size && !grid[ny][nx].visited) {             neighbors.push({cell: grid[ny][nx], dir: d});         }     }     if (neighbors.length > 0) {         // 갈 곳이 있다면 무작위로 벽 부수고 전진         let chosen = neighbors[Math.floor(Math.random() * neighbors.length)];         current[chosen.dir.wall] = false;         chosen.cell[chosen.dir.opp] = false;         chosen.cell.visited = true;         stack.push(chosen.cell);     } else {         // 막다른 길이면 뒤로 되돌아가기         stack.pop();     } } 5. 마무리 및 데이터 반환 수첩(stack)이 텅 비어 while 문이 끝났다는 것은 모든 방을 다 방문하고 다시 출발지로 돌아왔다는 뜻입니다.  이제 아까 기록해 둔 '가장 먼 곳'을 종료 지점(isEnd = true)으로 설정하고 데이터를 반환합니다.

 

3. 소스코드 위치
https://github.com/chobocho/maze_maker

GitHub - chobocho/maze_maker: maze generator