一．題目要求

參考下圖完成游戲地圖中從起點到目標點的最短路徑尋找問題。

二．設計思路

先對游戲地圖做了幾個設定，以矩陣來模擬游戲地圖。將可行的區域位置賦值0，障礙區賦值為inf。考慮到地圖大小，將起始點和終點區域賦值99。

從Start點A開始向外層擴展，每擴展一層pathlen加一。List Q存儲當前需要擴展的點，list P 存儲當前擴展層。當擴展到End點B時擴展結束，路徑可規劃。當Q為空時，本次層擴展結束，檢查P，若P非空，從P層向外擴展，若P為空，則End點B無法到達。

尋找最短路徑時，從End點B開始，尋找當前點附近8個點的標記中比當前點標記小的點，直到標記為1為止。

三．程序主體

# -*-coding:gbk -*-from numpy import *dirs = [(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1)] # 四鄰位置：從右下角開始順時針得到，是按坐標差得到的def find_path(oldmap,A,B): oldmap[A[0], A[1]] = 99 oldmap[B[0], B[1]] = 99 [a,b]=oldmap.shape pathmap=oldmap.copy() Q=[]#存儲擴展節點 P=[]#往外一層 pathlen=1 if A==B:  print('start point is equal to end point')  return True current=A while (True):  for i in range(8):   neighbor=[current[0]+dirs[i][0], current[1]+dirs[i][1]]   if neighbor==B:    print('the way is found')######################wrong    print('中間過程')    print(oldmap)    find_way(oldmap,pathmap,A,B,a,b)#####調用路徑函數    return True   if (neighbor[0]>=0 and neighbor[1]>=0 and neighbor[0]<a and neighbor[1]<b and oldmap[neighbor[0],neighbor[1]]==0):    P.append(neighbor)    oldmap[neighbor[0],neighbor[1]]=pathlen  if Q==[]:   if P ==[]:    print(oldmap) ##############    print('No path')    return False   else:    Q.extend(P)    P=[]    pathlen += 1  else:   current=Q.pop()###################尋找最短路徑def find_way(oldmap,pathmap,A,B,a,b): currentpos=B while (oldmap[currentpos[0],currentpos[1]]!=1):  for i in range(8):   neighborpos=[currentpos[0]+dirs[i][0], currentpos[1]+dirs[i][1]]   if (neighborpos[0] >= 0 and neighborpos[1] >= 0 and neighborpos[0] < a and neighborpos[1] < b and oldmap[neighborpos[0],neighborpos[1]]!=0):    if oldmap[neighborpos[0],neighborpos[1]]<oldmap[currentpos[0],currentpos[1]]:     pathmap[neighborpos[0],neighborpos[1]]=oldmap[neighborpos[0],neighborpos[1]]     currentpos=neighborpos     break print('the way:') print(pathmap)

 四．主函數

def main(): map =mat([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],    [0, 0, 0, 0, inf,inf, 0, 0, 0, 0, 0, 0, 0],    [0, 0, 0, 0, 0,inf, 0, 0, 0, 0, 0, 0, 0],    [inf,inf,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],    [0, 0,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0, inf],    [0, 0,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0, inf],    [0, 0,inf, 0, 0, 0, 0, 0, 0, 0, 0, 0,inf],    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, inf],    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],]) print('最初地圖') print(map) print('**********************************') A = [5, 0] # B=[5,0] B = [3, 12] find_path(map,A, B)if __name__=='__main__': main()