pythonによる基本A*アルゴリズムの実装
9309 ワード
本文は恋花蝶から発表された.http://blog.csdn.net/lanphaday全文の完全性を保証する前提の下で任意の形式で自由に伝播することができるが、本声明を保留し、違反しなければならない.
最近、あるタスクでA*アルゴリズムを使うため、C++で1部実現しました.ただし、A*でA点からB点までのパスの有無を検出するだけで、パスを出力する必要はありません.後でコードを貼りたいのですが、簡単な道探しアプリケーションを実現したほうがいいと思い、pythonでバージョンを書いて貼り付けました. A*アルゴリズムは道を探すだけでなく、道を探すにもA*アルゴリズムを使うだけではありません.これは学習とA*アルゴリズムを使う上で最も注意しなければならない点でしょう. A*アルゴリズムは道を探して実現するのは人工知能ではなく、本質的に啓発的な探求遡及アルゴリズムであるが、業界はそれをゲーム人工知能(GameAI)の構成部分と呼ぶのが好きで、「豪華」に聞こえるようだ.A*アルゴリズムは大きなメモリ(深さ優先探索に対して)を必要とし、複雑な論理を実現する必要があり、エラーが発生しやすい. A*プロセス: 1.開始ノードをオープンリストに入れる(開始ノードのFとGの値はいずれも0とする). 2.手順を繰り返します. i.オープンリストで最小F値を持つノードを検索し、検索したノードを現在のノードとする. ii.現在のノードをオープンリストから削除し、閉じたリストに追加する. iii.現在のノードに隣接する各ノードについて、次の手順に従います. 1.隣接ノードが通行不能であるか、または隣接ノードが既に閉じたリストにある場合、何の操作も実行せず、次のノードの検証を継続する. 2.隣接ノードがオープンリストにない場合、そのノードをオープンリストに追加し、その隣接ノードの親ノードを現在のノードに設定し、隣接ノードのGとFの値を保存する. 3.隣接ノードがオープンリストにある場合、現在のノードから当該隣接ノードに到達G値が元のG値より小さいか否かを判定し、小さい場合は当該隣接ノードの親ノードを現在のノードとし、当該隣接ノードのGとF値を再設定する. iv.サイクル終了条件: エンドノードがオープンリストに検証対象ノードとして追加されると、パスが見つかり、ループが終了することを示す. あるいは、オープンリストが空の場合、追加可能な新しいノードがないことを示しますが、検証されたノードにエンドノードがない場合は、パスが見つからないことを意味し、ループも終了します. 3.終点ノードから親ノードに沿って遍歴し、遍歴したノード座標全体を保存し、遍歴したノードが最後に得られた経路である.
はい、くだらないことはあまり言わないで、コードを見てください.詳しく説明しますが、bug~があるかもしれません.また、この例のプログラムは最適化されていません.
参考資料:http://www.gamedev.net/reference/programming/features/astar/default.asp
http://blog.csdn.net/win32asn/archive/2006/03/17/627098.aspx
最近、あるタスクでA*アルゴリズムを使うため、C++で1部実現しました.ただし、A*でA点からB点までのパスの有無を検出するだけで、パスを出力する必要はありません.後でコードを貼りたいのですが、簡単な道探しアプリケーションを実現したほうがいいと思い、pythonでバージョンを書いて貼り付けました. A*アルゴリズムは道を探すだけでなく、道を探すにもA*アルゴリズムを使うだけではありません.これは学習とA*アルゴリズムを使う上で最も注意しなければならない点でしょう. A*アルゴリズムは道を探して実現するのは人工知能ではなく、本質的に啓発的な探求遡及アルゴリズムであるが、業界はそれをゲーム人工知能(GameAI)の構成部分と呼ぶのが好きで、「豪華」に聞こえるようだ.A*アルゴリズムは大きなメモリ(深さ優先探索に対して)を必要とし、複雑な論理を実現する必要があり、エラーが発生しやすい. A*プロセス: 1.開始ノードをオープンリストに入れる(開始ノードのFとGの値はいずれも0とする). 2.手順を繰り返します. i.オープンリストで最小F値を持つノードを検索し、検索したノードを現在のノードとする. ii.現在のノードをオープンリストから削除し、閉じたリストに追加する. iii.現在のノードに隣接する各ノードについて、次の手順に従います. 1.隣接ノードが通行不能であるか、または隣接ノードが既に閉じたリストにある場合、何の操作も実行せず、次のノードの検証を継続する. 2.隣接ノードがオープンリストにない場合、そのノードをオープンリストに追加し、その隣接ノードの親ノードを現在のノードに設定し、隣接ノードのGとFの値を保存する. 3.隣接ノードがオープンリストにある場合、現在のノードから当該隣接ノードに到達G値が元のG値より小さいか否かを判定し、小さい場合は当該隣接ノードの親ノードを現在のノードとし、当該隣接ノードのGとF値を再設定する. iv.サイクル終了条件: エンドノードがオープンリストに検証対象ノードとして追加されると、パスが見つかり、ループが終了することを示す. あるいは、オープンリストが空の場合、追加可能な新しいノードがないことを示しますが、検証されたノードにエンドノードがない場合は、パスが見つからないことを意味し、ループも終了します. 3.終点ノードから親ノードに沿って遍歴し、遍歴したノード座標全体を保存し、遍歴したノードが最後に得られた経路である.
はい、くだらないことはあまり言わないで、コードを見てください.詳しく説明しますが、bug~があるかもしれません.また、この例のプログラムは最適化されていません.
参考資料:http://www.gamedev.net/reference/programming/features/astar/default.asp
http://blog.csdn.net/win32asn/archive/2006/03/17/627098.aspx
# -*- coding: utf-8 -*-
import math
#
tm = [
'############################################################',
'#..........................................................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.......S.....................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#######.#######################################............#',
'#....#........#............................................#',
'#....#........#............................................#',
'#....##########............................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#...............................##############.............#',
'#...............................#........E...#.............#',
'#...............................#............#.............#',
'#...............................#............#.............#',
'#...............................#............#.............#',
'#...............................###########..#.............#',
'#..........................................................#',
'#..........................................................#',
'############################################################']
# python string ， test_map
test_map = []
#########################################################
class Node_Elem:
"""
，parent
"""
def __init__(self, parent, x, y, dist):
self.parent = parent
self.x = x
self.y = y
self.dist = dist
class A_Star:
"""
A
"""
# w,h ， ，
def __init__(self, s_x, s_y, e_x, e_y, w=60, h=30):
self.s_x = s_x
self.s_y = s_y
self.e_x = e_x
self.e_y = e_y
self.width = w
self.height = h
self.open = []
self.close = []
self.path = []
#
def find_path(self):
#
p = Node_Elem(None, self.s_x, self.s_y, 0.0)
while True:
# F
self.extend_round(p)
# ， ，
if not self.open:
return
# F
idx, p = self.get_best()
# ， ，
if self.is_target(p):
self.make_path(p)
return
# ，
self.close.append(p)
del self.open[idx]
def make_path(self,p):
# ， parent == None
while p:
self.path.append((p.x, p.y))
p = p.parent
def is_target(self, i):
return i.x == self.e_x and i.y == self.e_y
def get_best(self):
best = None
bv = 1000000 # ，
bi = -1
for idx, i in enumerate(self.open):
value = self.get_dist(i)# F
if value < bv:# ， F
best = i
bv = value
bi = idx
return bi, best
def get_dist(self, i):
# F = G + H
# G ， H
# A* 。
return i.dist + math.sqrt(
(self.e_x-i.x)*(self.e_x-i.x)
+ (self.e_y-i.y)*(self.e_y-i.y))*1.2
def extend_round(self, p):
# 8
xs = (-1, 0, 1, -1, 1, -1, 0, 1)
ys = (-1,-1,-1, 0, 0, 1, 1, 1)
#
# xs = (0, -1, 1, 0)
# ys = (-1, 0, 0, 1)
for x, y in zip(xs, ys):
new_x, new_y = x + p.x, y + p.y
# ，
if not self.is_valid_coord(new_x, new_y):
continue
#
node = Node_Elem(p, new_x, new_y, p.dist+self.get_cost(
p.x, p.y, new_x, new_y))
# ，
if self.node_in_close(node):
continue
i = self.node_in_open(node)
if i != -1:
#
if self.open[i].dist > node.dist:
# ~
#
self.open[i].parent = p
self.open[i].dist = node.dist
continue
self.open.append(node)
def get_cost(self, x1, y1, x2, y2):
"""
， 1.0， ， 1.4
"""
if x1 == x2 or y1 == y2:
return 1.0
return 1.4
def node_in_close(self, node):
for i in self.close:
if node.x == i.x and node.y == i.y:
return True
return False
def node_in_open(self, node):
for i, n in enumerate(self.open):
if node.x == n.x and node.y == n.y:
return i
return -1
def is_valid_coord(self, x, y):
if x < 0 or x >= self.width or y < 0 or y >= self.height:
return False
return test_map[y][x] != '#'
def get_searched(self):
l = []
for i in self.open:
l.append((i.x, i.y))
for i in self.close:
l.append((i.x, i.y))
return l
#########################################################
def print_test_map():
"""
"""
for line in test_map:
print ''.join(line)
def get_start_XY():
return get_symbol_XY('S')
def get_end_XY():
return get_symbol_XY('E')
def get_symbol_XY(s):
for y, line in enumerate(test_map):
try:
x = line.index(s)
except:
continue
else:
break
return x, y
#########################################################
def mark_path(l):
mark_symbol(l, '*')
def mark_searched(l):
mark_symbol(l, ' ')
def mark_symbol(l, s):
for x, y in l:
test_map[y][x] = s
def mark_start_end(s_x, s_y, e_x, e_y):
test_map[s_y][s_x] = 'S'
test_map[e_y][e_x] = 'E'
def tm_to_test_map():
for line in tm:
test_map.append(list(line))
def find_path():
s_x, s_y = get_start_XY()
e_x, e_y = get_end_XY()
a_star = A_Star(s_x, s_y, e_x, e_y)
a_star.find_path()
searched = a_star.get_searched()
path = a_star.path
#
mark_searched(searched)
#
mark_path(path)
print "path length is %d"%(len(path))
print "searched squares count is %d"%(len(searched))
# 、
mark_start_end(s_x, s_y, e_x, e_y)
if __name__ == "__main__":
#
tm_to_test_map()
find_path()
print_test_map()