Clever Geek Handbook

古典的な迷路生成アルゴリズム。 パート1：はじめに





まえがき



迷路を生成するアルゴリズムに関するロシア語の資料がほぼ完全に不足しているため、記事を書くようになりました。 Habréでは、一般的に主題に関するものから、2つの記事に注目することができます： 1と2 。 その価値と利点はほんの2番目です。 最初は-正式なアルゴリズムの単なる翻訳とその簡単な説明です。 もちろん、これは悪いことではありませんが、非常に少なく、トピックをさらに勉強したいという欲求を引き起こしません。



私の記事が気に入ったら、さまざまなアルゴリズムについて書いていきます。 最も基本的で単純な2つのケース、バイナリツリーの生成と、本質的に1つの顕著なプラスを持つバイナリツリーのわずかに変更されたバージョンであるSidewinderを検討します。 注意トラフィック 。



アドバイスを1つお伝えします。実装を記述するまでコードを覗かないでください。 ある言語から別の言語に翻訳するだけの場合よりも、バグを修正してエラーを見つけることで、はるかに多くの喜びと利益が得られます。



真剣に。 アドバイスをください。 確かに、あなたはもっと時間を費やしますが、それだけの価値はあります。 たとえば、いくつかのエラーにより、さまざまなSci-Fiゲームでテキストを作成するために使用できる「エイリアン」テキストの非常に面白いジェネレーターを入手しました。 トピックを自分で勉強して、どこにも急がないでください。



PS：



英語のバイアスを意味するために「 バイアス 」という用語を使用します。 つまり 任意の方向の方向へのアルゴリズムの中毒。 たとえば、右シフト-アルゴリズムは長い右の通路を持つ迷路を生成します。



ラビリンスは、フィールドの左端から特定のセルまでの距離を基準にペイントされます。 原点から遠くなるほど、色は濃くなります。



理想的なラビリンスは、1つのセルが1つの方法で別のセルに接続されるラビリンスです。 言い換えれば、スパニングツリー。



Luaについて
迷路のトピックを掘り始めたばかりのとき、最終的に記事を書いて、レンダリングとアーキテクチャにあまり時間を費やさず、ロジックだけを扱う機会のある言語を選択するとは思っていませんでした。 その結果、C ++とLuaの間で、LuaとLove2Dが選択されました。



Luaに不慣れであっても心配しないでください。 言語の無知は、構文が単純であるため、実装の理解を妨げることはありません。 少なくとも少しプログラミングする方法を知っていれば、コードの80％は理解の問題を引き起こしません。 残りの20％は言語固有のものであり、これについては記事の冒頭で常に記述し、彼らの仕事を説明します。



私が最初に言うべきこと：

Luaには、データ構造が1つだけあります-テーブル-必要な構造を作成するための連想配列。 たとえば、クラス、セット、通常の配列、スタック、キューなど。 小文字のキーまたはインデックスを使用してそれらにアクセスできます。

また、テーブルは1つのオブジェクトに1つのデータ型のみを格納することを制限せず、C / C ++の構造と同様に機能します。 そのようなコードは絶対に正しいです： 



ourStructure = {} ourStructure[“BeautyKey”] = 42 ourStructure[42] = “UltimateAnswer” ourStructure[1] = false


nilを割り当てると、フィールドが削除されます。 

 ourStructure[42] = nil




第二：

Luaには、隠しテーブルコピーメカニズムがありません。 以下のコードは、新しいSomeNewArrayオブジェクトをコピーして作成するのではなく、SomeArrayオブジェクトへの参照をそのオブジェクトにコピーするだけであるため、C / C ++の非定数リンクまたはポインターを介して値を渡す場合と同じ方法で変更します： 



 someArray = {} someArray[1] = 42 someArray[2] = “ReferencesTest” someNewArray = someArray someNewArray[1] = “42 Is Gone, Now Only the Garbage-String here”




そして第三に、Luaに精通している人のために：

はい、一部の場所ではコードが冗長であることを知っています。 また、一部の場所ではすべてがメタメソッドによって簡素化できるという事実。 コードは主にアルゴリズムを理解するために作成されたものであり、実際のプロジェクトで使用するためのものではないことに留意してください。 さらに、言語固有の機能が過剰にないため、コメントの山なしにコードをフォーム内に配置できます。





二分木アルゴリズム























説明 ：



私が検討することを理解する上で、最初で最も簡単なアルゴリズム。 その本質は、フィールドの各セルからランダムな方向に道を開くことです：私の実装では、（選択したオフセットに応じて）上または右のいずれかです。 単位時間あたり1つのセルのみを処理するため、無限のサイズのラビリンスを生成できます。最終的な結果（ラビリンス）のみを保存し、二次情報を保存する必要はありません。



この生成方法には2つの副作用があります。



1.ラビリンスには、斜め方向の変位が大きく、その方向に行き止まりがありません。 上記のスクリーンショットを見ると、各廊下が右上のセルに向かっている傾向があり、その結果、パスが1つだけであり、行き止まりがないことがわかります。



2.迷路の両側にある2つの空の廊下。 アルゴリズムが行/列の最後まで「掘る」とき、空の「境界」を作成して、パスを一方向に継続する以外に選択肢はありません。



ところで、名前はデータ構造と一致するだけではありません。 彼の仕事の結果は、各セル（頂点）からルート（親頂点）へのパスがちょうど1つ、したがって他のセルへのパスがちょうど1つであるランダムなバイナリツリーです。 その結果、どのセルにも、隣接セルとの接続は3つ以下になります。



形式アルゴリズム（北東バイアス用）：



  1. 初期セルを選択します。
  2. 道を開くためにランダムな方向を選択してください。 この方向の隣接セルがフィールドの境界を越える場合は、可能な方向にのみセルを掘ります。
  3. 次のセルに移動します。
  4. すべての細胞が処理されるまで、2〜3を繰り返します。


作業例
緑は問題の現在のセル、赤は前面、移動可能なセルです。



座標（0; 0）から始めます。 そうしないと迷路の境界を越えてしまうため、この列の2階に行くことはできません。 途中ですべての壁を破壊し、すぐに停止します。











それで終わりです。 どこにも行きません。 次の行に移動して、今度は右上に移動する機会があることを確認します。







コインを投げて選択...トップ。 壁を取り除き、次のセルに進みます。





素晴らしい。 チャンスは私たちに正しく行くように言います。 壁を取り除き、次のセルに移動します。















私たちには選択肢がありません。左に行くことはできません。つまり、上から壁を取り除き、次の行に進みます。











コインは私たちに正しい方向に進むよう説得します。 さて、聞いて。 壁を取り除き、次のセルに進みます。











メーターを転がして、不幸な金属片が落ち、上昇する時だと言います。 壁を破壊し、次のセルに移動します。この列の最後のセルなので、上から壁を取り除きます。 迷宮は終わりました。















長所 ：



短所 ：



実装 
 local mod = {} local aux = {} aux.width = false aux.height = false aux.sx = false aux.sy = false aux.grid = false function aux.createGrid (rows, columns) local MazeGrid = {} for y = 1, rows do MazeGrid[y] = {} for x = 1, columns do MazeGrid[y][x] = {bottom_wall = true, right_wall = true} -- Wall grid end end return MazeGrid end -- Binary Tree North-East variant function mod.createMaze(x1, y1, x2, y2, grid) aux.width, aux.height, aux.sx, aux.sy = x2, y2, x1, y1 aux.grid = grid or aux.createGrid(aux.height, aux.width) aux.binarytree() return aux.grid end function aux.binarytree() for y = aux.sy, aux.height do for x = aux.sx, aux.width do if y ~= aux.sy then if math.random(0, 1) == 0 then if x ~= aux.width then aux.grid[y][x].right_wall = false else aux.grid[y-1][x].bottom_wall = false end else aux.grid[y-1][x].bottom_wall = false end else if x ~= aux.width then aux.grid[y][x].right_wall = false end end end end end return mod




Sidewinderアルゴリズム























説明 ：



翻訳中のSidewinderという名前のアルゴリズムは、バイナリツリーアルゴリズムと非常によく似ています。特徴的な対角線シフトがないという点で、1つの空のコリドーとセルを別々にではなく、セットで考慮します。 ラビリンスは、主に垂直方向または水平方向の変位（実装に応じて）で得られ、方向に行き止まりはありません。 より原始的な対応物と比較すると、変位はそれほど顕著ではなく、垂直および水平のコリドーをスムーズに置き換える「らせん」のようなものです。



副作用に関して、Sidewinderは片側に2つではなく1つの空の廊下を作成します。 フィールドの最初の行からセットの作成を開始しますが、パスを掘り下げる機会はありません。私たちは最も極端な垂直位置にあり、高くしようとするとフィールドの境界を越えることになります。 ただし、垂直方向に移動せずにセットを整理しても、互いに分離された複数の領域を作成します。



たとえば、最初の行の9つのセルを3つのセットに分割し、その間に壁を配置できます。 2行目の各セットは、上記の3つの「ブロック」の1つへのパスを掘ります。 3番目の行は、2番目の「ブロック」への道を開きます。 フィールドの終わりまで続きます。 その結果、3つの分岐し、互いに垂直な領域から分離されます。これは理想的な迷路には適さず、フィールドの各ポイントから他のパスまで正確に1つのパスがあります。



形式アルゴリズム（標準バイアス用）：



  1. 開始行を選択します。
  2. 行の最初のセルを選択し、現在のセルにします。
  3. 空のセットを初期化します。
  4. 現在のセルをセットに追加します。
  5. 右への道を開くかどうかを決定します。
  6. 舗装されている場合は、新しいセルに移動して現在のセルにします。 手順3〜6を繰り返します。
  7. 舗装していない場合は、セットのランダムなセルを選択し、そこから上に向かって舗装します。 次の行に進み、2〜7を繰り返します。
  8. 各行が処理されるまで続行します。


作業例
赤血球は多数のメンバーです。

最初の行から始めて、それが上にあることを確認します-フィールドを超えています。 すべての壁を取り壊し、すぐに2行目に行き、空のセットを作成します。











それで、ここでもっと面白いです。 行の最初の2つのセルをセットに追加しましょう。







これらのセルのいずれかを選択し、最初の行でそれに属する上部の壁を削除します。







セットをゼロにし、行の次のセルを追加します。







今回は誰とも団結しておらず、この単一のセルから直接道を切り開いています。







アクションを繰り返します。 セットをゼロにし、次のセルに移動して追加します...そして、行の最後のままなので、上から壁を削除し、下の行に移動します。











そして、最初の3つのセルをすぐに1つのセットに結合します。







セル、ここでは2番目のセルをランダムに選択し、上から前の行まで壁を削除します。







さて、ここでも選択の余地はありません。上の壁を取り除き、下の列に進みます。











今回は、最初のセルのみを作成します。 前の列の壁を削除して、次のセルに移動します。











最後に3つのセルを結合するとします。







また、セットの中央のセルが気に入ったので、そこから壁を取り外します。 これで、迷路の準備ができました。









長所 ：





短所 ：





実装 
 local mod = {} local aux = {} aux.width = false aux.height = false aux.sx = false aux.sy = false aux.grid = false function aux.createGrid (rows, columns) local MazeGrid = {} for y = 1, rows do MazeGrid[y] = {} for x = 1, columns do MazeGrid[y][x] = {bottom_wall = true, right_wall = true} end end return MazeGrid end function mod.createMaze(x1, y1, x2, y2, grid) aux.height, aux.width, aux.sx, aux.sy = y2, x2, x1, y1 aux.grid = grid or aux.createGrid(y2, x2) aux.sidewinder() return aux.grid end function aux.sidewinder() local cx = aux.sx --[[ cx –     x.         ,          ]] for y = aux.sy, aux.height do for x = aux.sx, aux.width do if y ~= aux.sy then if math.random(0, 1) == 0 and x ~= aux.width then aux.grid[y][x].right_wall = false else aux.grid[y-1][math.random(cx, x)].bottom_wall = false if x ~= aux.width then cx = x+1 else cx = aux.sx end end else if x ~= aux.width then aux.grid[y][x].right_wall = false end end end end end return mod




エピローグ



この記事を楽しんで、迷路の原始的な手続き生成についての新しい知識を得たと思います。 実装と作業に最も簡単な2つのアルゴリズムを選択したので、初心者がトピックに「触れ」て、さらに勉強したいかどうかを理解しやすくなります。 そのような記事がHabrahabrの人々にとって興味深いものであるかどうか、そしてそれらを書き続ける価値があるかどうかを知ることは私にとって重要です。 読者には、検討する価値のある少なくとも9つの古典的なアルゴリズムがあります。 それらのいくつかは、PrimまたはWilsonアルゴリズムなど、フィールドをランダムにウォークします。一部は、EllerやKruskalなどのグラフで動作するため、動作するためにより多くのリソースを必要とします。 しかし、これは終わりではありません-私は袖に物を持っています：極（円形）ラビリンス、さまざまなグリッド（ヘックス、三角形など）のラビリンスの生成、碑文と形状のラビリンスのマスキング、2.5Dラビリンスと3D、理論迷路、アルゴリズムの統計的比較、生成アルゴリズムの組み合わせ。 最終的に、ラビリンスの種類には非常に多くのバリエーションがあります。 たとえば、現在、各ポイントから他のパスへのパスが1つだけである理想的なアルゴリズムを検討しています。 しかし、1つのセルに他のセルへの複数のパスを許可するものもあります。 たとえば、いくつかの噂によると、Quake、Doom、およびその他の新ジャンルのシューティングゲームでは、このようなアルゴリズムを使用してレベルが生成されていました。



したがって、記事、トピックが気に入った場合、さらにそれらを参照したい場合は、コメントでそれについて書いてください。 また、技術的、言語的、スタイリストの両方の批判に非常に満足しています。


More articles:


All Articles