【VBA】穴掘り法で迷路を自動生成

VBA

迷路を自動で生成してみる

 

以前、Excelのシートに入力した文字を迷路に見立てて
幅優先探索で迷路を解くプログラムをVBAで作成しました。

【VBA】迷路を解く
VBAで迷路を解いてみよう! 今回はPythonで習ったアルゴリズムをVBAに使用して迷路を解いてみたいと思います。

前回のプログラムでは迷路を手動で入力する必要がありました。
大きいサイズの迷路を作成するのは大変なので、自動で迷路を作成する方法を探してみました。

 

穴掘り法

迷路を作成するアルゴリズムで「穴掘り法」というものがあるので
今回は「穴掘り法」アルゴリズムを使用して、VBAで迷路を作成してみます。

穴掘り法アルゴリズムは下記のページの内容を参考にさせていただきました。

穴掘り法
迷路生成(穴掘り法) - Algoful
穴掘り法は迷路生成アルゴリズムの一種です...

迷路を解くアルゴリズムと組み合わせると、迷路の生成から迷路の解決まで一気にできます。

迷路作成プログラムの作成

実装内容

以下の内容で実装してみます。

  • mazeという名前のシートに迷路を作成する。
    スタート位置とゴール位置の自動生成はしない。

S スタート位置です。今回は生成しません。
G ゴール位置です。今回は生成しません。
空白 通ることができます。
# 壁なので通ることができません。
  • 正方形の迷路を生成する。長方形や矩形の迷路は生成しない。
  • 迷路のサイズを入力できるインプットボックスを表示する。
    入力する数値は5以上99以下の奇数とする。

    • 数値のサイズが大きいとスタック領域不足エラーが発生するため99以下としました。

 

コード

VBAの穴掘り法のコードは以下になります。

穴掘り法で壁を壊す方向をランダムに決める必要があったので
東西南北の方角を配列に格納し、配列をシャッフルして破壊方向をランダムに出してます。

配列をシャッフルする関数は以下のサイトを参考にさせていただきました。

VBAで配列をシャッフルする(要素をランダムに並べ替える)
VBAでも配列の要素をランダムに並べ替えたいときがあります。 そんなときはランダム関数を使って配列の中をシャッフルする関数を作ってしまいましょう。 スポンサーリンク AdSense Responsiv

 

穴掘り法で迷路を生成してみる

createMazeを実行するとインプットボックスが表示されます。
5~99以外の数値や文字を入力するとエラーになります。

15を入力してOKを押してみます。

 

「迷路作成の途中経過を表示しますか?」とメッセージボックスが表示されます。

「はい」を押すと迷路の作成経過をmazeシートに表示します。
迷路のサイズが大きいと表示処理に時間がかかるので注意してください!

「いいえ」を押すと、作成経過を表示せず迷路を表示します。

迷路の作成が完了すると完了メッセージが表示されます。

 

迷路作成後、SとGの文字をシートに書き込みます。
以前作成した迷路を探索するアルゴリズムを使用すると
スタートからゴールまでの経路を表示します。

 

エラー

実行時エラー’28’:スタック領域が不足しています

迷路作成時に再帰処理を行っているため、スタックの容量を超えてしまうとエラーが発生します。
この場合はインプットボックスに入力する迷路のサイズを小さくしてみてください。

コメント