A*搜索算法（python）_python的a*搜索策略

先了解一下什么是A*算法。

A*搜寻算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC（Non-Player-ControlledCharacter）的移动计算，或线上游戏的BOT（ROBOT）的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。

A星算法核心公式：

F = G + H

F - 方块的总移动代价
G - 开始点到当前方块的移动代价
H - 当前方块到结束点的预估移动代价

G值是怎么计算的？
假设现在我们在某一格子，邻近有8个格子可走，当我们往上、下、左、右这4个格子走时，移动代价为10；当往左上、左下、右上、右下这4个格子走时，移动代价为14；即走斜线的移动代价为走直线的1.4倍。
这就是G值最基本的计算方式，适用于大多数2.5Drpg页游。
根据游戏需要，G值的计算可以进行拓展。如加上地形因素对寻路的影响。格子地形不同，那么选择通过不同地形格子，移动代价肯定不同。同一段路，平地地形和丘陵地形，虽然都可以走，但平地地形显然更易走。
我们可以给不同地形赋予不同代价因子，来体现出G值的差异。如给平地地形设置代价因子为1，丘陵地形为2，在移动代价相同情况下，平地地形的G值更低，算法就会倾向选择G值更小的平地地形。

拓展公式：

G = 移动代价 * 代价因子

H值是如何预估出来的？
很显然，在只知道当前点，结束点，不知道这两者的路径情况下，我们无法精确地确定H值大小，所以只能进行预估。
有多种方式可以预估H值，如曼哈顿距离、欧式距离、对角线估价，最常用最简单的方法就是使用曼哈顿距离进行预估：
H = 当前方块到结束点的水平距离 + 当前方块到结束点的垂直距离
题外话：A星算法之所以被认为是具有启发策略的算法，在于其可通过预估H值，降低走弯路的可能性，更容易找到一条更短的路径。其他不具有启发策略的算法，没有做预估处理，只是穷举出所有可通行路径，然后从中挑选一条最短的路径。这也是A星算法效率更高的原因。

鉴于前人已经把原理讲的很清楚了，便不再废话，想要深入了解下的可以参考下面的两篇文章。

接下来上代码：

代码1

文件AStar.py

# coding=utf-8

#描述AStar算法中的节点数据 
class Point:
    """docstring for point"""
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y

class Node:     
    def __init__(self, point, g = 0, h = 0):  
        self.point = point        #自己的坐标  
        self.father = None        #父节点  
        self.g = g                #g值
        self.h = h                #h值  

    """
    估价公式：曼哈顿算法
     """
    def manhattan(self, endNode):
        self.h = (abs(endNode.point.x - self.point.x) + abs(endNode.point.y - self.point.y))*10 

    def setG(self, g):
        self.g = g

    def setFather(self, node):
        self.father = node

class AStar:
    """
    A* 算法 
    python 2.7 
    """
    def __init__(self, map2d, startNode, endNode):
        """ 
        map2d:      寻路数组 
        startNode:  寻路起点 
        endNode:    寻路终点 
        """  
        #开放列表
        self.openList = []
        #封闭列表  
        self.closeList = []
        #地图数据
        self.map2d = map2d
        #起点  
        self.startNode = startNode
        #终点
        self.endNode = endNode 
        #当前处理的节点
        self.currentNode = startNode
        #最后生成的路径
        self.pathlist = [];
        return;

    def getMinFNode(self):
        """ 
        获得openlist中F值最小的节点 
        """  
        nodeTemp = self.openList[0]  
        for node in self.openList:  
            if node.g + node.h < nodeTemp.g + nodeTemp.h:  
                nodeTemp = node  
        return nodeTemp

    def nodeInOpenlist(self,node):
        for nodeTmp in self.openList:  
            if nodeTmp.point.x == node.point.x \
            and nodeTmp.point.y == node.point.y:  
                return True  
        return False

    def nodeInCloselist(self,node):
        for nodeTmp in self.closeList:  
            if nodeTmp.point.x == node.point.x \
            and nodeTmp.point.y == node.point.y:  
                return True  
        return False

    def endNodeInOpenList(self):  
        for nodeTmp in self.openList:  
            if nodeTmp.point.x == self.endNode.point.x \
            and nodeTmp.point.y == self.endNode.point.y:  
                return True  
        return False

    def getNodeFromOpenList(self,node):  
        for nodeTmp in self.openList:  
            if nodeTmp.point.x == node.point.x \
            and nodeTmp.point.y == node.point.y:  
                return nodeTmp  
        return None

    def searchOneNode(self,node):
        """ 
        搜索一个节点
        x为是行坐标
        y为是列坐标
        """  
        #忽略障碍
        if self.map2d.isPass(node.point) != True:  
            return  
        #忽略封闭列表
        if self.nodeInCloselist(node):  
            return  
        #G值计算 
        if abs(node.point.x - self.currentNode.point.x) == 1 and abs(node.point.y - self.currentNode.point.y) == 1:  
            gTemp = 14  
        else:  
            gTemp = 10  


        #如果不再openList中，就加入openlist  
        if self.nodeInOpenlist(node) == False:
            node.setG(gTemp)
            #H值计算 
            node.manhattan(self.endNode);
            self.openList.append(node)
            node.father = self.currentNode
        #如果在openList中，判断currentNode到当前点的G是否更小
        #如果更小，就重新计算g值，并且改变father 
        else:
            nodeTmp = self.getNodeFromOpenList(node)
            if self.currentNode.g + gTemp < nodeTmp.g:
                nodeTmp.g = self.currentNode.g + gTemp  
                nodeTmp.father = self.currentNode  
        return;

    def searchNear(self):
        """ 
        搜索节点周围的点 
        按照八个方位搜索
        拐角处无法直接到达
        (x-1,y-1)(x-1,y)(x-1,y+1)
        (x  ,y-1)(x  ,y)(x  ,y+1)
        (x+1,y-1)(x+1,y)(x+1,y+1)
        """ 
        if self.map2d.isPass(Point(self.currentNode.point.x - 1, self.currentNode.point.y)) and \
        self.map2d.isPass(Point(self.currentNode.point.x, self.currentNode.point.y -1)):
            self.searchOneNode(Node(Point(self.currentNode.point.x - 1, self.currentNode.point.y - 1)))

        self.searchOneNode(Node(Point(self.currentNode.point.x - 1, self.currentNode.point.y)))

        if self.map2d.isPass(Point(self.currentNode.point.x - 1, self.currentNode.point.y)) and \
        self.map2d.isPass(Point(self.currentNode.point.x, self.currentNode.point.y + 1)):
            self.searchOneNode(Node(Point(self.currentNode.point.x - 1, self.currentNode.point.y + 1)))

        self.searchOneNode(Node(Point(self.currentNode.point.x, self.currentNode.point.y - 1)))
        self.searchOneNode(Node(Point(self.currentNode.point.x, self.currentNode.point.y + 1)))

        if self.map2d.isPass(Point(self.currentNode.point.x, self.currentNode.point.y - 1)) and \
        self.map2d.isPass(Point(self.currentNode.point.x + 1, self.currentNode.point.y)):
            self.searchOneNode(Node(Point(self.currentNode.point.x + 1, self.currentNode.point.y - 1)))

        self.searchOneNode(Node(Point(self.currentNode.point.x + 1, self.currentNode.point.y)))

        if self.map2d.isPass(Point(self.currentNode.point.x + 1, self.currentNode.point.y)) and \
        self.map2d.isPass(Point(self.currentNode.point.x, self.currentNode.point.y + 1)):
            self.searchOneNode(Node(Point(self.currentNode.point.x + 1, self.currentNode.point.y + 1)))
        return;

    def start(self):
        ''''' 
        开始寻路 
        '''
        #将初始节点加入开放列表
        self.startNode.manhattan(self.endNode);
        self.startNode.setG(0);
        self.openList.append(self.startNode)

        while True:
            #获取当前开放列表里F值最小的节点
            #并把它添加到封闭列表，从开发列表删除它
            self.currentNode = self.getMinFNode()
            self.closeList.append(self.currentNode)
            self.openList.remove(self.currentNode)

            self.searchNear();

            #检验是否结束
            if self.endNodeInOpenList():
                nodeTmp = self.getNodeFromOpenList(self.endNode)
                while True:
                    self.pathlist.append(nodeTmp);
                    if nodeTmp.father != None:
                        nodeTmp = nodeTmp.father
                    else:
                        return True;
            elif len(self.openList) == 0:
                return False;
        return True;

    def setMap(self):
        for node in self.pathlist:
            self.map2d.setMap(node.point);
        return;
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

文件2

文件map2d.py

# coding=utf-8
from __future__ import print_function

class map2d:
    """ 
    地图数据
    """  
    def __init__(self):
        self.data = [list("####################"),
                     list("#*****#************#"),
                     list("#*****#*****#*####*#"),
                     list("#*########*##******#"),
                     list("#*****#*****######*#"),
                     list("#*****#####*#******#"),
                     list("####**#*****#*######"),
                     list("#*****#**#**#**#***#"),
                     list("#**#*****#**#****#*#"),
                     list("####################")]

        self.w = 20
        self.h = 10
        self.passTag = '*'
        self.pathTag = 'o'

    def showMap(self):
        for x in xrange(0, self.h):
            for y in xrange(0, self.w):
                print(self.data[x][y], end='')
            print(" ")
        return;

    def setMap(self, point):
        self.data[point.x][point.y] = self.pathTag
        return;

    def isPass(self, point):
        if (point.x < 0 or point.x > self.h - 1) or (point.y < 0 or point.y > self.w - 1):
            return False;

        if self.data[point.x][point.y] == self.passTag:
            return True;
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

文件3

文件AStarTest.py

# coding=utf-8
import map2d
import AStar

if __name__ == '__main__':
    ##构建地图
    mapTest = map2d.map2d();
    mapTest.showMap();
    ##构建A*
    aStar = AStar.AStar(mapTest, AStar.Node(AStar.Point(1,1)), AStar.Node(AStar.Point(8,18)))
    print "A* start:"
    ##开始寻路
    if aStar.start():
        aStar.setMap();
        mapTest.showMap();
    else:
        print "no way"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在AStar.py中增加了对拐角的处理，设置拐角无法直达。

运行结果：

参考：

用简单直白的方式讲解A星寻路算法原理

A星算法详解(个人认为最详细,最通俗易懂的一个版本)