作成日：2002-02-15
棒倒し法
はじめに
迷路作成アルゴリズムには、大きく分けて「棒倒し法」と「穴掘り法」の２種類がありますが、このページでは棒倒し法を紹介します。 また、迷路作成のための処理をいくつかのステップに分けて解説します。- ▽ STEP 1
-
まず、迷路の枠組み（周囲の壁）を作成します。
■図１
- ▽ STEP 2
-
次に、１ブロックおきに、基準となる点（壁）を作成します。
これを仮に基準点と呼びます。
■図２
- ▽ STEP 3
-
次に、一番左側の基準点（下図の赤い部分）に注目します。
この全ての列（縦）に対して、周囲（上、左、右、下）の一方向にランダムで壁を作成します。
このとき、壁を作ろうとしたところが既に壁になっている場合があります。
この対処法としては２通りあります。
１つはもう一度ランダムに方向を決定して、ぶつからないようにすることです。
この場合、ゴールまでの道のりが一通りしかない迷路ができあがります。
もう１つの方法は、壁を置くのをやめることです。
下図の例では２つ目の方法を採用しています。
■図３
- ▽ STEP 4
-
最後に、残った全ての基準点に対して、周囲の一方向にランダムで壁を作ります。
ですが、このときランダムに壁を作れる方向は（上、右、下）のみです。
左側に壁を作ってはいけません。
この方法で最後まで壁を作り終えたならば、迷路は完成です。
■図４
■図５：完成図
