GODRICH
#css애니메이션#버튼#로딩#전환효과#스크롤#대시보드#실전ui#디자인트렌드

미로 게임 만들기 9단계 — 벽 걷기·물결 자국·최단 거리 계산

· Godrich · 9종 · 22분 읽기

game바닐라 JSSCSS자동 재생게임 · 놀이포트폴리오

미로 게임 만들기는 미로를 그리는 일이 아니라 벽을 걷어내는 일이다 — 02번은 무작위 프론티어가 남긴 물결 띠에서 파낸 순서를 읽고, 06번은 A 열린 목록이 출구 쪽으로 뻗는 모습을 보여 주며, 07번은 왼쪽 벽을 짚는 규칙 세 개만으로 출구에 닿는다.

아홉 개의 미로를 이 화면에서 파고 나가 본다

깊이 우선으로 파고 들어갔다 막히면 되돌아와 갈래를 파는 격자 미로01 mz-grid-dfs-carve-passage 프론티어가 물결 모양으로 바깥으로 번지며 자라나는 미로02 mz-frontier-ripple-growth 섞어 놓은 벽 목록에서 하나씩 걷으며 섬이 하나로 합쳐지는 미로03 mz-wall-shuffle-merge-islands 막다른 골목을 다시 이어 여러 갈래 길을 남기는 미로04 mz-braid-open-loop-deadend 입구에서 번지는 파도가 모든 칸까지의 거리를 계산해 남기는 미로05 mz-distance-bfs-flood-heat 목표까지의 추정 거리가 가장 작은 칸부터 열어 나가는 길 찾기06 mz-astar-open-set-greedy-trace 왼쪽 벽에 손을 댄 채 규칙 세 개만으로 출구를 찾는 걷기07 mz-left-hand-wall-follower 거리 값을 온도 색으로 바꿔 정답 경로가 골짜기로 드러나는 판08 mz-solution-thermo-reveal-path 울타리 정원 미로를 내려다보며 안개는 중심 거리로, 그림자는 높이와 해 방향으로 계산하는 장면09 mz-hero-hedge-garden-scene

자동 재생 · 눌러서 해당 항목으로 · 전부 한 zip

미로 게임 만들기 9단계 — 벽 걷기·물결 자국·최단 거리로 만드는 길 찾기 판

아홉 판은 미로 한 장이 태어나서 풀리기까지를 순서대로 나눈 것이다. 01~03 은 벽을 걷는 세 가지 방식으로 미로를 만들고, 04 는 다 만든 미로의 막다른 골목을 다시 이어 고치며, 05~08 은 만들어진 미로를 네 가지 방식으로 풀고, 09 는 그 결과를 울타리 정원 한 장면으로 세운다. 판은 아홉 개 모두 <canvas> 2D 하나에 그려지고, 스타일시트는 무대 크기와 버튼, 포커스 테두리만 맡는다. 움직임을 만드는 @keyframes 는 없고 전부 requestAnimationFrame 스크립트가 돌린다.

칸 하나에 벽 네 장을 비트로 담는다

칸마다 북 1·동 2·남 4·서 8 의 비트를 하나씩 배정하고, 모든 칸은 벽 네 장이 다 선 값 15(ALL_WALLS)에서 출발해 벽을 걷을 때마다 해당 비트를 지운다. knock 은 벽 한 장을 지울 때 건너편 칸의 마주 보는 비트도 같이 지워서, 이쪽에선 뚫렸는데 저쪽에선 막힌 벽이 생기지 않는다. 방향 번호는 0 북·1 동·2 남·3 서의 시계 방향이라 지금 방향에 1 을 더하면 오른쪽으로, 3 을 더하면 왼쪽으로 돈 방향이 나온다. 07 의 손 짚기는 이 덧셈 두 개로 돈다.

시드가 같으면 미로도 같다

난수는 32비트 정수를 뒤섞는 makeRng(seed) 한 가지이고 기본 시드는 464, 자동 시연이 다음 판으로 넘어갈 때마다 1씩 오른다. 아홉 index.html 에는 Math.random·Date.now·fetch·localStorage 가 한 줄도 없다. 그래서 이 글에 나오는 막다른 골목 96개, 최단 320칸 같은 수치는 zip 을 열고 시드 464 로 돌리면 같은 값으로 다시 나온다.

아홉 판을 2초 동안 찍어 잰 움직임

캡처 창은 480×300, 2초 동안 24장을 찍어 앞뒤 장을 비교했으므로 움직인 프레임의 분모는 23 이다.

판 누적면적 강도 평균 움직인 프레임
01 깊이 우선 파기 5.2% 105.4 23/23
02 프론티어 물결 16.9% 106.4 23/23
03 섬 합치기 25.4% 43.1 23/23
04 막다른 골목 잇기 19.1% 33.6 23/23
05 거리 파도 열지도 41.1% 122.5 19/23
06 추정 거리 길 찾기 12.8% 55.6 23/23
07 왼손 걷기 4.7% 70.1 23/23
08 돌아가는 거리 골짜기 40.3% 120.3 13/23
09 울타리 정원 28.2% 25.5 23/23

01 과 07 의 면적이 5% 안팎인 건 걸음 하나가 바꾸는 자리가 9px 칸 하나 둘레에 그치기 때문이다. 01 은 24ms 에 한 걸음이라 2초 동안 약 83걸음을 걷고, 스택 안 칸의 분홍은 머리가 한 칸 깊어질 때 e^(−1/72), 곧 약 1.4%씩만 옅어진다. 07 은 16ms 마다 한 걸음이라 2초에 약 125걸음을 걷지만, 지나간 자취는 걸음마다 0.996배여서 한 번에 0.4%씩만 빠진다. 05 와 08 은 파도가 끝까지 번지거나 수위가 다 차면 다음 판으로 넘어가기 전까지 화면이 서 있는 구간이 있어서 23 에 못 미친다.

이 판들이 들어갈 만한 화면

게임의 레벨 지도나 아이들에게 나눠 줄 인쇄용 미로 활동지라면 01 이 바탕이고, 미로가 생겨나는 과정 자체를 로딩 배경으로 보여 주고 싶다면 02 의 물결이 어울린다. 03 은 알고리즘 수업 자료나 기술 글의 그림으로, 04 는 어린이 퍼즐이나 방 탈출 힌트 판처럼 길이 여러 갈래여야 하는 곳에 맞는다. 05 는 난이도 지도, 06 은 경로 안내 데모, 07 은 보드게임 규칙 설명이나 로딩 중 미니게임, 08 은 정답을 공개하는 장면, 09 는 서비스 첫 화면 히어로 영역의 출발점이 된다. 작은 미로 게임 사이트를 직접 꾸린다면 01 로 판을 만들고 07 이나 08 로 풀이를 보여 주는 조합부터 시작할 수 있다.

미로는 왜 벽을 그리는 대신 걷어내는 방식으로 생기는가?

31×31 격자의 안쪽 벽 후보는 2×31×30 = 1,860장이다. 벽이 전부 선 상태에서 「아직 이어지지 않은 두 칸 사이의 벽」만 걷어 나가면, 칸 961개를 하나로 잇는 데 걷히는 벽은 정확히 960장(칸 수 − 1)이고 그 순간 어느 두 칸 사이에도 길이 딱 하나뿐인 완전 미로가 된다. 01·02·03 은 다음 벽을 고르는 방식이 전혀 다른데도 실측에서 셋 다 960장을 걷었고, 남은 벽은 900장으로 같았다. 반대로 빈 판에 벽을 그려 넣으면 어느 방이 갇혔는지, 고리가 생겼는지를 따로 검사해야 하지만, 걷어내는 쪽은 「이미 이어진 두 칸이면 걷지 않는다」는 조건 하나가 그 검사를 대신한다. 그래서 미로 만들기 알고리즘이 저마다 달라 보여도 실제 차이는 「다음에 걷을 벽을 무엇으로 고르는가」 한 가지로 좁혀진다. 04 는 이 조건을 일부러 어겨 고리를 만든다.

01깊이 우선으로 파고 들어갔다 막히면 되돌아와 갈래를 파는 격자 미로

스택 머리 칸에서 아직 파지 않은 이웃 하나를 시드 난수로 골라 그쪽 벽을 걷고 들어가며, 갈 곳이 없으면 스택에서 한 칸을 빼 되돌아간다. 961칸 판은 넣기 960번과 빼기 961번으로 시드와 상관없이 1,921걸음에 끝나고, 스택 안 칸은 머리에서 k칸 아래일수록 e^(−k/72)로 분홍이 옅어지며 막 빠져나온 칸은 연달아 되돌아간 걸음 수에 비례해 하늘색이 짙다. 자동 시연은 640걸음을 미리 걸어 둔 자리(스택 깊이 463)에서 출발하지만 「다시 파기」 를 누르면 0걸음부터 파며, 렌더 수치는 누적면적 5.2%·강도 105.4·23/23 프레임이다.

깊이 우선으로 파고 들어갔다 막히면 되돌아와 갈래를 파는 격자 미로
새 창에서 열기

01 · 깊이 우선으로 파고 들어갔다 막히면 되돌아와 갈래를 파는 격자 미로 — 측정 누적면적 5.212% · 움직인 프레임 23/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

GRID_NCARVE_STEP_MSBACKTRACK_TINT
        const opts = [];
        for (let d = 0; d < 4; d += 1) {
            const n = neighbor(cur, d);
            if (n >= 0 && visited[n] === 0) {
                opts.push(d);
            }
        }
        steps += 1;
        if (opts.length > 0) {
            const n = knock(walls, cur, opts[Math.floor(rnd() * opts.length)]);
            visited[n] = 1;
            stackPos[n] = top;
            stack[top] = n;
            top += 1;
            carved += 1;
            backRun = 0;
            return 0;
        }
        top -= 1;
        stackPos[cur] = -1;
        backRun += 1;
        popRun[cur] = backRun;
        backs += 1;
        return 1;

02프론티어가 물결 모양으로 바깥으로 번지며 자라나는 미로

이미 판 영역에 닿아 있는 칸들을 프론티어 배열에 모아 두고, 그중 하나를 꺼내 판 안쪽 이웃 하나와 벽 한 장으로 이은 다음 그 칸의 새 이웃을 다시 배열에 넣는다. 칸마다 편입 순번을 적어 26칸(RIPPLE_W)씩 한 띠로 칠하는데, 띠 37개마다 가운데 칸에서 떨어진 거리의 평균이 첫 띠 2.1칸에서 마지막 띠 14.4칸으로 커져 가운데에서 퍼져 나간 물결처럼 읽힌다. 가운데 칸에서 8ms 에 한 칸씩 붙여 960칸을 7,680ms 에 채우고, 렌더 수치는 누적면적 16.9%·강도 106.4·23/23 프레임이다.

프론티어가 물결 모양으로 바깥으로 번지며 자라나는 미로
새 창에서 열기

02 · 프론티어가 물결 모양으로 바깥으로 번지며 자라나는 미로 — 측정 누적면적 16.87% · 움직인 프레임 23/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

FRONTIER_PICKRIPPLE_WRING_FADE
        let c = 0;
        if (mode === 'newest') {
            c = g.front.pop();
        }
        else if (mode === 'oldest') {
            c = g.front.shift();
        }
        else {
            const k = Math.floor(g.rnd() * len);
            c = g.front[k];
            g.front[k] = g.front[len - 1];
            g.front.pop();
        }
        g.inFront[c] = 0;
        const links = [];
        for (let d = 0; d < 4; d += 1) {
            const n = neighbor(c, d);
            if (n >= 0 && g.inMaze[n] === 1) {
                links.push(d);
            }
        }
        knock(g.walls, c, links[Math.floor(g.rnd() * links.length)]);

03섞어 놓은 벽 목록에서 하나씩 걷으며 섬이 하나로 합쳐지는 미로

안쪽 벽 1,860장을 시드로 섞어 앞에서부터 한 장씩 검사하고, 양쪽 칸이 속한 섬의 대표가 다르면 벽을 걷어 작은 섬을 큰 섬 대표 밑에 붙이며 대표가 같으면 벽을 남긴다. 대표를 찾을 때 지나온 칸을 모두 대표에 바로 붙이는 경로 압축과 크기 합치기를 함께 써서 섬이 한 줄로 길게 늘어지지 않게 하고, 섬 색은 대표 번호를 6 으로 나눈 나머지로 고른다. 시드 464 에서는 1,738번째 검사에서 섬이 하나로 모여 뒤의 122장은 하나도 걷히지 않으며, 렌더 수치는 누적면적 25.4%·강도 43.1·23/23 프레임이다.

섞어 놓은 벽 목록에서 하나씩 걷으며 섬이 하나로 합쳐지는 미로
새 창에서 열기

03 · 섞어 놓은 벽 목록에서 하나씩 걷으며 섬이 하나로 합쳐지는 미로 — 측정 누적면적 25.362% · 움직인 프레임 23/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

WALL_SHUFFLE_SEEDISLAND_HUE_NMERGE_FLASH_MS
    // 대표 원소 찾기 + 경로 압축 — 올라간 길의 칸들을 모두 대표에 바로 붙여 다음 찾기를 짧게 한다
    function find(i) {
        let r = i;
        while (parent[r] !== r) {
            r = parent[r];
        }
        let c = i;
        while (parent[c] !== r) {
            const nx = parent[c];
            parent[c] = r;
            c = nx;
        }
        return r;
    }

        const code = order[wi];
        wi += 1;
        const a = code >> 1;
        const dir = (code & 1) === 0 ? 1 : 2;
        const b = neighbor(a, dir);
        let ra = find(a);
        let rb = find(b);
        if (ra === rb) {
            skipped += 1;
            return 1;
        }
        knock(walls, a, dir);
        if (size[ra] < size[rb]) {
            const t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;
        size[ra] += size[rb];
        islands -= 1;
        removed += 1;
        flashes.push({ cell: a, dir: dir, age: 0 });
        return 0;

04막다른 골목을 다시 이어 여러 갈래 길을 남기는 미로

완성된 깊이 우선 미로를 0번 칸부터 훑다가 열린 쪽이 하나뿐인 칸을 만나면 BRAID_KEEP 확률로 남기고, 나머지는 끝의 닫힌 벽 하나를 걷어 옆길에 잇는다. 옆 칸도 막다른 골목이면 그쪽 벽을 먼저 골라 두 골목을 한 번에 없애기 때문에, 시드 464 미로의 막다른 골목 96개가 95번의 잇기로 0개가 된다. 기본값 0 에서 입구→출구 거리는 320칸에서 90칸으로 짧아지고, 렌더 수치는 누적면적 19.1%·강도 33.6·23/23 프레임이다.

막다른 골목을 다시 이어 여러 갈래 길을 남기는 미로
새 창에서 열기

04 · 막다른 골목을 다시 이어 여러 갈래 길을 남기는 미로 — 측정 누적면적 19.073% · 움직인 프레임 23/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

BRAID_KEEPDEADEND_SCAN_MSSPLICE_GLOW
    // 막다른 골목 끝의 벽 하나를 걷어 옆길과 잇는다 — 옆 칸도 막다른 골목이면 그쪽을 먼저 골라 두 골목을 한 번에 없앤다
    function spliceAt(walls, i, rnd) {
        const shut = [];
        const dead = [];
        for (let d = 0; d < 4; d += 1) {
            const n = neighbor(i, d);
            if (n < 0 || (walls[i] & BIT[d]) === 0) {
                continue;
            }
            shut.push(d);
            if (isDeadEnd(walls, n)) {
                dead.push(d);
            }
        }
        const pool = dead.length > 0 ? dead : shut;
        if (pool.length === 0) {
            return -1;
        }
        const d = pool[Math.floor(rnd() * pool.length)];
        knock(walls, i, d);
        return d;
    }

05입구에서 번지는 파도가 모든 칸까지의 거리를 계산해 남기는 미로

입구 칸에 0 을 적고, 지금 겹의 칸마다 열린 이웃 가운데 거리가 비어 있는 칸에 거리+1 을 적어 다음 겹을 만드는 일을 20ms 에 한 번씩 되풀이한다. 색은 거리를 「지금 겹」과 60(HEAT_MAX_D) 가운데 큰 값으로 나눠 하늘·민트·복숭아·분홍 눈금에 얹고, 시드 464 판은 66겹(1,320ms)에 961칸 전체에 닿으며 마지막 겹의 칸 932 가 가장 먼 방으로 드러난다. 「가장 먼 방에서」 를 누르면 그 방에서 다시 번져 69겹 끝에 닿는 칸이 가장 긴 길(69칸)의 반대쪽 끝이 되고, 렌더 수치는 누적면적 41.1%·강도 122.5·19/23 프레임이다.

입구에서 번지는 파도가 모든 칸까지의 거리를 계산해 남기는 미로
새 창에서 열기

05 · 입구에서 번지는 파도가 모든 칸까지의 거리를 계산해 남기는 미로 — 측정 누적면적 41.073% · 움직인 프레임 19/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

FLOOD_STEP_MSHEAT_MAX_DRING_ALPHA
        const next = [];
        for (const c of layer) {
            for (let d = 0; d < 4; d += 1) {
                if (!isOpen(walls, c, d)) {
                    continue;
                }
                const n = neighbor(c, d);
                if (dist[n] >= 0) {
                    continue;
                }
                dist[n] = front + 1;
                next.push(n);
            }
        }
        if (next.length === 0) {
            layer = [];
            if (sweep === 2) {
                longest = front;
                longEnd = farCell;
            }
            return;
        }
        front += 1;
        layer = next;
        reached += next.length;

06목표까지의 추정 거리가 가장 작은 칸부터 열어 나가는 길 찾기

최소 힙에서 f(지나온 거리 g + 기울기 K × 출구까지 남은 가로·세로 칸 수)가 가장 작은 칸을 꺼내 닫고, 열린 이웃의 g 가 줄어들면 부모를 이 칸으로 바꿔 힙에 다시 넣는다. 이 판만은 막다른 골목의 40%를 남기고 나머지를 이어 고리를 낸 미로(LOOP_KEEP 0.4)라 출구까지 길이 여럿이고, 출구를 닫는 순간 부모를 거꾸로 짚은 경로를 18ms 에 한 칸씩 긋는다. 시드 464 미로에서 K 1.0 은 264칸을 닫고 최단 90칸 경로를 내며, 렌더 수치는 누적면적 12.8%·강도 55.6·23/23 프레임이다.

목표까지의 추정 거리가 가장 작은 칸부터 열어 나가는 길 찾기
새 창에서 열기

06 · 목표까지의 추정 거리가 가장 작은 칸부터 열어 나가는 길 찾기 — 측정 누적면적 12.835% · 움직인 프레임 23/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

ASTAR_H_KOPEN_TINTTRACE_MS
            for (let d = 0; d < 4; d += 1) {
                if (!isOpen(walls, c, d)) {
                    continue;
                }
                const n = neighbor(c, d);
                if (closed[n] === 1) {
                    continue;
                }
                const ng = g[c] + 1;
                if (ng >= g[n]) {
                    continue;
                }
                g[n] = ng;
                parent[n] = c;
                if (inOpen[n] === 0) {
                    inOpen[n] = 1;
                    openN += 1;
                }
                heapPush(ng + k * hEst(n), n);
            }

07왼쪽 벽에 손을 댄 채 규칙 세 개만으로 출구를 찾는 걷기

왼쪽이 열렸으면 왼쪽으로 돌아 한 칸, 아니고 앞이 열렸으면 곧장 한 칸, 둘 다 막혔으면 제자리에서 오른쪽으로 도는 순서를 16ms 마다 한 번씩 돌린다. 걸음마다 모든 칸의 자취에 0.996 을 곱해(반감 약 173걸음) 오래된 발자국이 흐려지고, 한 번 지난 칸은 민트, 두 번 이상 지난 칸은 라일락으로 칠한다. 시드 464 미로에서 왼손은 1,095걸음(앞으로 810칸·돌기 570번)에 출구에 닿는데, 자동 시연은 420걸음을 미리 걸어 둔 자리에서 이어 가고 「처음부터」 는 0걸음에서 다시 걸으며, 렌더 수치는 누적면적 4.7%·강도 70.1·23/23 프레임이다.

왼쪽 벽에 손을 댄 채 규칙 세 개만으로 출구를 찾는 걷기
새 창에서 열기

07 · 왼쪽 벽에 손을 댄 채 규칙 세 개만으로 출구를 찾는 걷기 — 측정 누적면적 4.677% · 움직인 프레임 23/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

WALK_STEP_MSHAND_SIDETRAIL_FADE
    // 규칙 세 개 — ① 짚은 손 쪽이 열려 있으면 그쪽으로 돌아 한 칸 ② 아니고 앞이 열려 있으면 한 칸 ③ 둘 다 막혔으면 반대쪽으로 제자리 돌기
    function walkStep() {
        if (pos === EXIT) {
            return false;
        }
        const side = hand === 'left' ? (dir + 3) % 4 : (dir + 1) % 4;
        const other = hand === 'left' ? (dir + 1) % 4 : (dir + 3) % 4;
        steps += 1;
        for (let i = 0; i < CELL_N; i += 1) {
            trail[i] *= TRAIL_FADE;
        }
        if (isOpen(walls, pos, side)) {
            dir = side;
            turns += 1;
            moveAhead();
        }
        else if (isOpen(walls, pos, dir)) {
            moveAhead();
        }
        else {
            dir = other;
            turns += 1;
        }
        return true;
    }

08거리 값을 온도 색으로 바꿔 정답 경로가 골짜기로 드러나는 판

입구와 목표 두 곳에서 각각 너비 우선으로 거리를 잰 뒤 칸마다 「입구 거리 + 목표 거리 − 최단 거리」를 구하면 그 칸을 거쳐 갈 때 더 걷는 칸 수가 되고, 최단 경로 위에서는 이 값이 정확히 0 이다. 이 값을 다섯 눈금 온도 색에 얹고 0 에 가까울수록 최대 45%(VALLEY_DEPTH)까지 어둡게 누르며, 수위가 1.5초에 걸쳐 제곱 곡선으로 차오르기 때문에 가장 낮은 띠가 골짜기처럼 먼저 떠오른다. 시드 464 에서 0 인 칸은 321칸으로 320걸음짜리 최단 경로가 지나는 칸 수와 같고(시드 10개 모두 최단 + 1), 렌더 수치는 누적면적 40.3%·강도 120.3·13/23 프레임이다.

거리 값을 온도 색으로 바꿔 정답 경로가 골짜기로 드러나는 판
새 창에서 열기

08 · 거리 값을 온도 색으로 바꿔 정답 경로가 골짜기로 드러나는 판 — 측정 누적면적 40.303% · 움직인 프레임 13/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

THERMO_STOPSVALLEY_DEPTHREVEAL_MS
    // 칸마다 「입구→칸 거리 + 칸→목표 거리 − 최단 거리」 = 그 칸을 거쳐 가면 더 걷는 칸 수. 최단 경로 위는 정확히 0
    function computeField() {
        const ds = bfsDist(walls, ENTRY);
        const dg = bfsDist(walls, goal);
        shortest = ds[goal];
        maxEx = 1;
        floorN = 0;
        for (let i = 0; i < CELL_N; i += 1) {
            excess[i] = ds[i] + dg[i] - shortest;
            if (excess[i] > maxEx) {
                maxEx = excess[i];
            }
            if (excess[i] === 0) {
                floorN += 1;
            }
        }
        revealT = 0;
        holdLeft = 0;
    }

09울타리 정원 미로를 내려다보며 안개는 중심 거리로, 그림자는 높이와 해 방향으로 계산하는 장면

벽 비트를 선분 1,024개(시드 464)로 바꾼 뒤 해 반대쪽으로 민 평행사변형 그림자를 한 경로에 모아 한 번에 칠하고, 그 위에 옆면과 4px(HEDGE_H_PX) 위로 올린 윗면을 그어 울타리를 세운다. 옆면은 가로 울타리가 −sin, 세로 울타리가 −cos 를 따라 해를 마주 볼수록 밝아지고, 안개 짙기 1 − e^(−0.0042·r) 는 판 가장자리 중점에서 0.443, 캔버스 모서리에서 0.695 까지 올라 눈길이 판 가운데로 모인다. 해는 5,712ms 에 한 바퀴를 돌고 등불이 정답 길 321칸을 70ms 에 한 칸씩 따라가며, 렌더 수치는 누적면적 28.2%·강도 25.5·23/23 프레임이다.

울타리 정원 미로를 내려다보며 안개는 중심 거리로, 그림자는 높이와 해 방향으로 계산하는 장면
새 창에서 열기

09 · 울타리 정원 미로를 내려다보며 안개는 중심 거리로, 그림자는 높이와 해 방향으로 계산하는 장면 — 측정 누적면적 28.202% · 움직인 프레임 23/23GODRICH 원작 · zip 에 SCSS·React 포함 · 비밀번호 보기

HEDGE_H_PXFOG_KSHADOW_LEN
        const len = SHADOW_LEN * HEDGE_H_PX;
        const sx = Math.cos(sun) * len;
        const sy = Math.sin(sun) * len;
        // 그림자 — 선분 하나를 해 반대쪽으로 민 평행사변형
        ctx.fillStyle = rgba(BG, 0.24);
        ctx.beginPath();
        for (let s = 0; s < segs.length; s += 4) {
            const x1 = segs[s];
            const y1 = segs[s + 1];
            const x2 = segs[s + 2];
            const y2 = segs[s + 3];
            const nx = y1 === y2 ? 0 : 1.6;
            const ny = y1 === y2 ? 1.6 : 0;
            ctx.moveTo(x1 - nx, y1 - ny);
            ctx.lineTo(x2 + nx, y2 + ny);
            ctx.lineTo(x2 + nx + sx, y2 + ny + sy);
            ctx.lineTo(x1 - nx + sx, y1 - ny + sy);
            ctx.closePath();
        }
        ctx.fill();

걷는 순서·물결 폭·추정 거리 기울기 — 숫자 하나가 길의 생김새를 바꾸는 자리

아래 수치는 측정 스크립트가 각 판의 index.html 함수를 직접 불러 시드를 고정한 채 잰 값이다.

02 는 꺼내는 순서 한 줄로 막다른 골목이 266~326개로 갈린다

같은 시드, 같은 가운데 시작에서 random 은 막다른 골목 326개·가운데에서 가장 먼 칸까지 35칸·입구→출구 62칸이고, newest 는 319개·487칸·426칸, oldest 는 266개·30칸·60칸이다. newest 는 방금 넣은 칸을 곧바로 다시 꺼내므로 깊이 우선처럼 긴 복도가 이어져 가장 먼 칸이 487칸까지 멀어진다. oldest 는 오래 기다린 칸부터 꺼내 가장 먼 칸이 30칸에 그치고, 입구→출구도 60칸으로 셋 중 가장 짧으며 막다른 골목도 가장 적다. Enter 나 「고르는 법 바꾸기」 로 세 방식을 차례로 돌려 볼 수 있다.

01 의 걸음 간격은 완성 시간만 바꾼다

CARVE_STEP_MS 를 24 에서 8 로 내리면 1,921걸음이 46,104ms 에서 15,368ms 로, 약 46.1초에서 15.4초로 줄어든다. 벽을 고르는 난수는 파 들어가는 걸음에서만 뽑히고 시간과는 무관해서, 같은 시드면 같은 미로가 세 배 빠르게 나올 뿐이다. 한 번에 122걸음까지 이어지는 되돌아가기 구간도 같은 비율로 짧아진다(계산값 2,928ms → 976ms).

06 의 기울기를 2.2 로 올리면 닫는 칸이 절반 아래로 준다

시드 464 미로에서 K 1.0 은 264칸, K 2.2 는 126칸을 닫고 경로는 둘 다 90칸이다. 남은 거리를 아예 보지 않는 K 0 은 804칸을 닫는다. 시드 20개로 넓혀 보면 닫는 칸의 평균이 556.85 에서 249.45 로 줄고 20개 모두 줄었지만, K 1.0 이 20개 전부 최단 경로를 낸 반면 K 2.2 는 12개 미로에서 최단보다 긴 길을 내놓았고 가장 크게 벌어진 차이는 14칸이었다.

04 의 남길 비율을 0 으로 내리면 왼손 걷기 걸음이 5분의 1로 준다

시드 464 깊이 우선 미로(막다른 골목 96개)를 비율마다 한 번씩 훑은 결과다.

남길 비율 이은 수 남은 막다른 골목 입구→출구 왼손 걷기 오른손 걷기
0 (기본) 95 0 90 219 253
0.3 69 27 112 251 271
0.6 37 59 112 209 451
1 0 96 320 1,095 1,484

비율 1 은 아무것도 잇지 않은 원래 미로라 왼손 걷기가 1,095걸음이고, 0 이면 219걸음으로 꼭 5분의 1이 된다. 오른손은 같은 두 비율에서 1,484걸음과 253걸음이라 약 5.9배 차이다. 0.6 에서는 왼손이 209걸음인데 오른손은 451걸음이라, 같은 판이라도 어느 손으로 벽을 짚느냐에 따라 두 배 넘게 벌어진다. 한 번 훑는 데는 5,766ms 가 걸린다.

칸이 수천 개일 때·골목이 다시 이어질 때·탭이 멈출 때 깨지는 곳

아래는 소스의 식을 다시 계산하거나 측정 스크립트로 함수를 직접 불러 확인한 내용이다. 기기마다 한 프레임이 얼마나 걸리는지는 재지 않았다.

재귀로 파면 스택 깊이가 호출 깊이가 된다

01 의 스택은 시드 464 에서 499칸까지 깊어진다. 이 걷기를 재귀 함수로 짜면 그만큼 호출이 겹겹이 쌓이고, 판을 키울수록 깊이도 늘어 호출 스택 한도에 닿을 수 있다. 소스가 칸 번호를 Int32Array 스택에 넣고 빼는 반복문으로 도는 이유다.

칸 수를 늘리면 걸음이 칸 수의 두 배로 붙는다

01 의 걸음 수는 칸 수 × 2 − 1 이어서 61×61 판(3,721칸)이면 7,441걸음, 24ms 간격으로 약 178.6초가 걸린다. 이 크기는 직접 돌려 잰 값이 아니라 식으로 낸 계산값이다. 07 도 시드 464 에서 1,095걸음으로 칸 수 961 을 넘었고, 시드 464~473 열 개 사이에서 496걸음부터 1,641걸음까지 벌어졌다. 02 의 oldest 는 Array.shift 로 꺼내 꺼낼 때마다 배열 앞을 당기는데, 이 판의 프론티어는 최대 138칸이라 지금 크기에서는 느려지지 않는다.

골목을 다시 이으면 손 짚기 걷기가 섬을 맴돌 수 있다

04 처럼 고리를 낸 미로에서는 「두 칸 사이 길은 하나」라는 성질이 깨진다. 이 판들은 입구와 출구가 바깥 벽에 붙어 있어서 왼손 걷기가 출구에 닿지만, 출구를 판 안쪽에 두거나 출발 칸이 고리에 둘러싸인 섬 위에 있으면 같은 섬을 끝없이 돈다. 05 가 쓰는 「두 번 번져 가장 긴 길 찾기」도 길이 하나뿐인 미로에서만 성립해서, 04·06 같은 고리 미로에서는 답을 보장하지 않는다.

07 의 민트 칸을 정답 길로 읽으면 틀린다

시드 464 에서 한 번만 지난 민트 칸은 350칸이고, 최단 경로가 지나는 칸은 321칸이다. 막다른 골목 끝 칸은 들어갔다가 제자리에서 두 번 돌아 나오므로 한 번만 지나 민트로 남고, 갈림길 칸은 곁가지를 드나들며 두 번 이상 지나 라일락이 되기도 한다. 정답 길만 따로 칠하려면 08 처럼 두 곳에서 거리를 재야 한다.

06 의 힙은 칸 수보다 커질 수 있다

힙에서 낡은 항목을 지우지 않고 꺼낼 때 닫힘 표시로 건너뛰는 방식이라, g 가 줄어든 칸은 같은 칸이 힙에 여러 번 들어간다. 그래서 힙 배열은 칸 수의 4배로 잡혀 있다. 판을 키우면서 이 배수를 줄이면 힙이 넘칠 수 있다.

같은 색 두 섬이 같은 섬이라는 뜻은 아니다

03 의 섬 색은 대표 번호 % 6 이라, 400번째 검사 직후 남아 있는 섬 561개가 여섯 색을 나눠 쓴다. 맞닿은 두 섬이 같은 색이어도 대표가 다르면 서로 다른 섬이고, 칸을 누르면 1.4초 동안 그 섬 전체를 밝혀 진짜 범위를 보여 준다. 벽 목록을 섞지 않고 만든 순서대로 검사하면 줄마다 같은 방향 벽만 걷혀 긴 가로 복도가 생긴다.

울타리를 높이면 9px 통로가 묻힌다

09 는 칸 한 변이 9px 인 판 위에 울타리 윗면을 HEDGE_H_PX 만큼 끌어올려 긋는다. 높이를 키우면 윗면과 그림자가 통로를 덮어 길이 보이지 않게 된다. 그림자도 선분마다 따로 fill 하면 1,024번을 칠해야 해서, 평행사변형을 한 경로에 모아 한 번만 칠한다.

탭을 가렸다 돌아와도 걸음이 몰려오지 않는다

탭이 숨으면 requestAnimationFrame 이 쉬고, 돌아온 첫 프레임에 더하는 시간은 100ms 에서 잘린다. 16ms 고정 스텝도 한 프레임에 여섯 번까지만 돌기 때문에 숨어 있던 동안의 걸음을 한꺼번에 따라잡지 않고 멈췄던 자리에서 다시 걷는다.

받은 판에서 시드나 고르는 법을 바꿔 직접 다시 파 볼 때 압축을 여는 비밀번호는 yh7mecs5 이다. 판마다 index.html 과 style.scss 한 쌍이 들어 있고, 같은 계산을 옮긴 리액트 컴포넌트도 함께 있다.

걷기 속도·추정 기울기·골목 비율로 다시 파 보기, 그리고 키보드로 푸는 미로 판의 접근성

이름 값 느낌
걷기 속도 바꾸기 01 CARVE_STEP_MS 24 → 8 1,921걸음 완성이 약 46.1초에서 15.4초로 세 배 빨라지고, 같은 시드라 미로 모양은 그대로다.
추정 거리 기울기 바꾸기 06 ASTAR_H_K 1.0 → 2.2 시드 464 에서 닫는 칸이 264 에서 126 으로 줄고 경로는 90칸 그대로, 시드 20개 중 12개에서는 최단보다 긴 답이 나온다.
골목 살리기 비율 바꾸기 04 BRAID_KEEP 0 → 0.6 남는 막다른 골목이 0 에서 59개로 늘고 이은 수는 95 에서 37, 입구→출구는 90 에서 112칸이 된다.

마우스 없이도 아홉 판을 다 다룰 수 있다. 캔버스마다 tabindex="0" 과 판이 무엇을 하는지 적은 한국어 aria-label 이 붙어 있고, 판마다 진짜 <button> 이 두 개씩 있다. 01·03 의 「멈춤」, 07 의 「오른손으로」, 09 의 「해 멈춤」 은 aria-pressed 로 켜짐 상태를 알린다. 키는 01 이 Space 멈춤·→ 20걸음·Home/Enter 처음부터, 02 가 Enter 고르는 법 바꾸기·→ 40칸, 03 이 Space 멈춤·→ 60장, 04 가 ↑·↓ 로 남길 비율, 05 가 Enter 가장 먼 방에서·→ 5겹, 06 이 ↑·↓ 로 기울기와 Enter 다시 풀기, 07 이 Space 멈춤·Enter 손 바꾸기·→ 20걸음, 08 이 방향키로 목표 칸 옮기기, 09 가 ←·→ 로 해를 15° 씩 돌리기다.

판 아래 상태 줄은 자동 시연 동안 aria-live="off" 로 조용히 있다가, 사람이 처음 포인터나 키, 버튼을 건드리는 순간 polite 로 바뀌어 그 뒤의 변화만 읽어 준다. 그래서 화면 읽기 프로그램이 시연의 걸음마다 말을 쏟아 내지 않는다.

prefers-reduced-motion 이 켜져 있으면 아홉 판 모두 프레임 루프를 시작하지 않고 settle() 로 과정을 끝까지 한 번에 돌린 뒤 draw() 를 한 번 부른다. 01~03 은 다 파인 미로, 05 는 다 번진 열지도, 07 은 출구까지 걸은 자취, 08 은 골짜기가 다 드러난 판으로 서 있고, 09 는 해와 등불이 처음 자리에 멈춘 정원이다. 입력은 이 상태에서도 받으며, 누를 때마다 after() 가 곧바로 결과까지 계산해 다시 그린다.

미로 만들기 사이트 없이 브라우저에서 바로 되는가?

된다. 미로를 만들고 푸는 데 필요한 건 칸 배열, 칸마다 벽 비트, 시드 난수, 그리고 스택이나 큐 하나다. 이 편의 판은 라이브러리나 CDN, WebGL 없이 fillRect 와 선 긋기, requestAnimationFrame 만 쓴다. 인쇄할 미로 한 장이 목적이라면 시연 속도와 상관없이 settle() 처럼 끝까지 한 번에 돌린 판을 그리면 되고, 961칸 판의 깊이 우선 파기는 1,921걸음이면 끝난다.

격자 위에서 길을 찾는 다른 장면으로는 같은 너비 우선 거리로 뱀을 자동 조종하는 스네이크 게임 자동 조종 9종 과 점균이 미로의 최단 경로를 찾는 점균 네트워크 시뮬레이션 이 가깝다. 손으로 조작하는 작은 게임을 더 보려면 CSS 미니 게임 모음 으로 이어 가면 된다.

미로 찾기 게임을 내 페이지에 붙이기 전에 자주 나오는 궁금증

미로 게임 사이트에 올릴 판을 더 크게 만들려면 무엇을 바꾸나?

GRID_N 과 칸 크기 CS 를 같이 바꾼다. 판 한 변은 GRID_N × CS 이고 캔버스 내부 좌표가 480×300 이라, 지금의 31×9 = 279px 은 높이 300 안에 들어가도록 맞춘 크기다. 칸을 늘리면 01 의 걸음도 칸 수 × 2 − 1 로 늘어나니 CARVE_STEP_MS 를 함께 줄여야 기다림이 길어지지 않는다.

정답 경로만 뽑아 쓰려면 어느 판을 보면 되나?

09 의 buildSegs() 뒷부분이 가장 간단하다. 입구에서 잰 거리 배열을 들고 출구에서 출발해, 열린 이웃 가운데 거리가 정확히 1 작은 칸으로 옮겨 가기를 입구에 닿을 때까지 되풀이한 뒤 순서를 뒤집는다. 경로 전체가 아니라 「어느 칸이 정답 길 위에 있는가」만 필요하면 08 의 「더 걷는 칸 수가 0 인 칸」 판정이 같은 답을 준다.

방향키로 사람이 직접 걷게 하려면 어디를 고치나?

07 의 walkStep() 이 쓰는 isOpen(walls, pos, dir) 검사를 그대로 쓰면 된다. 규칙 세 개 대신 누른 방향키를 dir 로 넘기고, 열려 있을 때만 moveAhead() 를 부르면 벽을 뚫지 않는 플레이어 이동이 된다. 출구 도착은 지금처럼 pos === EXIT 하나로 판정한다.

압축 비밀번호를 입력하세요

비밀번호는 이 글 본문 안에 있습니다. 읽다 보면 나옵니다.