GODRICH
#cssアニメーション#ボタン#ローディング#トランジション#スクロール#ダッシュボード#実用ui#デザイントレンド

迷路 ゲーム 9種 — 壁を払い、波紋で道を探す盤

· Godrich · 9種 · 20分で読める

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

自動再生 · タイルを押すとその項目へ · すべて1つの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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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枚をシードで混ぜて前から一枚ずつ調べ、両側のマスが属する島の代表が違えば壁を払って小さい島を大きい島の代表の下につなぎ、代表が同じなら壁を残します（壁リストのシャッフルと島の結合、union-find）。代表を探すときに通ったマスをすべて代表へ直接つなぎ直す経路圧縮と、大きさを見て結合する工夫を併用しているので島が一列に細長く伸びず、払った壁の位置には360ms（MERGE_FLASH_MS）のあいだ広がりながら薄れる光の円が灯ります。シード464では1,738回目の検査で島がひとつにまとまって後ろの122枚は一枚も払われず、計測値は累積面積25.4%・強度43.1・23/23フレームです。

混ぜた壁のリストから一枚ずつ払い、島がひとつに結合する迷路
新しいタブで開く

03 · 混ぜた壁のリストから一枚ずつ払い、島がひとつに結合する迷路 — 計測 累積面積 25.362% · 動いたフレーム 23/23GODRICH オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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 オリジナル · SCSS と React は zip に同梱 · パスワードを見る

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にとどまり、道が短いうえに行き止まりも三つの中で最も少なくなり、Enterか「選び方を変える」で三つの方式を順に回せます。

01の歩く間隔が変えるのは完成までの時間だけです

CARVE_STEP_MSを24から8に下げると、1,921歩が46,104msから15,368ms、つまり約46.1秒から15.4秒に縮みます。壁を選ぶ乱数は奥へ掘り進む一歩でだけ引かれ、時間とは無関係なので、同じシードなら同じ迷路が3倍速く仕上がるだけです。一度に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は残す割合ひとつで左手の歩数がちょうど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分の1です）。0.6では左手が209歩なのに右手は451歩で、同じ盤でもどちらの手で壁をたどるかによって2倍以上開きます。一回の走査には5,766msかかります。

再帰の深さからタブの復帰まで — 迷路の盤が壊れる八つの場所

ここに並べたのは、ソースの式を計算し直すか、計測スクリプトで関数を呼び出して確かめた内容です。端末ごとに一フレームがどれだけかかるかは測っていません。

再帰で掘るとスタックの深さがそのまま呼び出しの深さになります

01のスタックはシード464で499マスまで深くなります。この歩きを再帰関数で書くと同じ数だけ呼び出しが積み重なり、盤を大きくするほど深さも増えて、呼び出しスタックの上限に届くおそれがあります。ソースがマスの番号をInt32Arrayのスタックに出し入れするループで回っているのはそのためです。

マスを増やすと歩数はマス数×2−1で伸びます

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の固定ステップも一フレームに6回までしか回らないので、隠れていたあいだの歩数を一気に取り戻そうとせず、止まった場所から歩きを再開します。

手元でシードや選び方を書き換えて迷路を掘り直してみるなら、圧縮ファイルを開くパスワードは yh7mecs5 です。盤ごとにindex.htmlとstyle.scssが一組ずつ入っていて、同じ計算を移したReactのコンポーネントも同梱しています。

三つの値を掘り直す、そして道さがし盤のアクセシビリティ

名前 値 手触り
掘る速さを変える 01 CARVE_STEP_MS 24 → 8 1,921歩の完成が約46.1秒から15.4秒へ3倍速くなり、シードが同じなので迷路の形は変わりません。
推定距離の傾きを変える 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歩なので、フレームを待たずに一度の計算で回しきれます。

格子の上で道を探す別の場面としては、ヘビが経路探索で自分で動くcss snake game の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ひとつで判定します。

解凍パスワードを入力してください

パスワードはこの記事の本文の中にあります。読み進めると出てきます。