人工知性を作りたい

私が日々、挑戦したことや学んだことなどを紹介していく雑記ブログです。 (新しいAI技術HTM, 専門の音声信号処理, 趣味のアニメ等も書いてます。)

global navigation menu page top

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

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





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

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

使用したものはPython3です。

 

 

深さ優先探索

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

proglight.jimdo.com

 

qiita.com

 

 

 

ソースコード

ソースコードは以下の記事に載せています。

www.hiro877.com

 

 

目的

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

 

使用したもの

・python2.7

 

では、実験!

 

コード解説

ソースコード 

1. 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で進める場所=0、進めない場所=1が配列で返ってきます。なので、preposi_indexに進める場所(0)のindexを格納してます。

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

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

        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 #右に1進む
        elif nextposi == 1:
                x -= 1 #左に1進む
        elif nextposi == 2:
                y += 1 #下に1進む
        elif nextposi == 3:
                y -= 1 #上に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(現在地の周囲)の0(進める場所を)カウントし、1より大きかったら交差点とみなしています。交差点と分かると次は、分かれ道の座標を格納していきます。ただし、同じ交差点に2回きた時に同じ情報を格納してしまうのを防ぐためにbranch_road_flagを用いて制御しています。また、branch_road_flag==Trueの中では、2度目に交差点に来た、つまり探索が終わった分かれ道をmaze[Py][Px]=1で通行止にしています。

 

 

実験結果・ソースコード(jupyter notebook) 

実行結果


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

 

 

ソースコードは以下の記事から 

www.hiro877.com