検索とフラストレーション
詳細や前置きなしで始めます-学生生活の中で、長方形の迷路を生成するアルゴリズムが必要でした。 罪深い唇に祈りながら、私はGoogleの果てしない腸に真っ逆さまに突っ込んで、 この記事を掘り下げました。 アルゴリズムはシンプルで明確であり、必要な理想的な非周期的な迷路を提供しました（迷路の任意のポイントから、他の任意のポイントに到達できますが、1つの方法でのみ） 6か月間の実装。 それはとても起こりました。 そして、率直に言って、結果に失望しました。 アルゴリズムは、20未満の次元の多かれ少なかれ興味深い迷路を生成しましたが、問題はこの境界からどこかで始まりました。
1.予測可能性
試していなかったので、迷路の左上隅から右上への移動は、下の2つのレベルを通過することによってのみ可能でした。 広い廊下のようなものにするなど、いくつかの機会を提供しましたが、私はそれを必要としませんでした。
2.メモリ消費
DOSBoxエミュレーターを実行した古き良きPascalでアルゴリズムを作成しました。 これにより、RAMが64Kバイトに制限されました。 3バイトの変数を含む構造体の配列にラビリンスを保存したため、ダイナミックメモリを使用せずに150x150を超えるサイズのラビリンスを作成することには問題がありました。
3.アルゴリズムの不完全さ
アルゴリズムが考えられるすべてのシナリオを考慮しなかったため、さまざまな望ましくないアーティファクトが出現しました。
これらの3つのポイントを実現した後、このアルゴリズムを放棄して独自のアルゴリズムを作成することにしました。
アイデアと実装
だから、私は完璧で非周期的な迷路が必要でした。 以前のアルゴリズムは空の部屋に壁を建設することを暗示していたので、私は別の方法、つまり、固い地面に道路を掘ることにした。 これは、小さな「じゃじゃ馬」によって行われます。これは、2次元座標のままです。 しかし、どのアルゴリズムが「トガリネズミ」の動きをガイドしますか？ いや！ 広大なダンジョンの「トガリネズミ」は、大韓民国のランダムによって駆動されます。
実際には、アルゴリズム
1を通路として、0を壁として指定します。 初期条件は、ゼロで満たされた2次元配列です。 配列の次元は任意の奇数です。 壁の左上隅には座標（1; 1）があると考えられます。 「トガリネズミ」の座標は常に偶数で、それぞれ、配列内の長い2つの要素をジャンプすることによってのみ移動します。
- 「トガリネズミ」のタッチダウンポイントをランダムに選択-ゼロ以外のランダムな座標を生成します。 タッチダウンポイントは1に設定されます。
- 上、下、左、右のいずれかの方向をランダムに選択します。
- 選択した方向にジャンプした後、外壁または通路にいる場合は、前のポイントに戻ります。 それ以外の場合は、指定された方向にジャンプします。 着陸してジャンプしたセルに値1を割り当てます。
- 着陸後にジャンプ（行き止まりに入る）ができない場合、ランダムに座標を生成します。 それ以外の場合-2番目のポイントに進みます。
- 示された座標に通路がなくなるまで、上記の点を繰り返します。
すべてがとてつもなく単純です。 遅かれ早かれ、私たちは最後の2つのポイントでサイクルに行きます。 アルゴリズムの割り込みは、カウンターまたは単純なチェックのいずれかです。各セルに偶数の座標がある場合は、アルゴリズムを安全に中断できます。
利点：
- 実装の容易さ
- 2つのセル状態で動作します
- 単純な着信および発信データ
- 迷路のサイズに関係なくエラーなく動作します
短所：
- 構造内の単純な迷路
以上です。 少なくとも誰かに役立つことを願っています。
UPD
ここにイラストを添付するのは論理的ですので、ここに。 迷路の寸法-320x240
