はじめに
![みなため](https://minatame-lab.com/wp-content/uploads/minatame-face.png)
どうも! みなため(@MinatameT)です。
迷路を生成するアルゴリズムに「棒倒し法」というものがあります。
この記事では、この棒倒し法の考え方について説明します。
棒倒し法は迷路生成アルゴリズムの中で最も簡単なので、迷路生成の初心者の方におすすめのアルゴリズムです!
![キャラクター](https://minatame-lab.com/wp-content/uploads/minatame-n-face.png)
それでは、棒倒し法の考え方について説明していきます。
棒倒し法で迷路を生成する手順
大前提として迷路なので、通行できる「通路」の部分と、通行できない「壁」の部分が必要になるのがわかります。
※プログラミングでは、通路を0、壁を1として、フィールド(迷路の空間)を整数型の二次元配列で表すと良いですね。
![外壁の生成](https://minatame-lab.com/wp-content/uploads/maze-stick01-300x300.png)
……ということで、まずは上の画像のように、通路(薄い緑色の部分)と、外側を囲む壁(灰色の部分)を作ります。
![4つの柱(棒)の生成](https://minatame-lab.com/wp-content/uploads/maze-stick02-300x300.png)
次に、図の1から4のように、等しい間隔で壁(棒)を配置していきます。
この1から4の壁は、高い柱(棒)だと思ってください。
![1の棒倒し](https://minatame-lab.com/wp-content/uploads/maze-stick03-300x300.png)
次に、横書きの文章を読む順番で(左上から順番に)、棒を「上下左右」のいずれかの方向に倒していきます。
棒を倒す方向はランダムで、1マス分のみとします。
まずは、1の棒を上へ倒しました。
![2の棒倒し](https://minatame-lab.com/wp-content/uploads/maze-stick04-300x300.png)
次に、2の棒を左へ倒しました。
![3の棒倒し](https://minatame-lab.com/wp-content/uploads/maze-stick05-300x300.png)
次に、3の棒を下へ倒しました。
![4の棒倒し](https://minatame-lab.com/wp-content/uploads/maze-stick06-300x300.png)
最後に、4の棒を右へ倒しました。
![迷路完成](https://minatame-lab.com/wp-content/uploads/maze-stick07-300x300.png)
すべての棒を倒したら、一番上の左から2番めの外壁を撤去します。ここがスタート地点になります。
その後に、一番下の右から2番めの外壁も撤去します。ここがゴール地点になります。
![迷路完成(ルート)](https://minatame-lab.com/wp-content/uploads/maze-stick08-300x300.png)
これで、迷路が完成しました!
棒倒し法でやってはいけないこと
棒倒し法の手順を説明しましたが、「やってはいけないこと」が2つあります。それについて説明していきます。
![禁止事項 その1](https://minatame-lab.com/wp-content/uploads/maze-stick09-300x300.png)
まず1つめは、2行め以降(1行め以外)の棒を上に倒すのはいけないということです。上の画像だと、1の棒と2の棒が「1行め」、3の棒と4の棒が「2行め」に該当します。
![閉じた領域の発生](https://minatame-lab.com/wp-content/uploads/maze-stick10-300x300.png)
なぜなら、上の画像の赤い部分ように「閉じた領域」ができてしまい、そこは迷路として使えない部分になってしまうからです。
![禁止事項 その2](https://minatame-lab.com/wp-content/uploads/maze-stick11-300x300.png)
次に、上の画像のように、棒がすでに倒されている場所(壁のある場所)に壁を倒すのはいけません。画像でいえば、2の棒は左に倒せません。
![複数の正解ルートの発生](https://minatame-lab.com/wp-content/uploads/maze-stick12-300x300.png)
これを許可してしまうと、上の画像のように、複数のルートでゴール地点に到着できてしまうため、難易度が下がるからです。画像でいえば、赤と青と黒のどの矢印のルートを通っても、ゴールへ到着できます。
棒倒し法のメリットやデメリット
棒倒し法のメリットは、簡単に作れるということだけです。簡単に作れる分、自動生成された迷路はゴール地点まで簡単に到達できるものになります。
つまり、難しい迷路が作れない(一番上の通路の壁が少なくなりやすい。)ということなので、この点はデメリットだといえます。
一番上の通路の壁が少なくなりやすい理由は、一番上の通路に棒が倒れてくる確率は4分の1……つまり「25 (%) 」なのに、それ以外の通路に棒が倒れてくる確率は3分の1……つまり「33 (%) 」ほどだからです。
したがって、一番上の通路はスカスカになりやすいのです。
例えば、次の迷路は簡単にゴールできると思います。
![9×9迷路](https://minatame-lab.com/wp-content/uploads/maze-stick-result01.jpg)
上の画像は、9×9マスの簡単な迷路です。全体を見渡せば楽勝ですね。
![11×11迷路](https://minatame-lab.com/wp-content/uploads/maze-stick-result02.jpg)
上の画像は、11×11マスの簡単な迷路です。これも全体を見渡せば、すぐにゴールできます。
![13×13迷路](https://minatame-lab.com/wp-content/uploads/maze-stick-result03.jpg)
上の画像は、13×13マスの簡単な迷路です。これも余裕でゴールできますね。
このように、簡単な迷路を作ることには向いていますが、複雑な迷路を作ることには向いていないのが「棒倒し法」ですね。
![キャラクター](https://minatame-lab.com/wp-content/uploads/minatame-n-face.png)
あなたもぜひ、棒倒し法で迷路の作成に挑戦してみてください!