A*寻路算法实践

一、题目背景

随着多媒体设备、虚拟现实、增强现实、物联网等技术的飞跃发展，计算速度与存储容量的日益提高以及相关软件的研究取得长足进步，人工智能的应用得以进一步推广发展起来。地图寻径问题是人工智能技术的一个重要领域。在网络游戏中，寻径问题必须考虑多方面的因素，比如游戏地图中文件结构和起点与目标点之间是否可以连通以及游戏运行时运行内存资源占用、可扩展更新性、安全程度等。长久以来，游戏开发者在开发过程中为了实现这些绞尽脑汁。

在搜索寻径问题中，Dijkstra算法是目前许多工程解决最短路径问题采用的理论基础，只是不同工程对Dijkstra算法在不同方面采用了各异的改进方法。常见的搜索算法有深度优先算法（ＤＦＳ ）、广度优先算法（ＢＦＳ ）、迭代加深算法、双向广度优先搜索算法、ＩＤＡ＊ 算法、Ａ＊ 搜索等。它们分为盲目式与启发式两种。盲目式是指其没有目的性的搜索，其可以在一定的规则下全局进行搜索；而启发式则是指有目的性地朝着一定的目标进行搜索。深度优先算法意在每次先向深度中进行搜索，如果未找到结果，再换一条路线进行搜索查询，直到查询到结果。此算法较为容易理解，会占用更小的内存，但是可能会需要更长的时间。广度优先算法每次查询时，首先搜索周围，如若没有查找到结果，则扩大范围，直到查询到结果。此算法虽然速度较快但是占用内存偏多，可以应用到许多关于有速度要求的应用上。迭代加深算法在深度优先算法基础上，增加了一个深度记录，以防止在深度优先算法中无限制地搜索，等其查找到一定的深度时就进行返回。IDA＊算法在迭代加深算法基础上增加了一个评估函数，此函数可以对接下来的路径进行评估，从而更快地预估出路径是否存在结果，即可以说是对迭代加深算法的一种优化。但是困难的地方在于评估函数的编写，如果评估函数优秀，那效果良好。相反，如果评估函数一般，它可能会和上一代有着相同的浪费程度。

Ａ ＊ 算法是游戏开发中应用最为广泛的一种路径搜索方法，可以说它是广度优先算法（ ＢＦＳ ）的一个升级版。此算法使用了Dijkstra算法的节点信息、广度优先算法的节点扩展方式、加入队列判重、路径点估价函数等。 Ａ ＊ 算法的广泛应用证实了其在搜索路径中的优势与地位。其在人工智能中属于一种典型的启发式搜索算法。而相对于理论，更难的是如何将其应用在游戏工程中，因为游戏中需要考虑到更多元素，包括起点终点连通性以及障碍物、人物碰撞体等。

二、算法原理

    Ａ ＊ 算法是游戏开发中人工智能寻路方面最为常用的算法之一。此算法类似于对广度优先算法的优化，其原理也是在查询点周围进行寻找，其不同点

在于以下两个方面：

    第一方面为加入了估价函数：

F(n)=g(n)+h(n)

g（n）代表某点n从当前位置上距离起点的代价函数值，它是由有限个数起始点与目标点代价函数的值累加构成。h(n)代表点n从其位置上距离终点的代价函数值。即用F（n）代表n点总的路径代价。常用的经典启发函数代价计算方法 h（n）有：曼哈顿距离（Manhattan Distance）、对角线距离、欧几里得距离（Euclidean Distance）等。

第二方面为增加两个表（Open-List与Close-List）来进行路径点的筛选与扩展，更好地统计整理路径点，通过判断和比较来节省资源消耗。

三、算法实现

算法具体过程描述如下：

① 通过循环提取Open-List中的值并不断地比较寻找此时列表中代价最低的路径点，将代价最低点移除Open-List，加入 Close-List后进入 ②。持续循环此步骤直到Open-List中的路径点个数为０ 。

② 判断此路径点是否为寻路终点，若是则计算路径，直接进入④。否则，获得此点周围的非障碍点，进入③ 。

③ 判断周围非障碍点是否已经存在于Open-List中，如果存在，重新计算并更新路径点代价函数值。如若不存在，计算路径点代价函数值后并将路径点储存在Open-List中。后将 ① 中的提取点与此周围非障碍点设为父子关系，方便最终路径点的提取。

④ 得到最终点，依次根据节点的父子关系寻找父节点并存入数列中，直至寻找到初始路径点。数列中所有点的集合，即为寻路路径。

四、程序流程

//Grid.cs

using UnityEngine;

using System.Collections;

using System.Collections.Generic;



public class Grid : MonoBehaviour {

    public GameObject NodeWall;

    public GameObject Node;



    // 节点半径

    public float NodeRadius = 0.5f;

    // 过滤墙体所在的层

    public LayerMask WhatLayer;



    // 玩家

    public Transform player;

    // 目标

    public Transform destPos;





    /// <summary>

    /// 寻路节点

    /// </summary>

    public class NodeItem {

        // 是否是障碍物

        public bool isWall;

        // 位置

        public Vector3 pos;

        // 格子坐标

        public int x, y;



        // 与起点的长度

        public int gCost;

        // 与目标点的长度

        public int hCost;



        // 总的路径长度

        public int fCost {

            get {return gCost + hCost; }

        }



        // 父节点

        public NodeItem parent;



        public NodeItem(bool isWall, Vector3 pos, int x, int y) {

            this.isWall = isWall;

            this.pos = pos;

            this.x = x;

            this.y = y;

        }

    }



    private NodeItem[,] grid;

    private int w, h;



    private GameObject WallRange, PathRange;

    private List<GameObject> pathObj = new List<GameObject> ();



    void Awake() {

        // 初始化格子

        w = Mathf.RoundToInt(transform.localScale.x * 2);

        h = Mathf.RoundToInt(transform.localScale.y * 2);

        grid = new NodeItem[w, h];



        WallRange = new GameObject ("WallRange");

        PathRange = new GameObject ("PathRange");



        // 将墙的信息写入格子中

        for (int x = 0; x < w; x++) {

            for (int y = 0; y < h; y++) {

                Vector3 pos = new Vector3 (x*0.5f, y*0.5f, -0.25f);

                // 通过节点中心发射圆形射线，检测当前位置是否可以行走

                bool isWall = Physics.CheckSphere (pos, NodeRadius, WhatLayer);

                // 构建一个节点

                grid[x, y] = new NodeItem (isWall, pos, x, y);

                // 如果是墙体，则画出不可行走的区域

                if (isWall) {

                    GameObject obj = GameObject.Instantiate (NodeWall, pos, Quaternion.identity) as GameObject;

                    obj.transform.SetParent (WallRange.transform);

                }

            }

        }



    }



    // 根据坐标获得一个节点

    public NodeItem getItem(Vector3 position) {

        int x = Mathf.RoundToInt (position.x) * 2;

        int y = Mathf.RoundToInt (position.y) * 2;

        x = Mathf.Clamp (x, 0, w - 1);

        y = Mathf.Clamp (y, 0, h - 1);

        return grid [x, y];

    }



    // 取得周围的节点

    public List<NodeItem> getNeibourhood(NodeItem node) {

        List<NodeItem> list = new List<NodeItem> ();

        for (int i = -1; i <= 1; i++) {

            for (int j = -1; j <= 1; j++) {

                // 如果是自己，则跳过

                if (i == 0 && j == 0)

                    continue;

                int x = node.x + i;

                int y = node.y + j;

                // 判断是否越界，如果没有，加到列表中

                if (x < w && x >= 0 && y < h && y >= 0)

                    list.Add (grid [x, y]);

            }

        }

        return list;

    }



    // 更新路径

    public void updatePath(List<NodeItem> lines) {

        int curListSize = pathObj.Count;

        for (int i = 0, max = lines.Count; i < max; i++) {

            if (i < curListSize) {

                pathObj [i].transform.position = lines [i].pos;

                pathObj [i].SetActive (true);

            } else {

                GameObject obj = GameObject.Instantiate (Node, lines [i].pos, Quaternion.identity) as GameObject;

                obj.transform.SetParent (PathRange.transform);

                pathObj.Add (obj);

            }

        }

        for (int i = lines.Count; i < curListSize; i++) {

            pathObj [i].SetActive (false);

        }

    }

}

//FindPath.cs

using UnityEngine;

using System.Collections;

using System.Collections.Generic;



public class FindPath : MonoBehaviour {

    private Grid grid;



    // Use this for initialization

    void Start () {

        grid = GetComponent<Grid> ();

    }

   

    // Update is called once per frame

    void Update () {

        FindingPath (grid.player.position, grid.destPos.position);

    }



    // A*寻路

    void FindingPath(Vector3 s, Vector3 e) {

        Grid.NodeItem startNode = grid.getItem (s);

        Grid.NodeItem endNode = grid.getItem (e);



        List<Grid.NodeItem> openSet = new List<Grid.NodeItem> ();

        HashSet<Grid.NodeItem> closeSet = new HashSet<Grid.NodeItem> ();

        openSet.Add (startNode);



        while (openSet.Count > 0) {

            Grid.NodeItem curNode = openSet [0];



            for (int i = 0, max = openSet.Count; i < max; i++) {

                if (openSet [i].fCost <= curNode.fCost &&

                    openSet [i].hCost < curNode.hCost) {

                    curNode = openSet [i];

                }

            }



            openSet.Remove (curNode);

            closeSet.Add (curNode);



            // 找到的目标节点

            if (curNode == endNode) {

                generatePath (startNode, endNode);

                return;

            }



            // 判断周围节点，选择一个最优的节点

            foreach (var item in grid.getNeibourhood(curNode)) {

                // 如果是墙或者已经在关闭列表中

                if (item.isWall || closeSet.Contains (item))

                    continue;

                // 计算当前相领节点现开始节点距离

                int newCost = curNode.gCost + getDistanceNodes (curNode, item);

                // 如果距离更小，或者原来不在开始列表中

                if (newCost < item.gCost || !openSet.Contains (item)) {

                    // 更新与开始节点的距离

                    item.gCost = newCost;

                    // 更新与终点的距离

                    item.hCost = getDistanceNodes (item, endNode);

                    // 更新父节点为当前选定的节点

                    item.parent = curNode;

                    // 如果节点是新加入的，将它加入打开列表中

                    if (!openSet.Contains (item)) {

                        openSet.Add (item);

                    }

                }

            }

        }



        generatePath (startNode, null);

    }



    // 生成路径

    void generatePath(Grid.NodeItem startNode, Grid.NodeItem endNode) {

        List<Grid.NodeItem> path = new List<Grid.NodeItem>();

        if (endNode != null) {

            Grid.NodeItem temp = endNode;

            while (temp != startNode) {

                path.Add (temp);

                temp = temp.parent;

            }

            // 反转路径

            path.Reverse ();

        }

        // 更新路径

        grid.updatePath(path);

    }



    // 获取两个节点之间的距离

    int getDistanceNodes(Grid.NodeItem a, Grid.NodeItem b) {

        int cntX = Mathf.Abs (a.x - b.x);

        int cntY = Mathf.Abs (a.y - b.y);

        // 判断到底是那个轴相差的距离更远

        if (cntX > cntY) {

            return 14 * cntY + 10 * (cntX - cntY);

        } else {

            return 14 * cntX + 10 * (cntY - cntX);

        }

    }

}

五、程序运行结果

红色小球作为起始点，而蓝色小球作为目标点，键盘的wasd控制蓝色小球的移动，键盘方向键可以控制红色小球的移动；A*寻路算法可以实现在迷宫中用最短路径找寻目标点，上图中蓝色的路径就是算法所呈现出的最短路径。本次实验使用A*算法实现了一款类似迷宫的小游戏，可以已最快的路径实现起始点与目标点的相遇。

 

注释：

本次实验是使用unity游戏引擎进行实践。是对网上开源代码与模型进行修改与学习。