< currentNode.g:# 如果更小 ， 就重新计算g值 ， 并且改变fathercurrentNode.g = minF.g + stepcurrentNode.father = minFdef start(self):"""开始寻路:return: None或Point列表（路径）"""# 判断寻路终点是否是障碍if self.map2d[self.endPoint.x][self.endPoint.y] != self.passTag:return None# 1.将起点放入开启列表startNode = AStar.Node(self.startPoint, self.endPoint)self.openList.append(startNode)# 2.主循环逻辑while True:# 找到F值最小的点minF = self.openList[0]# 把这个点加入closeList中 ， 并且在openList中删除它self.closeList.append(minF)self.openList.remove(minF)# 判断这个节点的周边8个节点self.searchNear(minF, 0, -1)self.searchNear(minF, 0, 1)self.searchNear(minF, -1, 0)self.searchNear(minF, 1, 0)self.searchNear(minF, -1, -1)self.searchNear(minF, 1, 1)self.searchNear(minF, -1, 1)self.searchNear(minF, 1, -1)# 判断是否终止point = self.endPointInCloseList()if point:# 如果终点在关闭表中 ， 就返回结果# print("关闭表中")cPoint = pointpathList = []while True:if cPoint.father:pathList.append(cPoint.point)cPoint = cPoint.fatherelse:pathList.append(self.startPoint)# print(pathList)# print(list(reversed(pathList)))# print(pathList.reverse())return list(reversed(pathList))if len(self.openList) == 0:return Noneif __name__ == '__main__':# 创建一个10*10的地图map2d = Array2D(10 , 10)# 设置障碍map2d[0][3] = 1map2d[1][3] = 1map2d[2][3] = 1map2d[3][3] = 1map2d[2][5] = 1map2d[3][5] = 1map2d[4][5] = 1map2d[5][5] = 1map2d[6][5] = 1map2d[2][7] = 1map2d[3][7] = 1map2d[4][7] = 1map2d[5][7] = 1map2d[7][7] = 1map2d[8][7] = 1map2d[9][7] = 1map2d[5][1] = 1map2d[5][2] = 1map2d[5][3] = 1map2d[5][4] = 1# 显示地图当前样子map2d.showArray2D()# 创建AStar对象,并设置起点为0,0终点为9,0aStar = AStar(map2d, Point(2,1), Point(0,9))# 开始寻路pathList = aStar.start()# 遍历路径点,在map2d上以'8'显示for point in pathList:map2d[point.x][point.y] = 8# print(point)print()print("----------------------")print()# 再次显示地图map2d.showArray2D()
2.一些解释说明
代码部分并非个人独立完成, 主体结构来自于下面的文章
关键在于个人对其代码的修改部分, 有四个部分
一是算法实现部分, 他的代码其实没有完整实现那篇参考的算法文章,
具体在于self.变量的改动, 在函数中 ,其实应该也不需要这样改,只是在算法参考文章中, 最好选择F值最小的那个要求 , 我希望能降一点时间复杂度, 直接获取self.[0], 即最小F值元素. 同时删掉了函数
以及对于当前位置周边的8个位置的探索 ,而不是仅仅局限于上下左右四个位置, 以至于无法形成斜边的路径, 也许作者是想使得路径不能有斜边吧, 可是这样那数字14的出现没有多大意义啊.
另外就是,对于算法参考的那篇文章, 墙角部分,大家可以自己去实现一下哦
二是对于显示的符号的改动,更加直观
三是对于行列的描述部分, 修改后 w为列 , h为行, 本来想直接修改变量名的,但是其实也无伤大雅吧.
四是对于打印的链, 我增加了打印的起点
下面是对应修改的算法代码部分
# 如果不在openList中 ， 就把它加入openlist ,并且使得openlist的首元素为f值最小的currentNode = self.pointInOpenList(currentPoint)if not currentNode:currentNode = AStar.Node(currentPoint, self.endPoint, g=minF.g + step)currentNode.father = minFfor item in self.openList:if item.g+item.h > currentNode.g+currentNode.h:self.openList.insert(self.openList.index(item), currentNode)breakif self.openList.count(currentNode) == 0:self.openList.append(currentNode)return
# 判断这个节点的周边8个节点self.searchNear(minF, 0, -1)self.searchNear(minF, 0, 1)self.searchNear(minF, -1, 0)self.searchNear(minF, 1, 0)self.searchNear(minF, -1, -1)self.searchNear(minF, 1, 1)self.searchNear(minF, -1, 1)self.searchNear(minF, 1, -1)