import?numpy?as?np
import?time

f?=?open（“openMaze.txt““r“）
#f?=?open（“mediumMaze.txt““r“）
list?=?[]
line?=?f.readline（）
while?line:
????line=line.strip（‘\n‘）
????#print（line）
????list.append（line）
????line?=?f.readline（）
????
f.close（）
hang?=?len（list）
lie?=?len（list[1]）

maze?=?np.zeros（（hanglie）dtype?=?np.int）
for?i?in?range（hang）:
????for?j?in?range（lie）:
????????if?list[i][j]?==?‘%‘:
????????????maze[i][j]?=?1
????????elif?list[i][j]?==?‘?‘:
????????????maze[i][j]?=?0
????????elif?list[i][j]?==?‘.‘:#終點(diǎn)用2表示
????????????maze[i][j]?=?2
????????elif?list[i][j]?==?‘P‘:#起點(diǎn)用3表示
????????????maze[i][j]?=?3

###############初始化標(biāo)記數(shù)組
mark?=?np.zeros（（hanglie）dtype?=?np.int）
for?i?in?range（len（maze））:
????for?j?in?range（len（maze[i]））:
????????if?maze[i][j]?==?2:
????????????endx?=?i
????????????endy?=?j
????????if?maze[i][j]?==?3:
????????????startx?=?i
????????????starty?=?j

#################初始化迷宮的四種方向走法
next_step?=?[[01]???????#向右走
??????????????[10]??????#向下走
??????????????[0-1]?????#向左走
???????????????[-10]]

#定義啟發(fā)函數(shù)
def?function（xy）:
????return?abs（endx?-?x）+abs（endy?-?y）
?
parent?=?np.zeros（（hanglie）dtype?=?int）
cost_so_far?=?np.zeros（（hanglie）dtype?=?int）
open?=?[]
closed?=?[]
F?=?[]
total_explore?=?0?####記錄總的探索的節(jié)點(diǎn)數(shù)

cost_so_far[startx][starty]?=?0
open.append（[startxstarty]）
F.append（0）
flag?=?0???#flag等于1表示到達(dá)終點(diǎn)，否則表示沒有到達(dá)

###############算法開始
starttime?=?time.time（）????#記錄開始時(shí)間
while（len（open）?!=?0）:
????????index?=?F.index（min（F））
????????current?=?open[index]
????????del?open[index]
????????del?F[index]
????????closed.append（current）
????????current_x?=?current[0]
????????current_y?=?current[1]
????????for?i?in?range（len（next_step））:
????????????next_x?=?current_x?+?next_step[i][0]
????????????next_y?=?current_y?+?next_step[i][1]
????????????
????????????next?=?[next_xnext_y]
????????????f?=?9*function（next_xnext_y）?+?cost_so_far[current_x][current_x]?+?1
????????????if（next_x??len（maze）?or?next_y?>?len（maze[0]））:
????????????????continue
????????????if（next?in?closed）:
????????????????continue
????????????if（next?in?open）:
????????????????same_index?=?open.index（next）
????????????????same_f?=?F[same_index]
????????????????if（f?????????????????????F[same_index]?=?f
????????????????????parent[next_x][next_y]?=?i
????????????????????cost_so_far[next_x][next_y]?=?cost_so_far[current_x][current_y]?+?1
????????????????????continue
????????????????else:
????????????????????continue
????????????if（maze[next_x][next_y]?==?0）:
????????????????parent[next_x][next_y]?=?i
????????????????open.append（[next_xnext_y]）
????????????????F.append（f）
????????????????total_explore?+=?1????????######每當(dāng)有一個(gè)節(jié)點(diǎn)加入open集當(dāng)中，總的探索的節(jié)點(diǎn)數(shù)加1
????????????????cost_so_far[next_x][next_y]?=?cost_so_far[current_x][current_y]?+?1

????????????if（next_x?==?endx?and?next_y?==?endy）:
????????????????flag?=?1
????????????????break

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????文件????????4812??2019-06-02?20:27??A_star.py
?????文件????????1447??2019-05-16?17:09??mediumMaze.txt
?????文件?????????778??2019-05-16?17:09??openMaze.txt