溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一．題目要求
參考下圖完成游戲地圖中從起點到目標點的最短路徑尋找問題。
二．設計思路
先對游戲地圖做了幾個設定，以矩陣來模擬游戲地圖。將可行的區域位置賦值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()
五．運行結果
六．結果分析
由中間過程對應的矩陣可知，共經歷了12次向外層擴展，第12次擴展即可將目標點包含進去。最短路徑如the way對應的矩陣所示，是通過一種類似梯度下降的方法得到的。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
