从头理解A*算法

A*算法概述

图例拆解A*寻路过程

本文中所有图中，黑色块表示墙壁，红色块表示目标点，绿色圆圈表示起点，黄色块表示需要考察的点，可能是通往目的点的路径，白色块和黄色块是人物能站上去的点。

示意图.png
在开始算法之前需要做一些准备工作。也需要介绍几个相关的数据结构。

openlist:待考察的点，有可能是通往目的地需要经过的点，一开始只有人物所在的起点。
closelist:已经考察过的点，或是不可达的点(墙壁)，这些点不要考察。
节点间距离:水平(垂直)相邻节点距离为10，斜向相邻节点距离为14
估值函数G(A,B):从点A到点B，大概需要走多远，用曼哈顿距离计算，即离目标点的横纵距离和。
单步代价H(A,B):从A移动到节点B的距离，水平(垂直)为10，斜向14
代价函数F(A,B):这是一个变化的量，表示从A到B大概需要走的距离，其值为G(A,B)+H(A,B)，需要在寻路过程中不断调整，直到到达目的地，或者寻路失败。

step 1:
从openlist中选取一个距离目标点的F值最小的点(第一次选择时只有起始点)，选取的点取名S。
点S的Hs=0, Gs等于S点和目标点的横纵坐标距离和，Fs=H+G
如果openlist中已经没有点了，说明寻路失败，即没有这么一条到目标点的路径
step 2:
将点S从openlist中删去，并加入closelist中
step 3:
对点S的八个邻居点做如下处理：
  a)如果邻居点在closelist中，表示之前访问过，或者是不可达点。直接跳过对该邻居点的处理
  b)如果邻居点不在openlist中，将其加入openlist中，并计算该邻居点的F， G， H值，
    H=Hs+10, G用曼哈顿距离，F=H+G
  c)如果邻居点在openlist中，需要跟新该邻居点的F,G,H值，即邻居
    点原来的H值比Hs+10还大，则说明经由S点到达该邻居点更合适。更新邻居点的H，F值。
  d)如果邻居点是目标点，算法结束
step 4:
重复step 1-3

step 1:初始只有起点在openlist中，且起点的F=50,H=0,G=50 step1.png step 2:把起点从openlist中移除，加入closelist中，考察起点的8个邻居，计算8个邻居的F H G值，并把邻居加入到openlist中，为了方便我们对每个节点进行了index编号，起点index=0。 step2.png step 3:从openlist中选取一个F值最小的点(现在openlist中有8个点，F值最小的是index=5的点)，考察index=5的点，其右侧三个邻居是不可达点，跳过，其余5个邻居都在openlist中，且不需要更新F H G值，用index=3这个点举例说明，现在F3=64，如果经由index=5这个点到index=3这个点，需要在index=3的基础上多走距离10，因此H'=H5 +10=20 > H3，所以不需要更新，其余邻居情况类似。
step 4:将index=5这个点从openlist中移除，加入到closelist中，从openlist中(还有7个点)选取F值最小的(有2个,index=3 index=8,选取后加入openlist的点8)，重复步骤3的计算。 step4.png step 5:剩下的选点合成一个图，如下所示，选点index分别为:index=8,index=11,index=12,index=18,到达终点。 step5.png step 6:最终寻路路径如下 path.png

A*算法流程

A*算法代码

import sys

#地图(从文件中获取的二维数组)
maze=[]
#起点
start=None
#终点
end=None
#开放列表（也就是有待探查的地点）
open_list={}
#关闭列表  (已经探查过的地点和不可行走的地点)
close_list={}
#地图边界(二维数组的大小，用于判断一个节点的相邻节点是否超出范围)
map_border=()
#方向
orientation=[]

class Node(object):
    def __init__(self,father,x,y):
        if x<0 or x>=map_border[0] or y<0 or y>=map_border[1]:
            raise Exception('坐标错误')

        self.father=father
        self.x=x
        self.y=y

        if father !=None:
            self.G=father.G+1
            self.H=distance(self,end)
            self.F=self.G+self.H
        else:
            self.G=0
            self.H=0
            self.F=0

    def reset_father(self,father,new_G):
        if father!=None:
            self.G=new_G
            self.F=self.G+self.H

        self.father=father

#计算距离
def distance(cur,end):
    return abs(cur.x-end.x)+abs(cur.y-end.y)
        

#在open_list中找到最小F值的节点
def min_F_node():
    global open_list
    if len(open_list)==0:
        raise Exception('路径不存在')

    _min=9999999999999999
    _k=(start.x,start.y)

    #以列表的形式遍历open_list字典
    for k,v in open_list.items():
        if _min>v.F:
            _min=v.F
            _k=k

    return open_list[_k]

#把相邻的节点加入到open_list之中，如果发现终点说明找到终点
def addAdjacentIntoOpen(node):
    global open_list,close_list
    
    #首先将该节点从开放列表移动到关闭列表之中
    open_list.pop((node.x,node.y))
    close_list[(node.x,node.y)]=node
    adjacent=[]

    #添加相邻节点的时候要注意边界
    #上
    try:
        adjacent.append(Node(node,node.x,node.y-1))
    except Exception as err:
        pass
    #下
    try:
        adjacent.append(Node(node,node.x,node.y+1))
    except Exception as err:
        pass
    #左
    try:
        adjacent.append(Node(node,node.x-1,node.y))
    except Exception as err:
        pass
    #右
    try:
        adjacent.append(Node(node,node.x+1,node.y))
    except Exception as err:
        pass

    #检查每一个相邻的点
    for a in adjacent:
        #如果是终点，结束
        if (a.x,a.y)==(end.x,end.y):
            new_G=node.G+1
            end.reset_father(node,new_G)
            return True
        #如果在close_list中,不去理他
        if (a.x,a.y) in close_list:
            continue
        #如果不在open_list中，则添加进去
        if (a.x,a.y) not in open_list:
            open_list[(a.x,a.y)]=a
        #如果存在在open_list中，通过G值判断这个点是否更近 
        else:
            exist_node=open_list[(a.x,a.y)]
            new_G=node.G+1
            if new_G<exist_node.G:
                exist_node.reset_father(node,new_G)

    return False

#查找路线
def find_the_path(start,end):
    global open_list
    open_list[(start.x,start.y)]=start

    the_node=start
    try:
        while not addAdjacentIntoOpen(the_node):
            the_node=min_F_node()

    except Exception as err:
        #路径找不到
        print(err)
        return False
    return True

#读取文件，将文件中的信息加载到地图(maze)信息中
def readfile(url):
    global maze,map_border
    f=open(url)
    line=f.readline()
    map_size=line.split()
    map_size=list(map(int,map_size))
    x=map_size[0]
    y=map_size[1]
    map_border=(x,y)
    
    i=0
    while line:
        line=f.readline()
        maze.append(list(map(int,line.split())))
        i=i+1
        if i>x-1:
            break


#通过递归的方式根据每个点的父节点将路径连起来
def mark_path(node):
    global orientation
    if node.father==None:     
        return
    
    #print('({x},{y})'.format(x=node.x,y=node.y))
    #将方向信息存储到方向列表中
    if node.father.x-node.x>0:
        orientation.append('L')
    elif node.father.x-node.x<0:
        orientation.append('R')
    elif node.father.y-node.y>0:
        orientation.append('U')
    elif node.father.y-node.y<0:
        orientation.append('D')
    mark_path(node.father)
    
#解析地图,把不可走的点直接放到close_list中
def preset_map():
    global start,end,map_bloder,maze
    row_index=0
    for row in maze:
        col_index=0
        for n in row:
            if n==1:
                block_node=Node(None,col_index,row_index)
                close_list[(block_node.x,block_node.y)]=block_node
            col_index=col_index+1
        row_index=row_index+1
    
if __name__=='__main__':
    #判断在控制台输入的参数时候达到要求
    if len(sys.argv)<6:
        raise Exception('参数格式')
    else:
        #从控制台读取参数
        readfile(sys.argv[1])
        start_x=int(sys.argv[2])
        start_y=int(sys.argv[3])
        end_x=int(sys.argv[4])
        end_y=int(sys.argv[5])
        start=Node(None,start_x,start_y)
        end=Node(None,end_x,end_y)

        
        
        preset_map()

        #判断起点终点是否符合要求
        if (start.x,start.y) in close_list or (end.x,end.y) in close_list:
            raise Exception('输入的坐标不可走')

        if find_the_path(start,end):
            mark_path(end)

        #列表方向调整为起点开始
        orientation.reverse()
        str_ori=''
        for o in orientation:
            str_ori=str_ori+o+' '
        print(str_ori)

简单测试数据：sample_test.txt文件内容如下，执行指令如下，a_star.py为代码名称，sample_test.txt为数据文件名，(0 0) (4 0)分别为起始点和终点。

python a_star.py sample_test.txt 0 0 4 0

5    3
0    0    1    0    0
1    0    1    0    0
0    0    0    0    1

执行结果如下：结果是这个样子的原因在于，执行的时候设置了不允许斜向移动。

R D D R R U U R