今回は迷路の探索法の一つである「深さ優先探索」に挑戦してみました。
プログラミングを組んでいく段階〜実行結果まで詳しく説明します!
使用したものはPython3です。
深さ優先探索
まずそもそも深さ優先探索って何?ってことなんですけど、ネットにたくさん載っていたので、例として一つ載せておきます。そちらをご覧ください!
ソースコード
ソースコードは以下の記事に載せています。
目的
キャラが「深さ優先探索」でゴールする
使用したもの
・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)
実行結果
ソースコードは以下の記事から