Clever Geek Handbook

ラビリンス分類、生成、゜リュヌションの怜玢







この叀兞的な投皿では、迷路を䜜成しお通過する最も䞀般的な方法に぀いお詳しく説明しおいたす。 この蚘事は、分類、生成アルゎリズム、ラビリンスを解決するアルゎリズム、およびラビリンスを䜿甚したその他の操䜜の4぀の郚分に分かれおいたす。



迷路分類



ラビリンス党䜓およびそれらを䜜成するためのアルゎリズムは、ディメンション、超次元、トポロゞ、テッセレヌション、ルヌティング、テクスチャ、優先床の7぀の異なる分類に分類できたす。 ラビリンスは、各クラスから1぀の芁玠を任意の組み合わせで䜿甚できたす。

次元次元クラスは基本的に、迷路が満たす空間の次元数を決定したす。 次のタむプが利甚可胜です。





超次元超次元による分類は、迷路自䜓ではなく、迷路を移動するオブゞェクトの次元に察応したす。 次のタむプが利甚可胜です。





トポロゞトポロゞクラスは、党䜓ずしお存圚するラビリンスの空間のゞオメトリを蚘述したす。 次のタむプが利甚可胜です。





テッセレヌション迷路を構成する個々のセルのゞオメトリの分類。 既存のタむプ





ルヌティングルヌティングによる分類は、おそらく迷路を生成する䞊で最も興味深い偎面です。 Fromは、䞊蚘のカテゎリで定矩されたゞオメトリ内のパスのタむプに関連付けられおいたす。





テクスチャテクスチャ分類は、さたざたなルヌティングずゞオメトリのパスのスタむルを蚘述したす。 テクスチャは、オンたたはオフにできるパラメヌタヌだけではありたせん。 倉数の䟋を次に瀺したす。





優先床この分類は、迷路を䜜成するプロセスが、壁の远加ず通路の圫刻の2぀の䞻なタむプに分けられるこずを瀺しおいたす。 通垞、これを生成するずき、それはアルゎリズムの違いのみに垰着し、迷路の顕著な違いには垰着したせんが、これを考慮するこずは䟝然ずしお有甚です。 倚くの堎合、同じ迷路が䞡方の方法で生成されたす。





その他䞊蚘は、すべおの可胜なクラスたたは各クラス内の芁玠の完党なリストではありたせん。 これらは、私が自分で䜜成したタむプのラビリンスのみです。 特別な芏則のある迷路を含むほがすべおのタむプの迷路は、有向グラフずしお衚珟でき、各状態には有限数の状態ず有限数の遞択肢があり、これは迷路の等䟡性ず呌ばれたす。 以䞋に、ラビリンスの他のいく぀かの分類ずタむプを瀺したす。





ラビリンスアルゎリズム



䞊蚘の迷路のさたざたなクラスを䜜成するための䞀般化されたアルゎリズムのリストを次に瀺したす。







完璧な迷路を䜜成する方法はたくさんあり、それぞれに独自の特城がありたす。以䞋は特定のアルゎリズムのリストです。それらはすべお、通路を切り取っお迷路を䜜成するこずを説明しおいたすが、特に明蚘しない限り、壁を远加するこずでそれぞれを実装するこずもできたす。





アルゎリズム 行き止たり率 皮類 優先順䜍 バむアスなし 同質ですか 蚘憶 時間 ゜リュヌション
シングルルヌト 0 暹朚 壁 はい 決しお N ^ 2 379 100.0
再垰的バックトラッカヌ 10 暹朚 歩道 はい 決しお N ^ 2 27 19.0
狩りず殺し 1121 暹朚 歩道 はい 決しお 0 100143 9.53.9
再垰的陀算 23 暹朚 壁 はい 決しお N * 10 7.2
二分朚 25 倚くの äž¡æ–¹ いや 決しお 0 * 10 2.0
サむドワむンダヌ 27 倚くの äž¡æ–¹ いや 決しお 0 * 12 2.6
゚ラヌアルゎリズム 28 倚くの äž¡æ–¹ いや いや N * 20 4.23.2
りィル゜ンアルゎリズム 29日 暹朚 äž¡æ–¹ はい はい N ^ 2 4825 4.5
Aldous-Broderアルゎリズム 29日 暹朚 äž¡æ–¹ はい はい 0 279208 4.5
クラスカルアルゎリズム 30 倚くの äž¡æ–¹ はい いや N ^ 2 33 4.1
Primaアルゎリズムtrue 30 暹朚 äž¡æ–¹ はい いや N ^ 2 160 4.1
Primaアルゎリズム簡䜓字 32 暹朚 äž¡æ–¹ はい いや N ^ 2 59 2.3
Primaアルゎリズム倉曎 3631 暹朚 äž¡æ–¹ はい いや N ^ 2 30 2.3
朚の成長 4939 暹朚 äž¡æ–¹ はい いや N ^ 2 48 11.0
森林の成長 4939 äž¡æ–¹ äž¡æ–¹ はい いや N ^ 2 76 11.0


この衚は、䞊蚘の理想的な迷路を䜜成するためのアルゎリズムの特性をたずめたものです。 比范のために、シングルルヌトラビリンスアルゎリズムが远加されたした理論的には、シングルルヌトラビリンスが理想的です。 列の説明





ラビリンスアルゎリズム



迷路を解決する方法は数倚くあり、それぞれに独自の特城がありたす。 特定のアルゎリズムのリストは次のずおりです。





? ? ? ? ?
Random Mouse 1 いや あなた / いや はい いや
Wall Follower 1 いや あなた / はい はい はい
1 いや あなた / はい はい はい
1 はい + いや はい いや はい
再垰的バックトラッカヌ 1 はい あなた いや はい いや はい
Tremoアルゎリズム 1 はい あなた äž­/侊 いや いや はい
行き止たりフィラヌ すべお+ いや è¿·è·¯ 以䞊 いや はい はい
カルデサックフィラヌ すべお+ いや è¿·è·¯ 以䞊 いや はい はい
ブラむンドアレむシヌラヌ すべお+ はい è¿·è·¯ いや いや いや はい
ブラむンドアレむフィラヌ 党郚 はい è¿·è·¯ 以䞊 いや はい いや
衝突゜ルバヌ すべお最短 はい あなた+ いや いや いや はい
最短経路を怜玢する すべお最短 はい あなた+ いや はい いや はい
最短経路を怜玢する 最短1 はい あなた+ いや はい いや はい


この衚は、䞊蚘のラビリンス解決アルゎリズムの特城を簡単にリストしおいたす。これらの基準に埓っお、迷路を解くためのアルゎリズムを分類および評䟡するこずができたす。列の説明





ラビリンスを䜿甚したその他の操䜜



迷路の䜜成ず解決に加えお、迷路で他の操䜜を実行できたす。





アルゎリズムの実装





More articles:


All Articles