【Processing】四角形、六角形、三角形の迷路生成アルゴリズム（Maze Generator）

成果物

仕組み

指定した場所からスタートし、まだ行ったことがなくて進める方向に、壁を壊しながら進んでいくという仕組みです。どこにも進めない場合は、前にいた場所に戻ります。これほどシンプルなコードで、深さ優先探索で全て塗りつくせるようになっています。なぜこうなるのか、考えてみると面白いですよ。

作り方・コード

全てのコードは、こちらに含まれています。

github.com

STEP1（四角形の迷路自動生成）

プログラムの難易度は次のようになっています。三角形は上下反転があるのでややこしいです。

四角形＜六角形＜三角形

それでは、まず、CodingTrainの解説を見て、四角形の迷路生成アルゴリズムの仕組みを理解してください。

www.youtube.com

STEP2（多角形の表示プログラム）

次に、今回使う多角形を表示するプログラムのデモを見てください。Processingのデモコードは、Polygonという名前です。

多角形の面を描画するにはpolygon関数を使います。

polygon(x, y, n, r, invY,rot)

横倒しが標準ですが、今回は、縦にしたいのでrotには-90度にしています。invYは、-1で上下反転です。普段は1でいいです。

多角形の壁（辺）を描画するにはpolygonLines関数を使います。

polygonLines(x, y, n, r, invY,rot,walls)

wallsがtrueの時、辺が描画されます。インデックスは、時計回りに割り当てられていて、今回は、-90°回転させているので、一番上の頂点から割り当てられています。wallsの要素の数が、辺の数だけ必要なことに注意してください。

STEP3（六角形のプログラム）

進める方向が6つに増えています。偶数列、奇数列で配置がずれるので、奇数列の時一つ左側のマスを選択するようになっています。詳しい数式は、ページの一番下に改定あります。ProcessingのコードはMazeHexagonです。

STEP4（三角形のプログラム）

規則的に三角形を反対にしなければなりません。ページの一番下で紹介しているinvTest()が-1の時上下を反転させ、さらには、場所をそろえるために、少し上に動かさなければなりません。別の方法で、三角形を描画するのもいいと思います。ぜひ、いろいろな方法を試してみてください。ProcessingのコードはMazeTriangleです。

BONUS（具体的な数式）

今回は、四角形も三角形も六角形も横幅（w）が同じになるようにしています。

iが配列の横の番号、jが配列の縦の番号として、座標x,yと半径rを求めるには、六角形の場合。

$\begin{array}{l}x=iw\\y=\frac{3}{2\sqrt{3}} jw\\r=\frac{w}{\sqrt{3}}\end{array}$

今回は、画面からはみ出ないように座標にオフセットを足しています。列によってxoffは変わります。条件式は、満たしたときのみ、その式が実行されると思ってください。

$\begin{array}{l}( j\bmod 2==0) \ xoff=w/2\ \\( j\bmod 2==1) \ xoff=w\ \\yoff=\frac{w}{\sqrt{3}}\end{array}$

三角形の場合は、

$\begin{array}{l}x=\frac{iw}{2}\\y=\frac{\sqrt{3}}{2} jw\\r=\frac{\sqrt{3}}{3} w\\invY=invTest( i,j)\end{array}$

invTestは偶数列、偶数列、もしくは、奇数列、奇数列の時に1を返しそれ以外では-1を返すというものですが、コンパクトな数式で表すとこうなります。また、オフセットは次のようになります。

$\begin{array}{l}(( i\bmod 2+j\bmod 2) \%2==0) \ invTest( i,j) =1\\(( i\bmod 2+j\bmod 2) \%2\neq 0) \ invTest( i,j) =-1\\xoff=w/2\ \\yoff=\frac{w}{\sqrt{3}} \ \\yoff=w/sqrt( 3)\end{array}$