前言

A*算法是常用的游戏算法之一，也是初学者比较难掌握的一个算法。

本文在Unity中以GUI的方式形象的再现了A*算法的详细步骤，

包括地图的搜索、FGH的计算以及开启关闭列表的变化等。

博文首发地址：http://blog.csdn.net/duzixi

步骤一：

创建Unity新工程新场景

步骤二：

创建AStar.cs脚本，将以下代码内容粘贴覆盖后，保存运行即可

/// <summary>    /// A*算法 Unity GUI实现    /// Created by 杜子兮(duzixi.com) 2015.2.19    /// www.lanou3g.com All Rights Reserved    /// </summary>        using UnityEngine;    using System.Collections;    using System; // 用到排序接口        // 枚举：定义格子类型    public enum GridType {        Normal,    // 常规        Obstacle,  // 障碍        Start,     // 起点        End        // 终点    }        // 定义格子类（继承可比较接口 IComparable）    public class Grid : IComparable{        public int x;       // x 坐标        public int y;       // y 坐标        public int F;       // 总评分        public int G;       // 从起点到当前点的消耗值        public int H;       // 从当前点到终点的估算值（直走10，斜走14）        public GridType gridType;  // 格子类型        public Grid fatherNode;            // 可比较接口的实现（用于排序）        public int CompareTo (object obj)        {               Grid g1 = (Grid) obj; // 强制类型转换            if (this.F < g1.F)    // 升序                return -1;              if (this.F > g1.F)    // 降序                return 1;              return 0;             // 相等        }    }        // A*算法    public class AStar : MonoBehaviour {        private const int col = 7;          // 列数        private const int row = 5;          // 行数        private int size = 70;              // 大小            private Grid[,] map;                // 地图（格子二维数组）        private const int xStart = 2;               private const int yStart = 1;               private const int xEnd = 2;                 private const int yEnd = 5;                    ArrayList openList;                 // 开启列表（重要！！）        ArrayList closeList;                // 关闭列表（重要！！）            // 初始化        void Start () {            map = new Grid[row, col];       // 创建地图            for (int i = 0; i < row; i++) {                for (int j = 0; j < col; j++) {                    map[i,j] = new Grid();  // 实例化格子                    map[i,j].x = i;         // x坐标赋值                    map[i,j].y = j;         // y坐标赋值                }            }                map[xStart, yStart].gridType = GridType.Start; // 确定开始位置            map[xStart, yStart].H = Manhattan(xEnd, yEnd); // 初始化开始位置的H值            map[xEnd, yEnd].gridType = GridType.End;       // 确定结束位置            for (int i = 1; i <= 3; i++) {                  // 确定障碍位置                map[i, 3].gridType = GridType.Obstacle;             }                openList = new ArrayList();                    // 初始化开启列表            openList.Add(map[xStart, yStart]);             // 将开始节点放入开放列表中            closeList = new ArrayList();                   // 初始化关闭列表        }            void OnGUI() {            // 绘制地图            for (int i = 0; i < row; i++) {                for (int j = 0; j < col; j++) {                    // 根据格子类型设置背景颜色                    Color bgColor;                    if (map [i, j].gridType == GridType.Start) {                        bgColor = Color.green;                    } else if (map [i, j].gridType == GridType.End) {                        bgColor = Color.red;                    } else if (map [i, j].gridType == GridType.Obstacle) {                        bgColor = Color.blue;                    } else if (closeList.Contains (map [i, j])) {                        bgColor = Color.black;                    } else {                        bgColor = Color.gray;                    }                    GUI.backgroundColor = bgColor;                    // 用按钮表示格子                    GUI.Button(new Rect(j * size, i * size, size, size), FGH (map[i, j]));                }            }                        if (GUI.Button(new Rect(col * size, 0 , size, size), "Go Next")) {                NextStep();            }                // 绘制开启列表            for (int j = 0; j < openList.Count; j++) {                GUI.Button(new Rect(j * size, (row + 1) * size, size, size), FGH((Grid)openList[j]));            }                // 绘制关闭列表            for (int j = 0; j < closeList.Count; j++) {                GUI.Button(new Rect(j * size, (row + 2) * size, size, size), FGH((Grid)closeList[j]));            }        }            // 通过逆向追溯找到路径        void showFatherNode(Grid grid) {            if (grid.fatherNode != null) {                print (grid.fatherNode.x + "," + grid.fatherNode.y);                showFatherNode(grid.fatherNode);                }         }            // 走下一步        void NextStep() {            //  0. 只要开启列表有节点, 就进行下一个过程            if (openList.Count == 0) {                print ("Over !");                return;            }                //  1. 从开放列表中选择第一个节点并将其作为当前节点            Grid grid = (Grid)openList[0];            if (grid.gridType == GridType.End) {                showFatherNode(grid);                print ("Over !");                return;             }                //  2. 获得这个当前节点不是障碍物的邻近节点            for (int m = -1; m <= 1; m++) {                for (int n = -1; n <= 1; n++) {                    if ( !( m == 0 && n == 0 )) {                        int x = grid.x + m;                        int y = grid.y + n;                        //  3. 对于每一个邻近节点,查看是否已在关闭列表中.                        if (x >= 0 && x < row && y >= 0 && y < col &&                            map[x,y].gridType != GridType.Obstacle &&                             !closeList.Contains(map[x, y]) ) {                            // 4.如果不在, 计算所有F、H、G                            int g = grid.G + (int)(Mathf.Sqrt(Mathf.Abs(m) + Mathf.Abs(n)) * 10);                            if (map[x, y].G == 0 || g < map[x, y].G) {                                map [x, y].G = g;                            }                            map[x, y].H = Manhattan(x, y);                            map[x, y].F = map[x, y].G + map[x, y].H;                            //  5.将代价数据存储在邻近节点中,并且将当前节点保存为该邻近节点的父节点.                            //    最后我们将使用这个父节点数据来追踪实际路径.                            map[x, y].fatherNode = grid;                            //  6.将邻近节点存储在开放列表中.                            if (!openList.Contains(map[x, y])) {                                openList.Add(map[x, y]);                            }                            //  7.根据F,以升序排列开放列表.                            openList.Sort();                        }                    }                }               }            //  8. 如果没有邻近节点需要处理, 将当前节点放入关闭列表并将其从开放列表中移除.            closeList.Add(grid);            openList.Remove(grid);        }            // H值(曼哈顿估算法)        int Manhattan(int x, int y) {            return (int)(Mathf.Abs(xEnd - x) + Mathf.Abs(yEnd - y)) * 10;        }            // 将格子FGH 以字符串形式显示        string FGH(Grid grid) {            string fgh = "F:" + grid.F + "\n";            fgh += "G:" + grid.G + "\n";            fgh += "H:" + grid.H + "\n";            fgh += "(" + grid.x + "," + grid.y + ")";            return fgh;        }    }  

步骤三：

点击画面上的“Go Next”按钮，即可观察每部计算详情

（注：最终找到的路径在控制台里可看到，这个部分没有可视化）

后语

A*算法的具体实现细节有很多，本文脚本只是给出了其中一种。

另外，按照这个算法障碍墙是可以斜穿的，若要避免斜穿还需进一步修改。