みなためラボ

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

文字サイズ

はじめに

どうも! 高杉 皆為(@MinatameT)です。

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

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

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

それでは、棒倒し法の考え方について説明していきます。

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

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

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

外壁の生成

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

4つの柱(棒)の生成

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

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

1の棒倒し

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

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

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

2の棒倒し

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

3の棒倒し

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

4の棒倒し

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

迷路完成

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

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

迷路完成(ルート)

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

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

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

禁止事項 その1

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

閉じた領域の発生

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

禁止事項 その2

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

複数の正解ルートの発生

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

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

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

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

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

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

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

9×9迷路

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

11×11迷路

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

13×13迷路

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

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

あなたもぜひ、棒倒し法で迷路の作成に挑戦してみてください!


 

みなためじゃんけん

このコーナーは、私と擬似的にじゃんけんできるコーナーです。

みなためじゃんけん、じゃんけんぽん!

私が出したのは……





チョキ

チョキでした! グーの勝利です!



この記事をSNSでシェアする

プログラミングカテゴリーの最新記事(5件)

最新記事(10件)

管理人のTwitter

内部リンク集