メインコンテンツへスキップ
Z Graph & Pathfinding

迷路ジェネレーター

再帰分割法（recursive division）によるアニメーション付き迷路ジェネレーター — 壁が組み上がっていく過程をステップごとに確認し、速度を調整して、新しい迷路を何度でも生成できます。経路探索アルゴリズムのビジュアライザーと組み合わせて使うのに最適です。すべてブラウザ上で完結します。

無料 登録不要 クライアントサイド プライバシーに配慮 Updated

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!
/

疑似コード

使い方

  1. 1 Generateを押すと、再帰分割アルゴリズムで迷路が組み上がる様子が表示されます。
  2. 2 Stepを使うと壁が1本ずつ追加され、再帰処理の流れを確認できます。
  3. 3 New mazeを押すと、別のランダムな迷路レイアウトが生成されます。
  4. 4 Speedを調整すると壁の生成速度をゆっくりにでき、じっくり観察できます。

このツールを使う理由

  • 再帰分割アルゴリズムが各区画をひとつだけ隙間のある壁で仕切っていく様子を確認できます。
  • 生成される迷路はすべて「完全な迷路」——任意の2マス間の経路がちょうどひとつだけです。
  • 同じ方眼グリッドモデルを使う経路探索アルゴリズムのビジュアライザーと組み合わせるのに最適な相棒ツールです。
  • すべてブラウザ上で完結します。登録もアップロードも不要です。

よくある質問

再帰分割アルゴリズムはどのように迷路を作るのですか？

まず何もない空間から始め、各区画をランダムな位置に隙間を残した1本の直線の壁で再帰的に仕切っていきます。これを区画がそれ以上分割できなくなるまで繰り返します。

「完全な迷路」とは何ですか？

任意の2マス間にちょうどひとつの経路しか存在しない迷路のことです——ループも孤立した領域もありません。再帰分割アルゴリズムは常に完全な迷路を生成します。

この迷路を解くことはできますか？

はい——同じ方眼グリッドを使うBFS、Dijkstra、A*のビジュアライザーにレイアウトをコピーすれば、経路探索アルゴリズムがどのように迷路を進んでいくか確認できます。

他にどんな迷路生成アルゴリズムがありますか？

Recursive backtracker（ランダム化DFS）、Prim法、Kruskal法、Wilson法、Eller法などがあり、それぞれ見た目の異なる構造の迷路が生成されます。

迷路ジェネレーター とは？

迷路ジェネレーターは、再帰分割（recursive division）という手法でランダムな迷路を作り出すツールです。各区画をひとつだけ隙間のある壁で仕切ることを繰り返し、区画がそれ以上分割できないほど小さくなるまで続けます。こうして生成されるのは「完全な迷路」（perfect maze）——任意の2つのマス間に経路がちょうどひとつだけ存在する迷路です。

機能

アニメーション付き生成

アルゴリズムがグリッドを進むにつれて壁が削られていく様子を確認できます。

計算量

O(cells)の時間・空間計算量で、完全迷路(任意の2つのセル間に唯一の経路)を生成します。

100%プライベート

すべての処理はブラウザ内で完結します——何もアップロードされません。

例

Input

grid size (e.g. 10×10)

Output

a perfect maze — exactly one path between any two cells

主な用途

  1. 1

    迷路パズルの生成

    解いたり印刷したりするためのランダムな迷路を作成します。

  2. 2

    経路探索のテスト

    BFS/DFS/A*を実行するためのグリッドを生成します。

  3. 3

    全域木を学ぶ

    完全迷路がグリッドグラフの全域木(spanning tree)であることを確認できます。

概要

Zerethonの迷路生成ツールは、ブラウザ上でランダムな完全迷路(perfect maze)を生成します——任意の2つのセル間にちょうど1本の経路しか存在しない迷路で(ループも孤立領域もありません)、ランダム化深さ優先探索(randomized depth-first search)などのアルゴリズムを使用します。生成処理は各セルを1回ずつ訪問し、O(cells)の時間・空間計算量で実行されます。

カテゴリ
アルゴリズム
料金
無料
プライバシー
ブラウザベース
登録
不要

参考文献

プライバシー

明記されない限り、データがブラウザの外に送信されることはありません。迷路ジェネレーター は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。

初めての方へ。Big-O 解析付きのステップバイステップ解説を読む: Graph Algorithms を学ぶ →

Zerethon Social で作成・共有・成長しよう

無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。

無料登録