迷路を波状探索で解く

迷路を幅優先探索で解く」「迷路を深さ優先探索で解く」に続く第3弾です。

幅優先でも深さ優先でもないアルゴリズムで迷路を解いています。

ここで示したアルゴリズムはあるサイトで見つけたものなのだと思うのですが、この迷路プログラムの原型は、数年前に 書いたものなので、それがどこのサイトなのかがわからなくなってしまいいました(T T)。
そのためこのアルゴリズムの名前もわかりません。 ここでは、勝手に波紋探索という名前を付けました。

どうやって経路を求めていくかというと、次のよう手順となります。

  1. スタート地点に番号 0 を振ります。0 は歩数を表します。現在の歩数に 0を代入します。
  2.  次に進めるすべての位置に 現在の歩数 + 1を振ります。 この時すでに番号が振られている位置には、番号を振り直すことはしません。
  3.  現在の歩数 に +1 します。
  4. 現在の歩数が振られたすべての位置について、2,3 の処理を行います。
  5. ゴールにたどり着いたら終了です。

経路は、ゴールから逆にたどっていくことで得られます。 逆順に辿る際に、同じ番号が現れた場合はどちらを辿っても構いません。

小さな迷路でその実行過程を示します。 DebugPrintというメソッドを用意しているので、このメソッドを途中で呼び出した ものを2つほど載せておきます。

数字が迷路を辿る順序を示しています。0がスタート地点です。 イメージがつかめると思います

***************************************************
 0  1 ***   ***      ***                        ***
*** 2 *********************   ***************   ***
*** 3  4  5  6                ***               ***
*** 4 ***************************   ******   ******
*** 5  6    ***                                 ***
*********************      ***   ******************
***                        ***                  ***
***************************************************
***************************************************
 0  1 ***   ***      ***14 13 14 15 16 17 18 19 ***
*** 2 *********************12 ***************20 ***
*** 3  4  5  6  7  8  9 10 11 ***25 24 23 22 21 ***
*** 4 ***************************26 ******23 ******
*** 5  6  7 ***         30 29 28 27 26 25 24 25 ***
*********************      ***29 ******************
***                        ***30                ***
***************************************************

数字が歩数を示しています。6歩までと30歩まで進んだところを示しいています。
実際に確かめてはいませんが、この探索方法は解を得るまでの時間が安定していると予想されます。

実行結果を2つほど示します。



以下C#のコードです。

  

 「迷路を幅優先探索で解く」「迷路を深さ優先探索で解く」同様、以下のようなテキストファイルをこのプログラムに読み込ませれば、解を表示してくれます。

■テストデータ1
******************************
S *     *     *              *
* * * *** ***** ************ *
* * * * *  * ** *        * * *
* * * * *  * ** * *** *  * * *
*   *           * *   *      *
***************** ***** ******
*                     *    * G
*** ********* ************** *
*    * * *       *           *
* **** * * ***** *** **** ****
*      * * *   * *   *     * *
***  * * * ***** *** ******* *
*    *   *       *         * *
* ***************** **** * * *
*     *      *      *  * * * *
* ***** **** * **** **** * * *
*       *      *         *   *
******************************

■テストデータ2
*S*****************************
*   *                   *     *
*** ******* ***** * *** *** * *
*         * *   * *   *     * *
***** *** * *** * *** *** *****
*   * *   *     *       *     *
*** * *** * * *** * * ******* *
*     *   * *   * * *   *     *
*** ***** *** * * * *** * *****
*     *         * * *   *   * *
* *********** ********* ***** *
* * *   *   * *   *     *     *
* *** * * *** * *** ***** *** *
*     *     *   *     *     * *
* ********* ********* * ***** *
* *   *     *         * *     *
* * ******* *** ******* *** ***
* * * *   * *   * *     * *   *
*** * * *** * *** * * *** * * *
*           *       *     * * *
*****************************G*