naohcodes/mazegenerator-java-2d-gui

迷路自動生成プログラム（2DGUI, 最短経路解表示もできる！）

MazeGenerator-Javaの迷路自動生成プログラムを利用してGUI化しました。

前提, 使用環境

Java : jdk-17
GUI : JavaFX
IDE : Eclipse IDE

SceneBuilder（FXML）の利用でリッチなGUIを手軽に作成できますが、今回は使用せずJavaのみでデザインまで行っています。
実行するにはJavaFXを実行できる環境が必要です。

説明

・迷路（2次元）の自動生成プログラム
・縦のマス数と横のマス数を指定できる
・501×501の迷路を3秒程度で生成できる
・タイトル画面と迷路画面の画面遷移ができる

実行方法（JavaFXの設定していないけど実行したい人用）

jarファイルにまとめたので、おいてあるMazeGenerator実行用ファイル内のReadme.txt通りに実行すればよいです。

実行写真

タイトル画面

縦マス数と横マス数を入力して、「迷路生成」ボタンをクリックすると迷路が生成されます。
縦マス数と横マス数は5以上の奇数である必要があります。異なる値でも大丈夫ですが、不格好になるので近い値にしたほうがいいです。

迷路生成した画面

写真は11×11です。壁やスタート、ゴールの角が丸まっていますが、内部変数の値を変更すれば丸まり具合を調整できます。

最短経路を表示した画面

「最短経路を表示する」ボタンを押すと最短経路が表示されます。 青で表示したルートが最短経路です。
ルートの計算方法は、スタートからの幅優先でそれぞれのマスへの最小マス数を求め、ゴールから逆探索で最短経路を出しています。

おまけ

501×501で生成するとこんな感じになります。
実行時間は3秒くらいです

課題

迷路生成を壁伸ばし法（参考資料欄を参照のこと）を利用しているので、自分の壁と接続しないために伸ばしている壁をスタックで管理しているが、 管理数が多くなるとStackOverflowErrorが発生する。
これを回避するためにスタックの最大数を7（経験的にこれくらいが妥当だと思う）に設定しているが、これによりまだ伸ばせる壁を途中で中断する ことになり、501×501の画像に見るように直線に近い道が最短経路となってしまう。

参考資料

迷路生成アルゴリズム（壁伸ばし法）： Algoful 様（https://algoful.com/Archive/Algorithm/MazeExtend）
画面遷移　：　のんぽぐ 様（https://nompor.com/2018/01/16/post-2683/）