前言

A*算法是常用的游戲算法之一，也是初學(xué)者比較難掌握的一個(gè)算法。

本文在Unity中以GUI的方式形象的再現(xiàn)了A*算法的詳細(xì)步驟，

包括地圖的搜索、FGH的計(jì)算以及開(kāi)啟關(guān)閉列表的變化等。

博文首發(fā)地址：http://blog.csdn.net/duzixi

步驟一：

創(chuàng)建Unity新工程新場(chǎng)景

步驟二：

創(chuàng)建AStar.cs腳本，將以下代碼內(nèi)容粘貼覆蓋后，保存運(yùn)行即可

/// <summary>  
/// A*算法 Unity GUI實(shí)現(xiàn)  
/// 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,    // 常規(guī)  
    Obstacle,  // 障礙  
    Start,     // 起點(diǎn)  
    End        // 終點(diǎn)  
}  
  
// 定義格子類（繼承可比較接口 IComparable）  
public class Grid : IComparable{  
    public int x;       // x 坐標(biāo)  
    public int y;       // y 坐標(biāo)  
    public int F;       // 總評(píng)分  
    public int G;       // 從起點(diǎn)到當(dāng)前點(diǎn)的消耗值  
    public int H;       // 從當(dāng)前點(diǎn)到終點(diǎn)的估算值（直走10，斜走14）  
    public GridType gridType;  // 格子類型  
    public Grid fatherNode;  
  
    // 可比較接口的實(shí)現(xiàn)（用于排序）  
    public int CompareTo (object obj)  
    {     
        Grid g1 = (Grid) obj; // 強(qiáng)制類型轉(zhuǎn)換  
        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;          // 列數(shù)  
    private const int row = 5;          // 行數(shù)  
    private int size = 70;              // 大小  
  
    private Grid[,] map;                // 地圖（格子二維數(shù)組）  
    private const int xStart = 2;         
    private const int yStart = 1;         
    private const int xEnd = 2;           
    private const int yEnd = 5;          
  
    ArrayList openList;                 // 開(kāi)啟列表（重要�。。�  
    ArrayList closeList;                // 關(guān)閉列表（重要�。。�  
  
    // 初始化  
    void Start () {  
        map = new Grid[row, col];       // 創(chuàng)建地圖  
        for (int i = 0; i < row; i++) {  
            for (int j = 0; j < col; j++) {  
                map[i,j] = new Grid();  // 實(shí)例化格子  
                map[i,j].x = i;         // x坐標(biāo)賦值  
                map[i,j].y = j;         // y坐標(biāo)賦值  
            }  
        }  
  
        map[xStart, yStart].gridType = GridType.Start; // 確定開(kāi)始位置  
        map[xStart, yStart].H = Manhattan(xEnd, yEnd); // 初始化開(kāi)始位置的H值  
        map[xEnd, yEnd].gridType = GridType.End;       // 確定結(jié)束位置  
        for (int i = 1; i <= 3; i++) {                  // 確定障礙位置  
            map[i, 3].gridType = GridType.Obstacle;   
        }  
  
        openList = new ArrayList();                    // 初始化開(kāi)啟列表  
        openList.Add(map[xStart, yStart]);             // 將開(kāi)始節(jié)點(diǎn)放入開(kāi)放列表中  
        closeList = new ArrayList();                   // 初始化關(guān)閉列表  
    }  
  
    void OnGUI() {  
        // 繪制地圖  
        for (int i = 0; i < row; i++) {  
            for (int j = 0; j < col; j++) {  
                // 根據(jù)格子類型設(shè)置背景顏色  
                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();  
        }  
  
        // 繪制開(kāi)啟列表  
        for (int j = 0; j < openList.Count; j++) {  
            GUI.Button(new Rect(j * size, (row + 1) * size, size, size), FGH((Grid)openList[j]));  
        }  
  
        // 繪制關(guān)閉列表  
        for (int j = 0; j < closeList.Count; j++) {  
            GUI.Button(new Rect(j * size, (row + 2) * size, size, size), FGH((Grid)closeList[j]));  
        }  
    }  
  
    // 通過(guò)逆向追溯找到路徑  
    void showFatherNode(Grid grid) {  
        if (grid.fatherNode != null) {  
            print (grid.fatherNode.x + "," + grid.fatherNode.y);  
            showFatherNode(grid.fatherNode);      
        }   
    }  
  
    // 走下一步  
    void NextStep() {  
        //  0. 只要開(kāi)啟列表有節(jié)點(diǎn), 就進(jìn)行下一個(gè)過(guò)程  
        if (openList.Count == 0) {  
            print ("Over !");  
            return;  
        }  
  
        //  1. 從開(kāi)放列表中選擇第一個(gè)節(jié)點(diǎn)并將其作為當(dāng)前節(jié)點(diǎn)  
        Grid grid = (Grid)openList[0];  
        if (grid.gridType == GridType.End) {  
            showFatherNode(grid);  
            print ("Over !");  
            return;   
        }  
  
        //  2. 獲得這個(gè)當(dāng)前節(jié)點(diǎn)不是障礙物的鄰近節(jié)點(diǎn)  
        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. 對(duì)于每一個(gè)鄰近節(jié)點(diǎn),查看是否已在關(guān)閉列表中.  
                    if (x >= 0 && x < row && y >= 0 && y < col &&  
                        map[x,y].gridType != GridType.Obstacle &&   
                        !closeList.Contains(map[x, y]) ) {  
                        // 4.如果不在, 計(jì)算所有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.將代價(jià)數(shù)據(jù)存儲(chǔ)在鄰近節(jié)點(diǎn)中,并且將當(dāng)前節(jié)點(diǎn)保存為該鄰近節(jié)點(diǎn)的父節(jié)點(diǎn).  
                        //    最后我們將使用這個(gè)父節(jié)點(diǎn)數(shù)據(jù)來(lái)追蹤實(shí)際路徑.  
                        map[x, y].fatherNode = grid;  
                        //  6.將鄰近節(jié)點(diǎn)存儲(chǔ)在開(kāi)放列表中.  
                        if (!openList.Contains(map[x, y])) {  
                            openList.Add(map[x, y]);  
                        }  
                        //  7.根據(jù)F,以升序排列開(kāi)放列表.  
                        openList.Sort();  
                    }  
                }  
            }     
        }  
        //  8. 如果沒(méi)有鄰近節(jié)點(diǎn)需要處理, 將當(dāng)前節(jié)點(diǎn)放入關(guān)閉列表并將其從開(kāi)放列表中移除.  
        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;  
    }  
}  

步驟三：

點(diǎn)擊畫(huà)面上的“Go Next”按鈕，即可觀察每部計(jì)算詳情

（注：最終找到的路徑在控制臺(tái)里可看到，這個(gè)部分沒(méi)有可視化）

后語(yǔ)

A*算法的具體實(shí)現(xiàn)細(xì)節(jié)有很多，本文腳本只是給出了其中一種。

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

標(biāo)簽： 代碼 腳本 搜索

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。