一．题目要求
参考下图完成游戏地图中从起点到目标点的最短路径寻找问题。
二．设计思路
先对游戏地图做了几个设定，以矩阵来模拟游戏地图。将可行的区域位置赋值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对应的矩阵所示，是通过一种类似梯度下降的方法得到的。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
python,最短路径
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。