A_star算法與Dijkstra算法 Grassfire 算法主要不一樣的地方就在于加入了一個度量目前的節點與目標點之間的距離的啟發函數：
常用的啟發函數有：

算法介紹就不詳細敘述了，本文主要是通過python實現A*算法在 0 1 地圖中（0 表示可通行區域，1表示障礙區域）的最優路徑尋找，最終效果為：

其中6是其進行行走的路徑。

下面在程序中，對算法中所設計到的需要進行抽象的對象及算法的邏輯流程進行了概述：

            
              
#需要進行抽象化的有：節點（屬性有：x y坐標  父節點  g及h ）  地圖（屬性有高度 寬度  數據(數據中有可通行路徑與障礙兩種)）
#A_star :
# open_list (存放待測試的點，剛開始有start加入list，后面每一個current的相鄰點（不能位于colse_list中且不是終點）要放到open_list中) 表示已經走過的點
# close_list(存放已測試的點，已經當過current的點，就放到close_list中) 存放已經探測過的點，不必再進行探測
# current 現在正在測試的點，要計算current周圍的點的代價f  經過current后要放到close_list中 將openlist代價f最小的node當作下一個current
# start_point end_point

#初始化地圖  openlist closelist node
#將start點放入openlist中
#while（未達到終點）：
#取出 openlist 中的點 將這個點設置為current 并放入closelist中
#for node_near in（current的臨近點）
#if（current的臨近點 node_near 不在closelist中且不為障礙）：
#計算 node_near 的f（f=g+h）大小
# if( node_near 不在 openlist 中)
# 將 node_near 放入 openlist，并將其父節點設置為current 然后將f值設置為計算出的f值
# else if( node_near 在 openlist 中)
#  if（計算出的f大于在openlist中的f）
#    不動作
#  else if（計算出的f小于等于在openlist中的f）
#     將 openlist 中的 node_near 的f值更新為計算出的新的更小的f值 并將父節點設置為current
#返回并繼續循環
import sys
#將地圖中的點抽象化成類
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other): #函數重載
        if((self.x == other.x )and (self.y == other.y)):
            return  1
        else:
            return 0

#通過列表實現的地圖的建立  類c語言數組？
class map_2d:
    def __init__(self,height,width):
        self.height = height
        self.width = width
        self.data = []
        self.data = [[0 for i in range(width)] for j in range(height)]
    def map_show(self):
        for i in range(self.height):
            for j in range(self.width):
                print(self.data[i][j], end=' ')
            print("")
    def obstacle(self,obstacle_x,obstacle_y):
        self.data[obstacle_x][obstacle_y]=1
    def end_draw(self,point):
        self.data[point.x][point.y] = 6

#A*算法的實現
class A_star:
    # 設置node
    class Node:
        def __init__(self, point, endpoint, g):
            self.point = point  # 自己的坐標
            self.endpoint = endpoint  # 自己的坐標
            self.father = None  # 父節點
            self.g = g  # g值，g值在用到的時候會重新算
            self.h = (abs(endpoint.x - point.x) + abs(endpoint.y - point.y)) * 10  # 計算h值
            self.f = self.g + self.h

        #尋找臨近點
        def search_near(self,ud,rl):  # up  down  right left
            nearpoint = Point(self.point.x + rl, self.point.y + ud)
            nearnode = A_star.Node(nearpoint, self.endpoint, self.g + 1)
            return nearnode


    def __init__(self,start_point,end_point,map):#需要傳輸到類中的，在此括號中寫出
        self.path=[]
        self.close_list=[] #存放已經走過的點
        self.open_list=[] #存放需要盡心探索的點
        self.current = 0 #現在的node
        self.start_point=start_point
        self.end_point=end_point
        self.map = map #所在地圖

    def select_current(self):
        min=10000000
        node_temp = 0
        for ele in self.open_list:
            if ele.f < min:
                min = ele.f
                node_temp = ele
        self.path.append(node_temp)
        self.open_list.remove(node_temp)
        self.close_list.append(node_temp)
        return node_temp

    def isin_openlist(self,node):
        for opennode_temp in self.open_list:
            if opennode_temp.point == node.point:
                return opennode_temp
        return 0

    def isin_closelist(self,node):
        for closenode_temp in self.close_list:
            if closenode_temp.point == node.point:
                return 1
        return 0

    def is_obstacle(self,node):
        if self.map.data[node.point.x][node.point.y]==1 :
            return  1
        return  0

    def near_explore(self,node):
        ud = 1
        rl = 0
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        ud = -1
        rl = 0
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        ud = 0
        rl = 1
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        ud = 0
        rl = -1
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        ud = 1
        rl = 1
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        ud = 1
        rl = -1
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        ud = -1
        rl = 1
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        ud = -1
        rl = -1
        node_temp = node.search_near(ud,rl) #在調用另一個類的方法時（不論是子類還是在類外定義的類），都要進行實例化才能調用函數
        if node_temp.point == end_point:
            return 1
        elif self.isin_closelist(node_temp):
            pass
        elif self.is_obstacle(node_temp):
            pass
        elif self.isin_openlist(node_temp) == 0:
            node_temp.father = node
            self.open_list.append(node_temp)
        else:
            if node_temp.f < (self.isin_openlist(node_temp)).f:
                self.open_list.remove(self.isin_openlist(node_temp))
                node_temp.father = node
                self.open_list.append(node_temp)

        return 0

##建圖并設立障礙
ss=map_2d(10,20)
for i in range(10):
    ss.obstacle(4,i)
for i in range(19):
    ss.obstacle(0,i+1)
for i in range(9):
    ss.obstacle(i+1,0)
for i in range(9):
    ss.obstacle(i+1,19)
for i in range(19):
    ss.obstacle(9,i)
ss.obstacle(8,6)
ss.obstacle(6,8)
ss.obstacle(6,15)
ss.obstacle(9,10)
start_point = Point(1,2)
end_point = Point(9,19)
ss.end_draw(end_point)
ss.end_draw(start_point)

#初始化設置A*
a_star = A_star(start_point,end_point,ss)
start_node = a_star.Node(start_point,end_point,0)
a_star.open_list.append(start_node)

flag=0 #到達終點的標志位
m=0 #步數統計

#進入循環
while  flag != 1 :
    a_star.current = a_star.select_current()#從openlist中選取一個node
    flag=a_star.near_explore(a_star.current)#對選中的node進行周邊探索
    m=m+1
    print(m)

#畫出地圖路徑
for node_path in a_star.path:
    ss.end_draw(node_path.point)
ss.map_show()