A*（A星）算法python实现
# 在春节放假前两天我偶然看到了A*算法，感觉挺有意思。正好放假前# 也没有什么事情，就花了一个下午写出算法的骨架，节后又花了半天# 时间完善屏幕输出的细节并且调试完成。
# 该实现只是一时兴起的随手而作，没有考虑性能和扩展性等问题。正# 在学习A*的朋友可以拿去随便折腾。
#email:************************
import sys
_2dmap = []
start = None
end = None
open_list = {}
close_list = {}
map_border = ()
class Node:
def __init__(this, father, x, y):
if x 0 or x = map_border[0] or y 0 or y = map_border[1]:
raise Exception( node position can’t beyond the border! )
this.father = father
this.x = x
this.y = y
if father != None:
G2father = calc_G(father, this)
if not G2father:
raise Exception( father is not valid! )  this.G = G2father + father.G
this.H = calc_H(this, end)
this.F = this.G + this.H
else:
this.G = 0
this.H = 0
this.F = 0
def reset_father(this, father, new_G):  if father != None:
this.G = new_G
this.F = this.G + this.H
this.father = father
def calc_G(node1, node2):
x1 = abs(node1.x-node2.x)
y1 = abs(node1.y-node2.y)
if (x1== 1 and y1 == 0):
return 10 # same row
if (x1== 0 and y1 == 1):
return 10 # same col
if (x1== 1 and y1 == 1):
return 14 # cross
else:
return 0
def calc_H(cur, end):
return abs(end.x-cur.x) + abs(end.y-cur.y)
# NOTE 这个地方可能成为性能瓶颈
def min_F_node():
if len(open_list) == 0:
raise Exception( not exist path! )
_min = 9999999999999999
_k = (start.x, start.y)
for k,v in open_list.items():
if _min v.F:
_min = v.F
_k = k
return open_list[_k]
exist什么意思# 把相邻节点加入open list, 如果发现终点说明到了路径def addAdjacentIntoOpen(node):
# 将该节点从开放列表移到关闭列表当中。
open_list.pop((node.x, node.y))
close_list[(node.x, node.y)] = node
_adjacent = []
# 相邻节点要注意边界的情况
try:
_adjacent.append(Node(node , node.x - 1 , node.y - 1))  except Exception,e:
pass
try:
_adjacent.append(Node(node , node.x , node.y - 1))
except Exception,e:
pass
try:
_adjacent.append(Node(node , node.x + 1 , node.y - 1))  except Exception,e:
pass
try:
_adjacent.append(Node(node , node.x + 1 , node.y))
except Exception,e:
pass
try:
_adjacent.append(Node(node , node.x + 1 , node.y + 1))  except Exception,e:
pass
try:
_adjacent.append(Node(node , node.x , node.y + 1))
except Exception,e:
pass
try:
_adjacent.append(Node(node , node.x - 1 , node.y + 1))  except Exception,e:
pass
try:
_adjacent.append(Node(node , node.x - 1 , node.y))
except Exception,e:
pass
for a in _adjacent:
if (a.x,a.y) == (end.x, end.y):
new_G = calc_G(a, node) + node.G
print find path finish!
return True
if (a.x,a.y) in close_list:
continue
if (a.x,a.y) not in open_list:
open_list[(a.x,a.y)] = a
else: