Usoda2D

出典: 究極の八百科事典『ウソペディア』
ナビゲーションに移動 検索に移動

Usoda2D(USOpedian's Dungeon Academy in 2D)とは、ウソゲームスプロジェクト用のプロトタイプとして作られたうちの一つ。2D迷路を生成し、表示するだけの機能しかない。これをベースにして、3D表示し操作可能にする想定があったが、無かったことにされた。その後、そのプロジェクトでは固定迷路を歩きまわるように手抜きという名の改良が施された。したがって、この記事はその無かったことにされた亡霊の供養を目的としたものである。

また、自動生成迷路がどのようなアルゴリズム(解法手順)で作られているのかも解説する。

迷路生成アルゴリズム[編集 | hide | hide all]























ウソペディアンMediaWikiテンプレート機能だけで2D迷路を自動生成できる。

コンピュータで迷路を作り出すには、有名なアルゴリズムが凡そ4つ存在する。

棒倒し法(ぼうたおしほう)
ドルアーガの塔と呼ばれる古(いにしえ)のゲームで使われていた(らしい)。古めかしいが簡単であり、その代わり精度の悪い迷路が作られる。このUsoda2Dでも用いている方法である。配列変数に対応していない言語や繰り返し処理がまともに出来ない言語、RPGツクールなどのツールでも再現可能なことが多く、迷路ゲーム作成者には愛好されている方法である。
一番の欠点は上から見下ろす二次元迷路としては簡単過ぎるものしか作られないこと。しかし、3D迷路ならば、3D迷路自体が難易度が鬼上がりするため、十分に用を供することができる。
壁掘り法(かべほりほう)
壁のみのマップを作っておき、ランダムに定めたスタートの地点から通路を作る(壁を掘る)ことで迷路を作っていく方法。基本的には1マス飛ばしで元の道に戻らない、且つ他の道と合流しない方向にある壁を、ランダムに壊すことで迷路を作っていく。もしも壁を作ったら他の道に合流するしかなかったりそもそも道を作れなく買ったら、今まで通ってきた道を一つ手前に戻り、同様に空いている方の壁を壊し道を掘り進める。これが全ての経路でできなくなったら迷路が完成している。
この方法は再帰処理を用いて作られることが一般的である。また、普段の実生活上で想像しやすい迷路の作成方法(山にトンネルを掘って迷路を作るイメージ)である。
欠点としては迷路のスタート地点の方は分岐が多く、ゴールの側に近づくと分岐がやや少なくなることである。
壁伸ばし法(かべのばしほう)
迷路の外周を作っておく。その外周をランダムに選び、外周から他の壁に繋がらないように上下左右に向けて壁を引く。さらにその壁を伸ばすように、可能な限り繰り返す。もしもこれが不可能であれば、前に伸ばした壁に戻り、再度別の方向へ壁を伸ばす。これを全ての外周を通して不可能になったら迷路が完成する。
アルゴリズムとしては、壁掘り法の亜種である。進化形とは言えず、殆ど対になっている。
そのため欠点も逆転しており、迷路のスタート地点よりも、ゴールのそばのほうが若干難しくなる。そのため、壁掘り法よりは優れていると言われることもあるが、迷路生成後にスタート地点とゴールをランダムに選ぶ場合に差異は存在しない。
クラスタリング法(くらすたりんぐほう)
比較的新しい手法のアルゴリズムである。クラスタリングによる迷路作成アルゴリズムを参照して欲しい。上の3つには一長一短があったが、この方法は作られた迷路の分岐に偏りが生まれないという素晴らしい特徴と、逆に予めゴールの道を描いたのちに処理することで、迷路を解くとその描いていおいた道(=絵)が浮かび上がるようなものを的簡単に作りだすことが可能である。
もちろん、予め経路を描いておく手法は壁掘り法でも、壁のばし法でも可能であるが、迷路を作りつつ分岐可能な通路を解析しておく必要があり、この手法よりは手間がかかる。従って、そのような用途にはこのクラスタリング法が優れている。

棒倒し法での迷路生成例[編集 | hide]

実際にここウソペディア上で使われているMediaWikiのテンプレート機能によって「棒倒し法で迷路を生成した例」がこのページの右上に出ているはずである。

ただし、この迷路は棒倒し法を簡易実装したものである点に注意しなくてはならない。それは、「壁を作った先に既に壁があったら、別の方向へ壁を作るという処理」を実装していない点だ。このような簡略化により、ソースコードは更に簡単になるが、その影響で浮島と呼ばれる、「ゴールに繋がっている壁と繋がっていない壁」が作られる点だ。

二次元迷路においては、この「浮島」は概ね無用な存在だと考えられている。その理由は、浮島があることで迷路の正解の経路が増えるからである。言い換えれば、浮島があるということは、迷路全体の面積に対して、正解の通路の含有率が上がるということである。要するに正解にたどり着きやすく、「浮島のある迷路=簡単な迷路」ということが言えるのである。

なお、先ほどの迷路において「概ね」と補足した理由は、「迷路を人間が作る際に、あえて浮島を作る」ことがあるからだ。このような意図をもたせた浮島の存在は悪いものではなく、むしろその迷路を楽しい物にするための手段なのである。しかし、自動生成迷路において、コンピュータが無作為に作り出す迷路においては、このような特徴は生まれ得ない訳である。

したがって、このUsoda2Dが作り出している迷路も、簡単なものでしかない。

されど、いわゆる3D迷路のように、現在位置から周囲数マスの情報しか得られない閉塞した空間においては、その限りではない。その場合、迷路解法アルゴリズムなどでゴールを目指すことになるが、これらは浮島に対して脆弱だからである。いわゆる壁伝い法や、トレモーアルゴリズムは、浮島の個数に応じてその試行回数・計算回数が上昇することが知られている。

ウソペディアでの迷路描画コード[編集 | hide]

実際にウソペディア上での迷路描画コードは以下に存在する。

デバッグ出力[編集 | hide]

以下にUsoda2Dが実際に迷路を作った内容を示す。

0112322002
0022120110
2212220112
1101100010
1022110202
1122011112
0120020201
1222011001
2011200011
1120020002

DebugPrint

迷路生成部のソースコード[編集 | hide]

実際にUsoda2Dのソースは以下に存在する。

CreateMaze

以下はその中身である。

{{#vardefine:wall_0_0|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_1|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_2|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_3|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_4|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_5|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_6|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_7|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_8|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_0_9|<choose uncached><option>0</option><option>1</option><option>2</option><option>3</option></choose>}}
{{#vardefine:wall_1_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_1_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_2_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_3_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_4_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_5_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_6_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_7_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_8_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_0|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_1|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_2|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_3|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_4|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_5|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_6|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_7|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_8|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}
{{#vardefine:wall_9_9|<choose uncached><option>0</option><option>1</option><option>2</option></choose>}}

アルゴリズムの解説[編集 | hide]

前述のとおり、このUsoda2Dは棒倒し法により作られている。このアルゴリズムの解説はこちらを参照して欲しい。


関連事項[編集 | hide]

Bouncywikilogo small.gif
ユーモア欠落症患者の為にウィキペディアのユーモア欠落症のマフィア達が「迷路」の項目を執筆しています。
Workstation Computer.png
Usoda2D』はコンピュータに関した書きかけのデータです。このページをエディットし、リビジョンしてくれる方を求めています。 → ポータル:コンピュータ