一．题目要求
参考下图完成游戏地图中从起点到目标点的最短路径寻找问题。
二．设计思路
先对游戏地图做了几个设定，以矩阵来模拟游戏地图。将可行的区域位置赋值0，障碍区赋值为inf。考虑到地图大小，将起始点和终点区域赋值99。
从start点a开始向外层扩展，每扩展一层pathlen加一。list q存储当前需要扩展的点，list p 存储当前扩展层。当扩展到end点b时扩展结束，路径可规划。当q为空时，本次层扩展结束，检查p，若p非空，从p层向外扩展，若p为空，则end点b无法到达。
寻找最短路径时，从end点b开始，寻找当前点附近8个点的标记中比当前点标记小的点，直到标记为1为止。
三．程序主体
python" id="highlighter_658761">
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
# -*-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) |
四．主函数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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对应的矩阵所示，是通过一种类似梯度下降的方法得到的。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/weixin_41819299/article/details/80840286
