A*算法的GUI實現

前言

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*算法的具體實現細節有很多，本文腳本只是給出了其中一種。

另外，按照這個算法障礙墻是可以斜穿的，若要避免斜穿還需進一步修改。