您好,登錄后才能下訂單哦!
一.題目要求
參考下圖完成游戲地圖中從起點(diǎn)到目標(biāo)點(diǎn)的最短路徑尋找問題。
二.設(shè)計(jì)思路
先對游戲地圖做了幾個(gè)設(shè)定,以矩陣來模擬游戲地圖。將可行的區(qū)域位置賦值0,障礙區(qū)賦值為inf。考慮到地圖大小,將起始點(diǎn)和終點(diǎn)區(qū)域賦值99。
從Start點(diǎn)A開始向外層擴(kuò)展,每擴(kuò)展一層pathlen加一。List Q存儲(chǔ)當(dāng)前需要擴(kuò)展的點(diǎn),list P 存儲(chǔ)當(dāng)前擴(kuò)展層。當(dāng)擴(kuò)展到End點(diǎn)B時(shí)擴(kuò)展結(jié)束,路徑可規(guī)劃。當(dāng)Q為空時(shí),本次層擴(kuò)展結(jié)束,檢查P,若P非空,從P層向外擴(kuò)展,若P為空,則End點(diǎn)B無法到達(dá)。
尋找最短路徑時(shí),從End點(diǎn)B開始,尋找當(dāng)前點(diǎn)附近8個(gè)點(diǎn)的標(biāo)記中比當(dāng)前點(diǎn)標(biāo)記小的點(diǎn),直到標(biāo)記為1為止。
三.程序主體
# -*-coding:gbk -*- from numpy import * dirs = [(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1)] # 四鄰位置:從右下角開始順時(shí)針得到,是按坐標(biāo)差得到的 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=[]#存儲(chǔ)擴(kuò)展節(jié)點(diǎn) 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)#####調(diào)用路徑函數(shù) 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)
四.主函數(shù)
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()
五.運(yùn)行結(jié)果
六.結(jié)果分析
由中間過程對應(yīng)的矩陣可知,共經(jīng)歷了12次向外層擴(kuò)展,第12次擴(kuò)展即可將目標(biāo)點(diǎn)包含進(jìn)去。最短路徑如the way對應(yīng)的矩陣所示,是通過一種類似梯度下降的方法得到的。
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。