先了解一下什么是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 = nodeclass 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 
文件2
文件map2d.py
# coding=utf-8from __future__ import print_functionclass 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  self.h - 1) or (point.y  self.w - 1):            return False;        if self.data[point.x][point.y] == self.passTag:
            return True;
文件3
文件AStarTest.py
# coding=utf-8import map2dimport AStarif __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"
在AStar.py中增加了对拐角的处理，设置拐角无法直达。
运行结果：
image.png
参考：
用简单直白的方式讲解A星寻路算法原理
A星算法详解(个人认为最详细,最通俗易懂的一个版本)


作者：漫步_9378
链接：https://www.jianshu.com/p/613ef51394ec