hello, A~* 寻路算法!

寻路算法是游戏中经常用到的算法之一，而这其中A~* 算法大概是我们最耳熟的寻路算法了，下面我们会通过A~* 算法与广度优先遍历搜索和深度优先遍历搜索的寻路过程的比较来了解A~*算法的思想

Demo演示代码可以点这→ Demo

BFS

广度优先遍历的过程就是以起始点为中心开始向周围搜索，每次搜索完一层，继续往更远一层搜索

因为BFS是一层层向外搜索，所以它总是能找到最短路径，因为它的路径不会绕道更远的地方再折回来。但是很明显我们肉眼直接能看出来的最短路径，BFS搜索则需要遍历那么多节点。

DFS

深度优先遍历的过程就是从起始点开始一直向远处搜索，直到搜索到边界，然后再往回寻找另外一条分支

从图中的DFS的最终路径可以看出来，DFS搜索出来的路径并不是最短路径，所以DFS路径搜索不能保证搜索到的是最短路径，除非你将整个地图全部遍历，记录下所有的可达路径，然后选择最短的，但是这个过程会代价是很大的。DFS不会去走捷径，它总是一条路走到黑。

A~*

A~* 算法的关键是每走的一步都是选择最短的估价路径节点。A~*的搜索过程既不会像BFS那样沿着周围海量的搜索，也不会像DFS那样可能会绕弯子，因为它每一步都会计算当前到达终点的估价距离，所以它往终点搜索是启发式的搜索，通过估价距离来启发往哪个方向走，所以它的路线总是往终点方向前进的；

图中可以看到A~每走一步都会去遍历当前点周围路径，然后选择最短(估价最短)的路径往下走。因为估价一般都是假定当前点到终点最短的路径上没有障碍物，一旦这个路径上有障碍物，那么该条路径在搜索到障碍物的时候会发生转向（放弃原有的路径），也就是说A~算法前进的过程中会修正估价函数的错误。如下图所示，估价值最短的路径一直是从蓝点到红点垂直往下的路径，当往下走到发现下方是障碍，说明当前路径的估价是错误的，就会从其他可选的路径中寻找估价最短的；

A~*算法实现

算法描述

start：起始点 end：终点 costG：该节点按照搜索路径到达起始点的代价； costH：该节点到达终点end的估计值 openedList：待搜索序列 closedList：已经过的序列

1. 将起始点start加入到待搜索序列openedList中
2. 从openedList选择一个代价最低的节点cheapest（期初cheapest是起始点）如果该节点是终点则搜索成功；
3. 遍历cheapest的所有邻近节点near；
4. • 如果near已经走过，即包含在closedList中，则将略过它；
   • 如果near已经遍历过，即包含在openedList中，则比较near之前遍历的路径到起始点的距离和near按照经过cheapest到达起始点的距离，如果新的路径起始点更低，则更新near的costG值。
   • 如果near不包含在openedList和closedList中，则计算该节点按照搜索的路径到达起始点的距离costG，计算该节点到达终点的估计距离costH，并更新该节点的这两个值，将near加入到openedList中
5. cheapest节点搜索完以后，将cheapest从openedList移除，并加入到closedList中； 重复2-5的过程；

A~* 算法的估价

每一步的估价包含2个部分

• 1. 当前点到起始的实际距离costG，因为当前点到起始点的路径是已经确认过的，所以很容易就能计算出这个距离；
• 2. 当前点到终点的估计距离costH，这个距离是通过坐标的一些运算来的，它会忽略当前点到达终点路径上的障碍物，假定它是畅通无阻的，所以这个costH不一定是真实最短的路径距离, ；

关键代码实现：

我们使用二维数组来表示整个地图，每个节点可以到达周围的上下左右四个方向；

+ (BOOL)findPathWithMap:(PathFindMap *)map
                  start:(PathFindNode *)start
                    end:(PathFindNode *)end
             closedList:(NSMutableArray<PathFindNode *> *)closedList
             openedList:(NSMutableArray<PathFindNode *> *)openedList {
    
    [openedList addObject:start];
    PathFindNode *cheapNode = [AStar findCheapNodeWithEndNode:end closedNodes:closedList openedNodes:openedList];
    do {
        [AStar searchAtNode:cheapNode
                        map:map
                    endNode:end
                closedNodes:closedList
                openedNodes:openedList];
        cheapNode = [AStar findCheapNodeWithEndNode:end closedNodes:closedList openedNodes:openedList];
    } while (![cheapNode isEqual:end] && openedList.count != 0);
    
    return cheapNode == end;
}

// 遍历当前节点的子节点
+ (void)searchAtNode:(PathFindNode *)node
                 map:(PathFindMap *)map
             endNode:(PathFindNode *)endNode
         closedNodes:(NSMutableArray<PathFindNode *> *)closedNodes
         openedNodes:(NSMutableArray<PathFindNode *> *)openedNodes {

    if (!node || !map.nodesDic.count) return;
    if (![map.nodesDic.allValues containsObject:node]) return;
  
    for (MoveStep *step in map.allSteps) {
        NSString *key = [NSString stringWithFormat:@"%lu_%lu", (unsigned long)node.row + step.row, (unsigned long)node.col + step.col];
        PathFindNode *nearNode = map.nodesDic[key];
        if (nearNode && !nearNode.isObstacle && ![closedNodes containsObject:nearNode]) {
            // calculate the cost
            NSUInteger tempCostG = node.costG + step.cost;
            if ([openedNodes containsObject:nearNode]) {
                if (tempCostG < nearNode.costG) {
                    nearNode.parent = node;
                    nearNode.costG = tempCostG;
                    nearNode.parentDirection = [PathFindMap parentDirectionWithStep:step];
                }
            } else {
                NSUInteger tempCostH = [AStar estimateCostBetweenNodeA:nearNode nodeB:endNode map:map];
                nearNode.costG = tempCostG;
                nearNode.costH = tempCostH;
                nearNode.parent = node;
                nearNode.parentDirection = [PathFindMap parentDirectionWithStep:step];
                [openedNodes addObject:nearNode];
            }
        }
    }
    
    [openedNodes removeObject:node];
    [closedNodes addObject:node];
}

// 查找估价值最短的节点
+ (PathFindNode *)findCheapNodeWithEndNode:(PathFindNode *)endNode
                               closedNodes:(NSMutableArray<PathFindNode *> *)closedNodes
                               openedNodes:(NSMutableArray<PathFindNode *> *)openedNodes {
    NSUInteger costMin = NSUIntegerMax;
    PathFindNode *cheapNode = nil;
    for (PathFindNode *tempNode in openedNodes) {
        NSUInteger cost = tempNode.costG + tempNode.costH;
        if (cost < costMin) {
            costMin = cost;
            cheapNode = tempNode;
        }
    }
    return cheapNode;
}

// estimate the cost
+ (NSUInteger)estimateCostBetweenNodeA:(PathFindNode *)nodeA nodeB:(PathFindNode *)nodeB map:(PathFindMap *)map {
    NSUInteger colCost = nodeA.col > nodeB.col? (nodeA.col - nodeB.col) : (nodeB.col - nodeA.col);
    if (nodeA.row == nodeB.row) {
        return colCost * 10;
    }
    NSUInteger rowCost = nodeA.row > nodeB.row? (nodeA.row - nodeB.row) : (nodeB.row - nodeA.row);
    if (nodeA.col == nodeB.col) {
        return rowCost * 10;
    }
    
    // top/left/bottom/right cost 10
    if (map.allSteps.count == 4) {
        return (colCost + rowCost) * 10;
    } else {
        // top/left/bottom/right cost 10
        // left-top/left-bottom/right-top/right-bottom cost 14
        NSUInteger costDiagonal =  MIN(colCost, rowCost);
        NSUInteger costLine = colCost > rowCost? (colCost - rowCost) : (rowCost - colCost);
        return costLine * 10 + costDiagonal * 14;
    }
}

算法稳定性 从上面的示例图中可以看到算法效率A~* > BFS >DFS 如果是用来寻找最短路径的话DFS是不适合的，但也有些极端情况下DFS却是遍历最少的。而A~*算法的效率也依托于它的估价函数的命中率，每一次估价的错误，就意味着这一次的前进路径最后要放弃，所以整个A~* 搜索过程中如果估价的距离和实际距离不匹配，那么搜索过程就会出现很多的迂回，所以A~*的效率是不稳定的, 最差的情况应该能接近BFS的效率；

实际应用中这些算法都会经过特定的优化改造来提高搜索效率 广度优先搜索可以采用双向广度优先搜索，最终是两个广度搜索区域出现交叉则搜索完成，这样的话可以减少遍历很多节点； A~*算法主要是针对估价函数进行定制，比如估价函数添加相应的逻辑预判可以让搜索路径比较早的发现障碍物减少不必要的搜索；

测试

A~*的实现并什么复杂度，在16x16的网格地图中我编辑了一个迷宫，下面是A~*算法的的寻路情况

Demo代码git地址: https://github.com/ienho/AStarDemo