迷路の作成

迷路作成

前回の投稿では、迷路の経路探索について詳しく説明しましたが、それは迷路の解決に密接に関連しています。

Wall-Eプロジェクトのために迷路地図を作成しようとしたとき、このタスクを素早く簡単に達成する方法を見つけることを最初に期待していました。しかし、私はすぐに迷路と迷宮の広大で魅力的な世界に没頭してしまいました。

私はこのトピックの広がりと深さを知らなかったのです。迷路は7つの異なる方法で分類できることを発見しました。それぞれに多くのバリエーションと生成アルゴリズムがあります。

驚いたことに、このトピックを包括的にカバーするアルゴリズムの本を見つけることができず、ウィキペディアのページでも体系的な概要が提供されていませんでした。幸運なことに、さまざまな迷路の種類とアルゴリズムをカバーしている素晴らしいリソースに偶然出会いました。ぜひ探索してみることをお勧めします。

• 大規模言語モデルのコード解読：Databricksが教えてくれたこと
• 「SMPLitexに会ってください：単一画像からの3D人間テクスチャ推定のための生成AIモデルとデータセット」
• 「AIゴールドラッシュの航海：エンタープライズベンチャーにおけるテクニカルデットの隠れたコストを明らかにする」

私は次元と超次元のバリエーション、完全迷路と一筆書き迷路、平面迷路と疎な迷路など、さまざまな迷路の分類について学ぶ旅に出ました。

迷路の作成方法

私の主な目標は、迷路を表す2Dマップを生成することでした。

さまざまな迷路生成アルゴリズムを実装して比較するのも魅力的でしたが、より効率的なアプローチも求めました。最も迅速な解決策は、接続されたセルをランダムに選択する方法でした。それがまさにmazerandomで行ったことです。この単一ファイルのアプリケーションは、20×20のセルのグリッドテーブルを作成し、Depth-First Search（DFS）トラバーサルを使用してそれらをランダムに接続します。言い換えれば、私たちは単にグリッド上に通路を刻んでいるだけです。

手動で紙に書くと、以下のようになります。

これをアルゴリズム的に実現するために、セルのグリッドにDepth-First Searchを適用します。Main.cppでの実装方法を見てみましょう。

通常通り、セルのグリッドを配列の配列で表し、DFSにはスタックを使用します：

グリッドのすべてのセルを訪れ、その隣接セルをスタックにプッシュして深いトラバースを行います：

最も複雑なロジックは、ノードを到達可能（つまり壁がない）としてマークすることです。具体的には、CELL_PATH_S、CELL_PATH_N、CELL_PATH_W、CELL_PATH_Eを使用します：

最後に、SFMLライブラリを使用して迷路を画面に描画するためにdrawMazeメソッドを呼び出します。現在のセルがCELL_PATH_S、CELL_PATH_N、CELL_PATH_W、CELL_PATH_Eでマークされていない場合、2つのセルの間に壁を描画します。

ただし、この迷路には解決策が保証されていません。多くの場合、2つの点の間に明確なパスがない地図が生成されます。このランダム性は興味深いかもしれませんが、私はもう少し構造化されたものを望みました。

迷路に解決策を保証する唯一の方法は、迷路のすべての部分をある方法で接続する予め決定された構造を使用することです。

グラフ理論を使用した迷路の作成

よく知られた迷路生成アルゴリズムはグラフに依存しています。各セルはグラフ内のノードであり、すべてのノードは他のノードと少なくとも1つの接続を持たなければなりません。

前述のように、迷路にはさまざまな形式があります。いくつかは「一筆書き」の迷路として、入り口兼出口が1つだけの迷宮として機能します。他の迷路には複数の解が存在する場合もあります。ただし、生成プロセスは通常、「完全」な迷路の作成から始まります。

「完全」な迷路、または単純連結迷路とも呼ばれる迷路は、ループ、閉回路、アクセスできない領域がない特徴を持っています。それに含まれる任意のポイントから、他の任意のポイントへは正確に1つの経路が存在します。迷路には単一で解が可能な解があります。

迷路を内部表現としてグラフを使用する場合、生成された全域木によってスタートからエンドまでのパスが存在することが保証されます。

コンピュータサイエンスの用語では、そのような迷路はセルまたは頂点の集合上の全域木として記述されます。

複数の全域木が存在するかもしれませんが、目標はスタートからエンドまでの少なくとも1つの解が保証されることです。以下の例に示されているように：

上の画像は1つの解だけを描いていますが、実際には複数のパスがあります。どのセルも孤立しており、到達不可能ではありません。では、これをどのように実現するのでしょうか？

私は@razimantvによって設計された、SVGファイル形式で迷路を生成する素晴らしいmazegeneratorのコードベースを発見しました。

したがって、私はリポジトリをフォークし、それに基づいて解決策を作りました。エレガントなOOPデザインを提供してくれた@razimantvに感謝します。これにより、SFMLライブラリを使用して視覚的に魅力的な画像を作成するか、Wall-Eプロジェクトの必要なマップの説明を含むテキストファイルを生成することができました。

コードをリファクタリングして不要なコンポーネントを削除し、矩形の迷路に特化するようにしました。

ただし、スパニングツリーを構築するためのさまざまなアルゴリズムのサポートは維持しました。

また、理解しやすくするためにコード全体にコメントを追加しましたので、ここでは詳細を説明する必要はありません。メインのパイプラインは \mazegenerator\maze\mazebaze.cpp にあります。

SFMLグラフィックスライブラリを使用した視覚化を導入しました。DFSはスパニングツリーを作成するためのデフォルトのアルゴリズムですが、複数のアルゴリズムをオプションとして利用できます。その結果、画面に表示される便利なユーティリティが生成されます。

ご覧のように、左上と右下の角には入力と出力がそれぞれ1つ含まれています。コードはまだSVGファイルを生成しますが、これは元のコードベースの主な機能です。

これで、Wall-Eプロジェクトでの実験を進めることができます。皆さんがこの魅力的な迷路の世界を探索し、自分自身の旅に乗り出すことを願っています。お楽しみに！

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!