黑松山资源网 Design By www.paidiu.com
一.题目要求
参考下图完成游戏地图中从起点到目标点的最短路径寻找问题。
二.设计思路
先对游戏地图做了几个设定,以矩阵来模拟游戏地图。将可行的区域位置赋值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对应的矩阵所示,是通过一种类似梯度下降的方法得到的。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月07日
2024年10月07日
- 群星.1991-音乐工厂1·皇后大道东【音乐工厂】【WAV+CUE】
- 群星.1992-音乐工厂2·首都【音乐工厂】【WAV+CUE】
- 群星.1994-音乐工厂3·儿童乐园【音乐工厂】【WAV+CUE】
- 胡鸿钧.2021-ex:CHANGE【星梦娱乐】【WAV+CUE】
- 班得瑞原装进口《第一张新世纪专辑:仙境》1CD[APE/CUE分轨][292.3MB]
- 伍佰《摇滚教父 伍佰黄金精选 2CD》[WAV+CUE][990MB]
- 班得瑞原装进口《第二张新世纪专辑:寂静山林》1CD[APE/CUE分轨][327.1MB]
- Beyond.1989-真的见证(2024环球MQA-UHQCD限量版)【环球】【WAV+CUE】
- 陈怡婷.2024-予你的心谁来赔【福茂】【FLAC分轨】
- 陈冠希.2003-HITS.OR.MISSES【英皇娱乐】【WAV+CUE】
- 班得瑞原装进口《第三张新世纪专辑:春野》1CD[APE/CUE分轨][278.9MB]
- 班得瑞原装进口《第四张新世纪专辑:蓝色天际》1CD[APE/CUE分轨][284.8MB]
- 班得瑞原装进口《第五张新世纪专辑:迷雾森林+EP》1CD[APE/CUE分轨][334.2MB]
- 田震.1997-顺其自然(日版)【红星生产社】【WAV+CUE】
- 小虫.1996-想得太美【滚石】【WAV+CUE】