算法-A星寻路｜默然的博客

关于自动寻路，在游戏中还是经常会遇到的。如角色如何代价最小(距离少，时间快，方式支持)移动到某个位置。本篇记录下A*寻路的流程与优化。

为了做一个可以方便展示在web的demo，更好拆解寻路的步骤，所以本篇用了cocos creater + ts实现。

A星算法是dijkstra的升级版(算法-迪杰斯特拉)，也是属于广度搜索遍历，不同于dijkstra，A星不需要遍历图中所有的节点。而是尽可能的去靠近终点。可以做个想象：地图比作一个挂起来的迷宫，起点在上方，终点在下方，从上方注入水，水会随着重力尽可能向下方(终点)流去。

所以AStar 是可以找到一个最快的路径，即当前的最优解，但这个最快不是唯一的，也可能不是最优的。有点像贪心。其时间复杂度为：O(logN)

A星算法用到的几个变量

1. 设定起点为A，终点为B。
2. 开放列表(OpenList)：记录所有待检测的节点。
3. 关闭列表(CloseList)：记录所有已经检测过的节点。
4. G值：当前节点到下一个节点N(八点 之一)的代价。
5. H值：下一个节点N到终点B的代价。（忽略有墙）
6. F值：F = G + H

代价值的计算：

• 垂直或者左右相邻记作：10
• 斜对角相邻记作：$\sqrt{10+10}\approx 14$

约定

• 八点指：“上、下、左、右、左上、左下、右上、右下”共八个点。
• 有效八点指：八点中剔除：
  1. 不可达的点(墙)
  2. 已经加入CloseList / OpenList的点
• 三围指 上面定义的三个值：“G, H, F”。

算法流程

1. 将起点作为当前点放入OpenList。
2. 遍历所有OpenList找到F值最小的点(MinFNode)，如果F相同则先择H值最小的点。
3. 把MinFNode从OpenList移除，并加入CloseList。
4. 1. 没有有效八点，回到步骤2。
   2. 拥有有效八点,遍历MinFNode的有效八点，根据以下情况计算三围。
      • 相邻点不在OpenList中。计算三围，加入OpenList。
      • 相邻点已在OpenList中, 跳过。
5. 如果当前点是终点则结束寻路；否则回到步骤2。
6. 直到达到终点，回溯找到起点。

可视化Demo

用cocos creater 做了一个demo，详细展示出寻路的步骤。
如下，绿色节点是在OpenList中找到的最小节点，只需依次点击绿色方块，直到达到终点。最后绘制出寻路路径。

代码实现

export class PathFind extends Component {
    @property({type: Vec2, displayName:"开始点"})
    private startPos:Vec2 = new Vec2(0, 0);
    @property({type: Vec2, displayName:"结束点"})
    private endPos: Vec2 = new Vec2(1, 1);

    private StartNode: MapNode;
    private EndNode: MapNode;

    // 开放列表
    private OpenList: IDict<string, MapNode> = new IDict<string, MapNode>();
    // 关闭列表
    private CloseList: IDict<string, MapNode> = new IDict<string, MapNode>();

    // 加入开放列表
    private Add2OpenList(node: MapNode): void{ node.SetColor(Color.CYAN); this.OpenList.Add(node.GetKey(), node); }
    // 加入关闭列表
    private Add2CloseList(node: MapNode): void{ node.SetColor(Color.GRAY); this.CloseList.Add(node.GetKey(), node); }



    private rowNodes: IMapRow[] = [];
    protected onLoad(): void {
        let rowsNode = this.node.getChildByName('Rows');
        let rows = rowsNode.children;
        for (let i = 0; i < rows.length; i++) {
            const element = rows[i];
            let childs = element.children;
            let cells:MapNode[] = [];
            for (let j = 0,jMax = childs.length; j < jMax; j++) {
                const cell = childs[j].getComponent(MapNode);
                cell.Init(j, i);
                cells.push(cell);
            }
            let row:IMapRow = {row: element, cells: cells};

            this.rowNodes.push(row);
        }

        Messenger.AddListener('click_node', this.ClickMapNodeCallback, this);
    }
    
    protected start(): void {
        this.StartNode = this.GetNode(this.startPos.x, this.startPos.y);
        this.StartNode.NodeType = NodeType.Start;

        this.EndNode = this.GetNode(this.endPos.x, this.endPos.y);
        this.EndNode.NodeType = NodeType.End;

        this.Add2OpenList(this.StartNode);
        this.RefreshEightNode(this.StartNode, this.EndNode);
        let node = this.GetMinOpenListNode();
        node.ClickEnable = true;
    }

    protected onDestroy(): void {
        Messenger.RemoveListener('click_node', this.ClickMapNodeCallback, this);
    }

    // 左上角为起点↓→
    private GetNode(x:number, y:number): MapNode{
        let row:IMapRow = this.rowNodes[y];
        let cells:MapNode[] = row.cells;
        return row.cells[x];
    }

    // 获得8点
    // 1. 不超界
    // 2. 不是墙
    // 3. 不在开放列表，不在闭合列表
    private GetEightNode(node:MapNode): MapNode[]{
        let data = [];
        let x = node.PosX;
        let y = node.PosY;

        let checkAndAdd=(item)=>{
            let key = item.GetKey();
            if(item.NodeType != NodeType.Wall && !this.OpenList.HasKey(key) && !this.CloseList.HasKey(key)){
                item.PreNode = node;
                data.push(item);
            }
        };

        if(x > 0){ let left = this.GetNode(x-1, y);     checkAndAdd(left); }
        if(x < 9){ let right= this.GetNode(x+1, y);     checkAndAdd(right); }
        if(y > 0){ let top  = this.GetNode(x, y-1);     checkAndAdd(top); }
        if(y < 6){ let buttom = this.GetNode(x, y+1);   checkAndAdd(buttom); }
        if(x>0 && y>0){let l_t = this.GetNode(x-1, y-1);checkAndAdd(l_t); }
        if(x>0 && y<6){let l_b = this.GetNode(x-1, y+1);checkAndAdd(l_b); }
        if(x<9 && y>0){let r_t = this.GetNode(x+1, y-1);checkAndAdd(r_t); }
        if(x<9 && y<6){let r_b = this.GetNode(x+1, y+1);checkAndAdd(r_b); }

        return data;
    }

    // 刷新8点
    private RefreshEightNode(node: MapNode, endNode: MapNode): void{
        let nodes = this.GetEightNode(node);
        console.log(`8点个数：${nodes.length}`);
        if(nodes.length == 0) return;

        // 从openList移除,加入闭合列表
        this.OpenList.Remove(node.GetKey());
        this.Add2CloseList(node);

        for (let i = 0; i < nodes.length; i++) {
            const element = nodes[i];
            element.SetColor(math.Color.CYAN);
            let g_x = Math.abs(node.PosX - element.PosX);
            let g_y = Math.abs(node.PosY - element.PosY);
            let g_value = g_x + g_y == 1 ? 10 : 14;
            element.GValue = g_value;

            let h_x = Math.abs(endNode.PosX - element.PosX);
            let h_y = Math.abs(endNode.PosY - element.PosY);
            let min = Math.min(h_x, h_y);
            let max = Math.max(h_x, h_y);
            let h_value = 14*min + 10* (max-min);
            element.HValue = h_value;
            element.FValue = g_value + h_value;
            this.OpenList.Add(element.GetKey(), element);
        }
    }

    // 获得OpenList中最小节点
    private GetMinOpenListNode(): MapNode{
        let items = this.OpenList.Values();
        if(items.length == 0) return null;

        let result:MapNode = items[0];
        for(let i = 1,iMax = items.length;i<iMax;i++){

            if(result.FValue > items[i].FValue) {
                result = items[i];
            }
            else if(result.FValue == items[i].FValue){
                if(result.HValue > items[i].HValue){
                    result = items[i];
                }
            }
        }
        let nodes = this.GetEightNode(result);
        if(nodes.length > 0){
            result.SetColor(Color.GREEN);
            return result;
        }
        this.OpenList.Remove(result.GetKey());
        this.Add2CloseList(result);
        return this.GetMinOpenListNode();
    }

    // 点击节点
    private ClickMapNodeCallback(clickNode: MapNode): void{
        console.log(clickNode.PosX, clickNode.PosY);
        if(clickNode == this.EndNode){
            this.PrintSearchPath(this.EndNode);
            return;
        }

        clickNode.ClickEnable = false;
        this.Add2OpenList(clickNode);
        this.RefreshEightNode(clickNode, this.EndNode);
        let node = this.GetMinOpenListNode();
        if(node == null) return;

        node.ClickEnable = true;
    }

    // 回溯，展示完整寻路路径
    private PrintSearchPath(node?: MapNode):void{
        if(node == null){ node = this.EndNode; }
        node.SetColor(math.Color.GREEN);
        if(node == this.StartNode) return;
        if(node.PreNode == null) return;

        this.PrintSearchPath(node.PreNode);
    }
}

每个节点挂载的脚本

export class MapNode extends Component {
    @property(Label) private labelG:Label = null;
    @property(Label) private labelH:Label = null;
    @property(Label) private labelF:Label = null;

    @property({type: Enum(NodeType), serializable: true, visible: true})
    public _nodeType = NodeType.Road;

    public PosX: number;
    public PosY: number;
    private sprite:Sprite = null;
    private button:Button = null;

    // 记录前置节点
    public PreNode: MapNode;

    public get NodeType(){return this._nodeType; }
    public set NodeType(type: NodeType){
        switch(type){
            case NodeType.Road:  break;
            case NodeType.Wall:  this.SetColor(math.Color.BLACK); break;
            case NodeType.Start: this.SetColor(math.Color.GREEN); this.labelF.string = '开始点'; break;
            case NodeType.End:   this.SetColor(math.Color.RED); this.labelF.string = '结束点'; break;
        }
        this._nodeType = type;
    }

    // G
    private _g_value:number;
    public get GValue(){ return this._g_value; }
    public set GValue(g: number){ this._g_value = g; this.labelG.string = g+""; }
    // H
    private _h_value:number;
    public get HValue(){ return this._h_value; }
    public set HValue(h: number){ this._h_value = h; this.labelH.string = h+""; }
    // F
    private _f_value:number;
    public get FValue(){ return this._f_value; }
    public set FValue(f: number){ this._f_value = f; this.labelF.string = f+""; }

    public set ClickEnable(enabled: boolean){ this.button.enabled = enabled; }

    protected onLoad(): void {
        this.labelG.string = '';
        this.labelH.string = '';
        this.labelF.string = '';
        
        this.sprite = this.getComponent(Sprite);
        this.button = this.getComponent(Button);

        this.NodeType = this._nodeType;
        this.button.enabled = false;

        this.button.node.on(Button.EventType.CLICK,()=>{
            Messenger.BroadcastT<MapNode>("click_node", this);
        }, this);
    }

    public Init(x:number, y: number){this.PosX = x; this.PosY = y; }

    // 设置颜色
    public SetColor(color:Color){ this.sprite.color = color; }

    public GetKey(): string{ return `${this.PosX}_${this.PosY}`; }
}

优化

对于长距离导航

如果距离比较远，中间的障碍物比较多时，寻路所需时间就会逐渐增加，甚至达到CPU的瓶颈，导致卡顿。可以提前计算出一些常用路径存放到数据文件中。如下图中所示
A、B点之间的路径为离线计算好的。现在想要C点走到D点，只需要开始C点找到最近的导航点A，结束点找到导航点B.然后 C—>A—>B—>D。

相关阅读

• 分治算法解决问题再回顾
• 目录及资源路径规范整理(03)