A*寻路初学-_-
A星寻路是一种非常有趣的寻路算法。
相比较bfs与dfs它更具体更科学。
个人推荐讲的最清楚的一篇文章
http://www.gamedev.net/reference/articles/article2003.asp
以下是我学习时的一些理解
*地图中的每个节点 都有自己对于终点、起点的移动代价。
F = G + H
F 是成本总和
G = 从起点移动到指定方格的移动代价。
H = 从指定的方格移动到终点 B 的估算成本。
-------------------------------------------------------------------------------
1.我们会从终点开始进行遍历,把当前的节点放到open list。
添加节点相邻节点到open list 并且计算他们的代价。
如果发现更少代价，则更新值。
2.我们会从起点开始再次遍历，把每个节点再次放入open list。
添加相邻节点到open list 并且计算他们的代价。
如果发现更少代价，则更新值。
最后的路径是这么产生的：反复遍历 open list ，选择 F 值最小的方格。
-----------------------------------------------------------------------------------
这张图看了就能理解了
以当前节点看相邻节点(上下左右1步可达) 用 ‘+ 10’ 表示基础代价
以当前节点看 左下 右上 右下 左上 斜角节点时，用 ‘+14’ 计算基础代价
-为什么代价这么取值？
之所以，是因为实际的对角移动距离是 2 的平方根，或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的，我们避免了开放和小数的计算。
-我的python代码
# 定义节点类，节点类呢会有一些属性来区别自身与其他节点的区别
class Node:
def __int__(self):
self.unable = False
self.distanceFromDes = -1 # 距离终点的距离
self.distanceFromOri = -1 # 距离起点的距离
self.allDistance = -1 # 所有距离总和
self.added = False # 是否添加过
self.closed = False # 是否已经走过
self.parent = None # 上层节点是什么
self.x = -1 # 坐标位置 x轴
self.y = -1
# 2.生成地图 m长 n宽
def GenerateMap(m, n):
map = list()
for j in range(m):
nodeRow = list()
map.append(nodeRow)
for i in range(n):
node = Node()
node.y = j
node.x = i
node.unable = False
node.distanceFromDes = -1 # 距离终点的距离
node.distanceFromOri = -1 # 距离起点的距离
node.allDistance = -1
node.added = False
node.closed = False
node.parent = None
nodeRow.append(node)
return map
# 放置障碍物
def SetUnableMapNode(map, ls=()): # 要求一个坐标队列，里边的点上的Node的unable == True
for index in ls:
map[index[0]][index[1]].unable = True
return map
# # 添加终点，并计算每个节点与终点的距离
def GetDistanceFromDes(map, mapSize, endNode): # map二维数组，mapsize(m,n),desIndex终点坐标
# 这里再次对所有节点初始化 屬性為未添加
for ls in map:
for node in ls:
node.added = False
desNode = map[endNode[0]][endNode[1]]
# 終點與終點的距離肯定0
desNode.distanceFromDes = 0
# TODO ...
addedList = list() # 已经加入的队列，已有值distanceFromDes
needList = list() # 待加入的队列，需要评估值distanceFromDes
addedList.append(desNode) # 将终点节点加入到已添加列表
desNode.added = True # 更改终点节点的属性为已添加
while(len(addedList) != 0): # 当地图上所有可以遍历的点还没全确定
while(len(addedList) != 0): # 当一个大循环中，addedList还没被needList取代
# 从addedList中选出来的一个点，找needList中的needNode
mainNode = addedList.pop(0)
#print("main node:",mainNode)
# 主节点的距离是从addedList中拿出来的node距离终点的距离
mainDistanceFromDes = mainNode.distanceFromDes
y = mainNode.y
x = mainNode.x
print("mainDistanceFromDes:",mainDistanceFromDes)
print("y:",y)
print("x:",x)
for needNodey in (y + 1, y, y - 1):
# 超出的情况就忽略了
#print("needNodey:",needNodey)
if needNodey < 0 or needNodey >= mapSize[0]:
continue
for needNodex in (x + 1, x, x - 1):
#print("inner needNodex:",needNodey)
if needNodex < 0 or needNodex >= mapSize[1]:
continue
needNode = map[needNodey][needNodex] # 坐标不出界
if needNode.unable == True or needNode.added == True:
continue # 坐标也满足add的要求
yOffset = needNodey - y
xOffset = needNodex - x
allOffset = yOffset + xOffset
print("yOffset:",yOffset,"xOffset:",xOffset,"allOffset=",allOffset)
if allOffset == 1 or allOffset == -1:
distanceFromDes = mainDistanceFromDes + 1
elif allOffset == -2 or allOffset == 0 or allOffset == 2:
distanceFromDes = mainDistanceFromDes + 1.4
else:
print("终点代价计算错误")
if needNode in needList: # 设置needNode的距离，要求最小
if distanceFromDes < needNode.distanceFromDes:
needNode.distanceFromDes = distanceFromDes
else: # needNode 不在needList中 distanceFromDes一定是-1
needNode.distanceFromDes = distanceFromDes
needList.append(needNode)
# print(needNode.y,needNode.x,needNode.distanceFromDes)
# needList 装满了 addedList排空了
addedList = needList
for node in addedList:
node.added = True
needList = list()
return map
# # 添加起点，并生成起点到终点的节点队列
def GetMinDistanceNodeList(map, mapSize, oriIndex, desIndex):
for ls in map:
for node in ls:
node.added = False
openedList = list()
node = map[oriIndex[0]][oriIndex[1]]
node.distanceFromOri = 0
node.allDistance = 0
openedList.append(node)
node.added = True
while len(openedList) != 0:
# 从openlist拿出一个节点
node = openedList.pop(0)
# 标示为close过
node.closed = True
if node.y == desIndex[0] and node.x == desIndex[1]:
finalListNeedReverse = list()
while node != None:
finalListNeedReverse.append(node)
node = node.parent
finalListNeedReverse.reverse()
return finalListNeedReverse
neighboursList = list()
y = node.y
x = node.x
parentDistanceFromOri = node.distanceFromOri
for needNodey in (y + 1, y, y - 1):
if needNodey < 0 or needNodey >= mapSize[0]:
continue
for needNodex in (x + 1, x, x - 1):
if needNodex < 0 or needNodex >= mapSize[1]:
continue
needNode = map[needNodey][needNodex] # 坐标不出界
if needNode.unable == True or needNode.closed == True or needNode.added == True:
continue # 坐标也满足add的要求
yOffset = needNodey - y
xOffset = needNodex - x
allOffset = yOffset + xOffset
if allOffset == 1 or allOffset == -1:
distanceFromOri = parentDistanceFromOri + 1
elif allOffset == -2 or allOffset == 0 or allOffset == 2:
distanceFromOri = parentDistanceFromOri + 1.4
else:
print("终点代价计算错误")
if needNode in neighboursList: # 设置needNode的距离，要求最小
if distanceFromOri < needNode.distanceFromOri:
needNode.distanceFromOri = distanceFromOri
else: # needNode 不在needList中 distanceFromDes一定是-1
needNode.distanceFromOri = distanceFromOri
neighboursList.append(needNode) # 距离计算完成
for needNode in neighboursList: # 开始添加至openedList
needNode.parent = node
needNode.allDistance = needNode.distanceFromOri + needNode.distanceFromDes
needNode.added = True
openedList.append(needNode)
# print(needNode.x,needNode.y,needNode.allDistance)
openedList.sort(key=lambda x: x.allDistance) # 最小距离的排在前边
print("无路可循!")
return None
# 打印具体的方向
def TestGetMinDistanceNodeList(map, mapSize, oriIndex, desIndex):
finalList = GetMinDistanceNodeList(
map, mapSize, oriIndex, desIndex) # 添加起点，并生成起点到终点的节点队列
# 行动路线
directions = (('↘', '↓', '↙'), ('→', "S", '←'), ('↗', '↑', '↖'))
print('行动路线示意')
for nodeRow in map:
for node in nodeRow:
if node in finalList:
#print(' * ',end ='')
parent = node.parent
if parent != None:
if node.y != desIndex[0] or node.x != desIndex[1]:
(y, x) = (parent.y - node.y+1, parent.x - node.x+1)
print(' '+directions[y][x]+' ', end='')
else:
print('Final', end='')
else:
print('Start', end='')
else:
if node.allDistance != -1:
print('{:^4.1f}'.format(node.allDistance), end=" ")
else:
print(' X ', end=" ")
print()
print()
def aStartGo(startNode=(4,6),endNode=(0,0)):
"""
两个参数分别为起点和终点节点的坐标
"""
m = 5 # 设置地图的长
n = 7 # 设置地图的宽
map = GenerateMap(m, n) # 2.生成地图节点
# for nodeRow in map:
# for node in nodeRow:
# print("(",node.y,",",node.x,")",end=" ")
# 放的障碍物位置
obstacleList = [(4, 3),(3,3),(2,3),(0,1),(1,1),(2,1)]
map = SetUnableMapNode(map, obstacleList) # 在地图中添加障碍
# 添加终点，并计算节点与终点的距离(代价)
GetDistanceFromDes(map, (m, n), endNode)
print("-------------------------------------")
# 先打印一下所有节点的到终点的代价，总所周知终点自己到自己是没有代价的，上下左右的一次代价为10
for nodeRow in map:
for node in nodeRow:
if node.distanceFromDes != -1:
print('{:^5.1f}'.format(node.distanceFromDes), end=" ")
#print('{:.2f}'.format(node.distanceFromDes), end=" ")
else:
print(' X ', end=" ")
print()
TestGetMinDistanceNodeList(
map, (m, n), startNode, endNode) # 终点距离测试完了，演示行动路线
#运行a*
aStartGo()
我的示例代码中,地图是 5 * 7 的，其中 startNode=(4,6),endNode=(0,0)
看看我打印的结果把
