私は迷路生成アルゴリズムを書いていますが、このウィキペディアの記事が私の目に留まりました。私はそれを Java で実装することにしました。私が抱えている問題は、迷路のような画像が生成される一方で、迷路が解けないことが多く、面白くないことが多いということです。興味深いとは、到達できない場所が膨大にあり、多くの場合、多くの解決策があるということです。
私は 1234/3 ルールを実装しました (これは簡単に変更できますが、説明についてはコメントを参照してください)。迷路は常に、t ステップ間で変化がない平衡状態に達します。
私の質問は、固定された開始点と終点から迷路の解決可能性を保証する方法はありますか? また、迷路を解決するのをより面白くする方法はありますか (より少ない/1 つのソリューションと、到達できない場所がほとんど/まったくありません)。これがセルオートマトンで不可能な場合は、教えてください。ありがとうございました。
開始状態に設定できる特定の基準がない限り、単純なセル オートマトンによって解決可能で興味深い迷路を確保することは不可能だと思います。各セルがグループ全体と調整できないため、セルが全体的な形状を認識していないという事実。
それらを使用することに固執している場合は、生成が終了した後に変更とパスファインディングを組み合わせて行うことができますが、他の方法 (ウィキペディアの記事またはこの質問に示されているものなど) は実装が簡単で、壁にはなりません。セル全体を占有します（必要な場合を除く）。
問題の根底にあるのは、「迷路の質」はグローバルな尺度ですが、オートマトン セルはシステムに関する非常にローカルな知識に制限されていることです。
これを解決するには、次の 3 つのオプションがあります。
外部からグローバル情報を追加します。オートマトンとランダムな初期データを使用して迷路を生成し、迷路の品質を測定し (例: フラッド フィルやその他の迷路解法を使用)、気に入った結果が得られるまで繰り返します。
明示的なルールと状態のより複雑なセットを使用します。壁の存在とパスの長さ/品質の両方をエンコードする一連のルール/セル値を作成できます。たとえば、-1 は壁であり、正の値は上と左のすべての隣接物の合計になります。次に、正の値は、左上からのパス距離を大まかにエンコードします。それだけでは不十分ですが、一般的な考え方を示しています...システムのルールで「直接」迷路に関するアルゴリズムをエンコードする必要があります。
それほど複雑ではありませんが、完全な一連のルールを使用し、初期状態で迷路生成のルールをエンコードします。たとえば、コンウェイのライフを使用して、グライダーなどを介して迷路の生成を実装する「プログラム」である初期状態を構築できます。
上記と以下の間に類似点を描くことができれば、それが役立つ場合があります。
その上でパス検索アルゴリズムを実行します。ダイクストラは、すべての解を計算する確実な方法を提供します。A* は 1 つの適切な解決策を提供します。
迷路の難しさは、これらのアルゴリズムが迷路を解く速度によって測定できます。
一部のソリューションをシャットダウンするために、いくつかの行き止まりを追加できます。