Little Strange Software

スマホアプリの開発を行う LittleStrangeSoftware のブログです。

【JavaScript】自動生成迷路+最短正解ルート表示

 どうも!LSSです!!

 

もう4か月も前になりますか。

【JavaScript】続・自動生成迷路 - Little Strange Software

というスクリプトを書いていました。

 

タイトル通り、自動的に迷路を生成するスクリプトでしたが、生成して表示するだけのものでした。

で、今回はそれに「最短正解ルート」を自動的に割り出し、表示する機能をつけてみました!

 

 

自動生成迷路

幅:

高さ:

 

 

スライダーで幅と高さを調節するたびに、そのサイズに合った迷路が自動生成されます。

そして迷路の下にある「search」ボタンを押すと、最短正解ルートが瞬時に割り出されて表示されます!

 

 

最短正解ルートの割り出しアルゴリズム

再帰呼び出しによる、かなりベタな方法を用いています。

 

スタート地点の位置情報を調査用配列変数に入れ、その位置の「上下左右隣の4マス」について調査します。

「迷路の範囲内」であり、「間が壁ではなく通過可能」であり、「調査用配列変数に未登録の位置」

という条件が全て成立した場合のみ、その(元のマスの上下左右隣の)調査したマスの位置を、調査用配列変数の末尾につけたし。(と同時に移動前のマスがどれかも別途記録)

「上下左右隣の4マス」を処理し終えると、調査用配列変数の次の要素に移動し、またその「上下左右隣の4マス」を同様に調査…というのを、
「調査用配列変数に追加したものがゴールマスだった!」
という条件が成立するまで、延々と繰り返します。

 

ゴールマスに到達すると上記処理は終了し、今度は、
「ゴールマスから一歩づつ移動前マスに引き返し、スタート地点に辿りつくまで、マスを水色に塗りながら進む」
という処理を実行。

 

調査用配列変数には「スタート地点からの歩数が少ない順に」記録されるため、これで最短ルートが見つかった事になります^^

 

 

コード

やたら長いので、見たい方だけしてください。

 

 

あとがき

なんだか再帰呼び出しで何かプラグラムしてみたい病」が発症したので、やってみましたw

こうして迷路の走査に成功したので、例えば迷路を歩くスクリプトで、「一歩づつ上下左右をポチポチして進む」という操作性から、「5歩以内で移動可能な範囲を示し、その範囲内をクリックで移動する」というような、クリック回数が少なくて済む操作性を実現する事もできますね^^

 

あと、この正解ルート表示できるようにした事で、「正解ルートがほぼ対角線移動に偏りがち」という、既知の難点がより分かりやすくなりました^^;;;;;

 

 

 

ってなとこで、今回はこのへんで!

次回もまた、よろしくお願いします^^