python游戲地圖最短路徑求解

更新時(shí)間：2019年01月16日 17:03:47 作者：北落師門XY

這篇文章主要為大家詳細(xì)介紹了python游戲地圖最短路徑的求解，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

一．題目要求

參考下圖完成游戲地圖中從起點(diǎn)到目標(biāo)點(diǎn)的最短路徑尋找問題。

二．設(shè)計(jì)思路

先對(duì)游戲地圖做了幾個(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é)果