前言
A*算法是常用的游戏算法之一，，也是初学者比较难掌握的一个算法。
本文在Unity中以GUI的方式形象的再现了A*算法的详细步骤，
包括地图的搜索、FGH的计算以及开启关闭列表的变化等。
博文首发地址：
步骤一：
创建Unity新工程新场景
步骤二：
创建AStar.cs脚本，将以下代码内容粘贴覆盖后，保存运行即可
<span style="font-size:14px;">/// <summary>/// A*算法 Unity GUI实现/// Created by 杜子兮(duzixi.com) 2015.2.19/// 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、Gint 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;}}</span>
步骤三：
点击画面上的“Go Next”按钮，即可观察每部计算详情
世界会向那些有目标和远见的人让路(冯两努——香港着名推销商
