1. まとめトップ

確実に『方向音痴』になる迷路!道に迷う、迷子のメカニズム

ちょっとした工夫が、迷路を難しくする。

更新日: 2014年10月09日

0お気に入り3914view
お気に入り追加

この記事は私がまとめました

tanari34abさん

■目次
- 迷路生成アルゴリズムが凄い!
- 定番の迷路生成アルゴリズムの概略
- 迷路の本質はループしないこと
- 確実に『方向音痴』になる迷路

迷路生成アルゴリズムが凄い!

このまとめでは、少し変わった迷路の作成方法を紹介する。

迷路生成アルゴリズムとは、コンピュータで自動的に迷路を作り出す為の「仕組み」のようなものである。

迷路生成アルゴリズムは多くの種類がある。

たとえば、以下のページには、多くの迷路が紹介されている。

*Maze Classification
http://www.astrolog.org/labyrnth/algrithm.htm

といっても、上のページでは作成済みの迷路が紹介されているだけなので、迷路生成アルゴリズムの凄さが伝わらないと思う。

以下の参考サイトでは、実際に、迷路を自動生成できるので、アルゴリズムの面白さがわかると思う。


*Meiro123
http://meiro123.com/
標準的な迷路アルゴリズム。プリントできる。

*Maze generation in 3D
http://totologic.blogspot.jp/2013/04/maze-generation-in-3d.html
迷路空間を歩くことができる。

*Wilson’s Algorithm
http://bl.ocks.org/mbostock/11357811
道のばし法を応用した手法と言えると思う。迷路が徐々に作成される過程を見ることができる。

定番の迷路生成アルゴリズムの概略

迷路生成アルゴリズムとして、有名なのは以下の3つの方法である。

1.道のばし法(穴あけ法)
2.壁のばし法
3.棒倒し法

http://okguide.okwave.jp/guides/73617

道をのばし、分岐させるという作業を繰り返す手法。
ただし、道をのばした時に、すでに存在する道にぶつかってはいけない。

http://okguide.okwave.jp/guides/73729

道のばし法のと同じ要領で、壁をのばす手法。

迷路の本質はループしないこと

一見難しそうだが、実は、迷路生成アルゴリズムは、単に、ループしない道を、生成し続けているだけである。

少し特殊な方法になるが、「分割法」というアルゴリズムを見るとわかりやすい。

http://sasataro.hateblo.jp/entry/2014/10/06/181309

道がループしないようにするには、4つ目の区画に道が達したら、道をのばすのを終了すればいい。

http://sasataro.hateblo.jp/entry/2014/10/06/181309

1つのスペースを4つの区画にわけて、その区画の3つをつなげれば、ループしない道ができるということである。

http://sasataro.hateblo.jp/entry/2014/10/06/181309

4つに分割、3つを道でつなぐという単調な作業を繰り返すと、迷路ができる。

確実に『方向音痴』になる迷路

既に紹介した迷路生成アルゴリズムは、どれも、正方形のセルを前提につくられている。

正方形のセル上に描かれた迷路は、道の全体像が把握しやすいという欠点がある。

しかし、セルの形が、不規則な形状だったらどうだろう。

実は、迷路アルゴリズムにおいて、セルは正方形でなくてもよい。

すべてのセルの形状や大きさが異なっていたとしても、道のばし法が適用できるのである。

それでは、不規則な形状のセルの上に迷路を描くことにしよう。

方向音痴迷路(1/5)

まず、隣接する多角形が「1本の辺」によって接するように、多角形セルを描く。
(今回は直線で描いたが、各辺は曲線でも描いてもよい。)

方向音痴迷路(2/5)

各多角形の中心点を書き、隣接する多角形の中心点同士を線で結ぶ。
(中心点は、正確でなくても良い。)
(ここで引いた緑色の線を、迷路の道を考えるときに使う)

方向音痴迷路(3/5)

スタートとゴールを設定し、正解路(赤線)を描く。
正解路は、同じセルを2回通ってはならない。

方向音痴迷路(4/5)

不正解路を描く。
正解路を分岐させるようにして、不正解路を描く。
その際、不正解路が既存路に戻ってはいけない。
不正回路を更に分岐させても良い。
これを繰り返して、すべての多角形の中点に、路が達するようにする。

方向音痴迷路(5/5)

正解路と不正解路が通る壁に穴を開け、補助線をすべて消す。

最後に

セルの数が、少ない割に、非常に難解な迷路になっていると思う。
難解な迷路とは言っても、紙と鉛筆を使えばすぐにゴールできる。

しかし!!!
これが、巨大迷路施設だったとしたらどうだろう。
自分が通った道を覚えることすら難しいはずである。
確実に方向音痴になると思う。

1