hermemo-エルメモ-

迷路生成アルゴリズム – 穴掘り法 With MatLab

time 2018/02/06

迷路生成アルゴリズム – 穴掘り法 With MatLab

最近強化学習を勉強し始めました。その一歩目として、迷路の探索を学習させました。その際、迷路を作るのが面倒だったので、迷路自動生成アルゴリズムを実装してみたので、備忘録として。

sponsored link

はじめに

MatLab特有の書き方(関数)に慣れていないので、あまり使っていません。その為、最適ではないと思います。ただ、C等に変換しやすいのかなとも思います。

アルゴリズム

アルゴリズムに関してはAlgofulさんでわかりやすく紹介されています。その中でも今回は穴掘り法を実装しました。(特に理由はありません)

どのような手法かといいますと、ざっくり・・・

地図を壁で埋める。
1点を決めそこから通路を掘っていく。一度に二箇所掘ります。
右に掘りたい場合は右方向に2マスが壁である必要があります。上、下、左も同じ。
条件を満たした方向から掘る方向を適当に選んで、掘ります。後はコレの繰り返し。
掘れる方向がなくなった場合は始点を選び直して、同じことをします。

と言った感じでしょうか。他の方法やもっと詳しく知りたい方はぐぐってね。

ソースコード

Zipで固めています。

[DownLoad (AutoMakeMaze.m.zip)]

手で打ちたいという方はソースコードも貼っておきますね。

 

 

使い方

見ての通りfunction です。引数に迷路のサイズを渡してあげてください。ただし、迷路のサイズはx, y どちらも奇数である必要があります。

そうすると二次元配列で迷路が生成されます。迷路のスタート地点は左上(1, 1)、ゴール地点は右下(size_x, size_y) となります。

例) Maze = AutoMakeMaze(11, 11);

Maze という配列に11 x 11の迷路が生成されます。

基本的にアルゴリズムのまま実装していまので、解説は行いません。もし、気になることがある方は気軽にコメントください。随時解説していきたいと思います。

 

商品リンク

sponsored link

down

コメントする




*

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)



sponsored link