【よくわかる】迷路生成アルゴリズム「棒倒し法」を説明！

はじめに

迷路を生成するアルゴリズムに「棒倒し法」というものがあります。

この記事では、この棒倒し法の考え方について説明します。

棒倒し法は迷路生成アルゴリズムの中で最も簡単なので、迷路生成の初心者の方におすすめのアルゴリズムです！

棒倒し法で迷路を生成する手順

大前提として迷路なので、通行できる「通路」の部分と、通行できない「壁」の部分が必要になるのがわかります。

※プログラミングでは、通路を0、壁を1として、フィールド（迷路の空間）を整数型の二次元配列で表すと良いですね。

……ということで、まずは上の画像のように、通路（薄い緑色の部分）と、外側を囲む壁（灰色の部分）を作ります。

次に、図の1から4のように、等しい間隔で壁（棒）を配置していきます。

この1から4の壁は、高い柱（棒）だと思ってください。

次に、横書きの文章を読む順番で（左上から順番に）、棒を「上下左右」のいずれかの方向に倒していきます。

棒を倒す方向はランダムで、1マス分のみとします。

まずは、1の棒を上へ倒しました。

次に、2の棒を左へ倒しました。

次に、3の棒を下へ倒しました。

最後に、4の棒を右へ倒しました。

すべての棒を倒したら、一番上の左から2番めの外壁を撤去します。ここがスタート地点になります。

その後に、一番下の右から2番めの外壁も撤去します。ここがゴール地点になります。

これで、迷路が完成しました！

棒倒し法でやってはいけないこと

棒倒し法の手順を説明しましたが、「やってはいけないこと」が2つあります。それについて説明していきます。

まず1つめは、2行め以降（1行め以外）の棒を上に倒すのはいけないということです。上の画像だと、1の棒と2の棒が「1行め」、3の棒と4の棒が「2行め」に該当します。

なぜなら、上の画像の赤い部分ように「閉じた領域」ができてしまい、そこは迷路として使えない部分になってしまうからです。

次に、上の画像のように、棒がすでに倒されている場所（壁のある場所）に壁を倒すのはいけません。画像でいえば、2の棒は左に倒せません。

これを許可してしまうと、上の画像のように、複数のルートでゴール地点に到着できてしまうため、難易度が下がるからです。画像でいえば、赤と青と黒のどの矢印のルートを通っても、ゴールへ到着できます。

棒倒し法のメリットやデメリット

棒倒し法のメリットは、簡単に作れるということだけです。簡単に作れる分、自動生成された迷路はゴール地点まで簡単に到達できるものになります。

つまり、難しい迷路が作れない（一番上の通路の壁が少なくなりやすい。）ということなので、この点はデメリットだといえます。

一番上の通路の壁が少なくなりやすい理由は、一番上の通路に棒が倒れてくる確率は4分の1……つまり「25 (%) 」なのに、それ以外の通路に棒が倒れてくる確率は3分の1……つまり「33 (%) 」ほどだからです。

したがって、一番上の通路はスカスカになりやすいのです。

例えば、次の迷路は簡単にゴールできると思います。

上の画像は、9×9マスの簡単な迷路です。全体を見渡せば楽勝ですね。

上の画像は、11×11マスの簡単な迷路です。これも全体を見渡せば、すぐにゴールできます。

上の画像は、13×13マスの簡単な迷路です。これも余裕でゴールできますね。

このように、簡単な迷路を作ることには向いていますが、複雑な迷路を作ることには向いていないのが「棒倒し法」ですね。