Astar

A* 是一种在平面图形上计算最优路径的方法，通常用来做 2D 游戏的最短寻路，该算法是一种 Dijkstra 算法的变体，使用启发式的策略来提高算法的搜索效率。

wikipedia；medium；pythonf

基本思想

基于启发式的方法，基于BFS去做最短路径搜索，借助类似Manhattan距离作为启发，每次加入后续的多个点，然后按照后续点的属性去排序，不断的加入close的区间，直到第一次遍历到终点就是最短的路径。

$$f(n) = g(n) + h(n)$$

f代表的是经过当前点，从起点到最终点的距离，g代表的是从起点到当前节点的距离，h代表的是启发式方法到终点的距离。

维护三个list：open(候选列表)、close（状态确定的列表）、children（等待操作的列表）

首先用 bfs 的方法，找到当前节点的可达后续节点，将这些节点加入 children，确定 child 不在 close_list 中后（即在 open 中）则判断哪个是最优解，然后更新 openlist 和 closelist 。

即：每次遍历的当前节点都从 open 中总距离最小的选，然后放入 close。直到 openlist 为空。

相关类别定义

class node(): 
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position

        self.g = 0 
        self.h = 0 
        self.f = 0 
    
    def __eq__(self, o: object) -> bool:
        return o.position == self.position

具体代码实现

def asterS(map,slope,start,end):
    # 在astar算法的基础上，我们需要加入的是高度的约束
    # 阻碍的条件是高度不同同时没有slope的存在，这种就是wall
    # 其余的和Astar算法应该是一样的

    # init the start and end node
    start_node = node(None,start)
    end_node = node(None,end)

    # init the open and closed lists
    open_list = []
    close_list = []

    # add the start node to the open list
    open_list.append(start_node)

    # loop util find the end_node 
    while len(open_list)>0:
        # make the best node as current_node
        # init 1 
        current_node = open_list[0]
        current_index = 0
        for index, nod in enumerate(open_list):
            if nod.f<current_node.f:
                current_node = nod
                current_index = index
        
        # pop the curr node off open list, add to close list 
        open_list.pop(current_index)
        close_list.append(current_node)

        # terminal conditions (reach the end node )
        if current_node == end_node:
            path = []
            while(current_node is not None):
                path.append(current_node.position)
                current_node = current_node.parent

            # return the path we find.
            return path[::-1]
        
        # the body of the loop: update the nodes
        # find the available children nodes
        children = []

        # define the adjacent squares 
        positions = [(-1,0),(1,0),(0,-1),(0,1)]
        for pos in positions:
            # get childrens positions
            node_pos = (current_node.position[0]+pos[0], current_node.position[1]+pos[1])
            
            # make sure within range  
            if node_pos[0] < 0 or node_pos[0] >= map.shape[0] or node_pos[1] < 0 or node_pos[1] >= map.shape[1]:
                continue

            # mkae sure walkab
            mapflag = map[current_node.position[0], current_node.position[1]] != map[node_pos[0], node_pos[1]]
            slopeflag1 = slope[node_pos[0], node_pos[1]] == 0  or slope[current_node.position[0], current_node.position[1]] == 0
            slpopeflag2 = slope[node_pos[0], node_pos[1]] != slope[current_node.position[0], current_node.position[1]]
            
            if mapflag and (slopeflag1 or slpopeflag2):
                continue

            # we need creat node first to find out if it is in the openlist or closed list
            new_node = node(current_node, node_pos)
            children.append(new_node)
        
        # loop those children
        # using the __eq__ to judge if it's already traveled.
        for child in children:
            if child in close_list:
                continue
            
            # create f,g,h for the legal child
            child.g = current_node.g + 1 
            child.h = manhattan(child.position, end_node.position)
            child.f = child.g + child.f

            # if the child is already in the open list, compare it
            if child in open_list:
                open_index = open_list.index(child)
                open_node = open_list[open_index] 
                if child.g > open_node.g:
                    continue
                open_list.pop(open_index)
            # if it is not in the open/closelist or better than that in open list, we add it.
            open_list.append(child)