pythonによる迷路の自動探索　深さ優先探索編

f:id:hiro-htm877:20190511223954p:plain

今回は迷路の探索法の一つである「深さ優先探索」に挑戦してみました。

プログラミングを組んでいく段階〜実行結果まで詳しく説明します！

使用したものはPython３です。

深さ優先探索

まずそもそも深さ優先探索って何？ってことなんですけど、ネットにたくさん載っていたので、例として一つ載せておきます。そちらをご覧ください！

proglight.jimdo.com

qiita.com

目的

キャラが「深さ優先探索」でゴールする

使用したもの

・python2.7

では、実験！

コード解説

ソースコード

１.　while文

###ゴールするまで進む
while(Px != x2 or Py != y2):

ゴールの座標＝（x2, y2）

に到達するまで進み続けます。

###壁に突き当たるまで進む
    while(1):

壁に突き当たったらbreak文でwhileを抜け、ゴールかどうかを判定する。

壁の判定は以下の通りです。

 ###壁判定
        if len(preposi_Index) > 0:
            nextposi = preposi_Index[0]
        else:    ###壁に突き当たった時
            Px, Py = x, y
            branch_road_stack_flag = True
            intersection_delete_flag =True     
            break

preposi_index（次に動ける場所）がない場合、壁に突き当たったとする。

Py, Px = x, y　で突き当たった位置を現在地として、リスタートさせる。

flagのTrueは壁に突き当たった時点で初期化、次の交差点まで真っ直ぐ進ませる。

現在地周囲の座標取得、進み方

まず、今回の探索では後ろに進むことはないとする。

その上で、現在地の座標（x, y）と一つ前の座標（Px, Py）から次に進める座標を取得し、一つ選択して進む。

関数prepositionで進める場所＝０、進めない場所＝１が配列で返ってきます。なので、preposi_indexに進める場所（０）のindexを格納してます。

※関数prepositionで返ってくる配列は長さ４で[右, 左, 下, 上]の各要素が０なら進めない、１なら進めるとなっています。例：[0, 1, 1, 1]⇨右にだけ進める

#現在地の前３つの座標を取得

        preposi = presentposition(x, y, Px, Py)
        print ("preposi", preposi)
        #進める場所のみを抽出
        preposi_Index = [i for i, j in enumerate(preposi) if j == 0]
        print ("preposi_Index", preposi_Index)

実際に進む処理は、while(1)の最後に書かれている以下のコードです。

まず、現在地を一つ前の座標に保管し、nextposiの値によって変化し、現在地の座標を変えることで進みます。

 Px, Py = x, y
        ###進む処理
        if nextposi == 0:
                x += 1 #右に１進む
        elif nextposi == 1:
                x -= 1 #左に１進む
        elif nextposi == 2:
                y += 1 #下に１進む
        elif nextposi == 3:
                y -= 1 #上に１進む
        print("x, y", x, y)

交差点検知

コードは以下の通りです。

###交差点検知
        intersection_detect = preposi.count(0)
        print ("intersection_detect", intersection_detect)
        if  intersection_detect > 1:
            print ("ここは交差点です")
            print(preposi)
            print (preposi_Index)
            intersection_posi = (x, y)
            if branch_road_stack_flag == True:
                print("----test----")
                print (branch_road_stack)
                branch_road_stack.pop(0)
                print ( branch_road_stack)
                branch_road_stack_flag = False
                print(maze)
                print(Px, Py)
                maze[Py][Px] = 1
                print(maze)
                print(x, y)
            else:
                ###スタックに状態を追加
                for i in preposi_Index:
                    if i == 0:
                        branch_road_stack.insert(0, (x+1, y))
                    elif i == 1:
                         branch_road_stack.insert(0, (x-1, y))
                    elif i == 2:
                         branch_road_stack.insert(0, (x, y+1))
                    elif i == 3:
                         branch_road_stack.insert(0, (x, y-1))
            print ("branch_road_stack", branch_road_stack)
            Px, Py = x, y
            x, y = branch_road_stack[0]
            break

preposi(現在地の周囲)の０（進める場所を）カウントし、１より大きかったら交差点とみなしています。交差点と分かると次は、分かれ道の座標を格納していきます。ただし、同じ交差点に２回きた時に同じ情報を格納してしまうのを防ぐためにbranch_road_flagを用いて制御しています。また、branch_road_flag＝＝Trueの中では、２度目に交差点に来た、つまり探索が終わった分かれ道をmaze[Py][Px]=1で通行止にしています。