1. 前文

先說SLG是什么，SLG=Simulation Game，策略類游戲，現特指回合制策略游戲以及即時SLG，有別于SIM（Simulation）類“生活“模擬游戲，SLG雖然也是縮寫的simulation（模擬但與經營類意思不同），卻是“戰爭策略“模擬游戲的總稱，

而本文要說的是SLG游戲中的一種分類，國產手游中比較具有代表性的有：率土之濱、三國志戰略版、宏圖之下，由于我們是要介紹A*演算法相關內容，所以我們貼幾張關于戰場的圖，以方便我們有一個理解，

以下三個游戲由發行時間先后順序展示：

率土之濱
三國志戰略版

在這里插入圖片描述

鴻圖之下

在這里插入圖片描述

那么有上述三個游戲，其沙盤布局如下：

在這里插入圖片描述

傳統的A*演算法就是用率土之濱的資料結構，而隨著沙盤游戲的不斷發展地圖的嵌入方式發生了變化，三國志戰略版錯開了50%，鴻圖之下則采用正六邊形的方式展示，

2. 演示代碼準備

以下使用C#+WPF，VS2019進行的代碼演示，

3. 深度優先和廣度優先

深度優先遍歷(Depth First Search, 簡稱 DFS) 與廣度優先遍歷(Breath First Search)是圖論中兩種非常重要的演算法，生產上廣泛用于拓撲排序，尋路(走迷宮)，搜索引擎，爬蟲等，也頻繁出現在 leetcode，高頻面試題中，

3.1 深度優先

/// <summary>
/// 深度優先
/// </summary>
/// <param name="sender"></param>
/// <param name="e"></param>
private void btnDFS_Click(object sender,RoutedEventArgs e)
{
    dicCache = new Dictionary<string, bool>();
    Tuple<int, int> pStartIndex = pStartShapeSquare.Tag as Tuple<int, int>;    
    DFS_WayFinding(pStartIndex.Item1, pStartIndex.Item2);
}

private bool DFS_WayFinding(int index1, int index2)
{
    if (index1 < 0 || index1 >= CrosswiseNodeCount)
    {
        return false;
    }
    if (index2 < 0 || index2 >= LengthwaysNodeCount)
    {
        return false;
    }

    string strTag = $"{index1},{index2}";
    if (dicCache.ContainsKey(strTag))
    {
        return false;
    }
    else
    {
        dicCache.Add(strTag,true);
    }

    ShapeSquare shapeSquare = PlotShapeSquare[index1, index2];
    if (shapeSquare is ShapeSquare_BlockingPoint)
    {
        return false;
    }
    else if (shapeSquare == pEndShapeSquare)
    {
        return true;
    }
    
    shapeSquare.Fill = Brushes.BurlyWood;
    Thread.Sleep(10);
    System.Windows.Forms.Application.DoEvents();

    if (DFS_WayFinding(index1 - 1, index2))
    {
        return true;
    }
    else if (DFS_WayFinding(index1, index2 - 1))
    {
        return true;
    }
    else if (DFS_WayFinding(index1 + 1, index2))
    {
        return true;
    }
    else if (DFS_WayFinding(index1, index2 + 1))
    {
        return true;
    }
    return false;
}

在這里插入圖片描述

3.2 廣度優先

private void btnBFS_Click(object sender, RoutedEventArgs e)
{
    dicCache = new Dictionary<string, bool>();
    Tuple<int, int> pStartIndex = pStartShapeSquare.Tag as Tuple<int, int>;
    BFS_WayFinding(pStartIndex);
}

/// <summary>
 /// 廣度優先
 /// </summary>
 /// <param name=""></param>
 /// <returns></returns>
private bool BFS_WayFinding(Tuple<int, int> pIndex)
{
    Queue<Tuple<int, int>> BFSQueue = new Queue<Tuple<int, int>>();
    BFSQueue.Enqueue(pIndex);
    string strTag = $"{pIndex.Item1},{pIndex.Item2}";
    dicCache.Add(strTag, true);
    while (BFSQueue.Count!=0)
    {
        Tuple<int, int> pShapeSquareIndex= BFSQueue.Dequeue();
        ShapeSquare shapeSquare = PlotShapeSquare[pShapeSquareIndex.Item1, pShapeSquareIndex.Item2]; 
        if (shapeSquare == pEndShapeSquare)
        {
            return true;
        }
        shapeSquare.Fill = Brushes.BurlyWood;
        Thread.Sleep(10);
        System.Windows.Forms.Application.DoEvents();
        if (IsRange(pShapeSquareIndex.Item1-1, pShapeSquareIndex.Item2))
        {
            BFSQueue.Enqueue(new Tuple<int, int>(pShapeSquareIndex.Item1 - 1, pShapeSquareIndex.Item2));
        }
        if (IsRange(pShapeSquareIndex.Item1 , pShapeSquareIndex.Item2 - 1))
        {
            BFSQueue.Enqueue(new Tuple<int, int>(pShapeSquareIndex.Item1, pShapeSquareIndex.Item2 - 1));
        }
        if (IsRange(pShapeSquareIndex.Item1 + 1, pShapeSquareIndex.Item2))
        {
            BFSQueue.Enqueue(new Tuple<int, int>(pShapeSquareIndex.Item1 + 1, pShapeSquareIndex.Item2));
        }
        if (IsRange(pShapeSquareIndex.Item1 , pShapeSquareIndex.Item2 + 1))
        {
            BFSQueue.Enqueue(new Tuple<int, int>(pShapeSquareIndex.Item1, pShapeSquareIndex.Item2 + 1));
        }
    }
    return false;
}

private bool IsRange(int index1, int index2)
{
    if (index1 < 0 || index1 >= CrosswiseNodeCount)
    {
        return false;
    }
    if (index2 < 0 || index2 >= LengthwaysNodeCount)
    {
        return false;
    }
    ShapeSquare shapeSquare = PlotShapeSquare[index1, index2];
    if (shapeSquare is ShapeSquare_BlockingPoint)
    {
        return false;
    }
    string strTag = $"{index1},{index2}";
    if (dicCache.ContainsKey(strTag))
    {
        return false;
    }
    else
    {
        dicCache.Add(strTag, true);
    }
    return true;
}

在這里插入圖片描述

3.3 特點

如果深搜是一個人，那么他的性格一定倔得像頭牛！他從一點出發去旅游，只朝著一個方向走，除非路斷了，他絕不改變方向！除非四個方向全都不通或遇到終點，他絕不后退一步！因此，他的姐姐廣搜總是嘲笑他，說他是個一根筋、不撞南墻不回頭的家伙，

深搜很討厭他姐姐的嘲笑，但又不想跟自己的親姐姐鬧矛盾，于是他決定給姐姐講述自己旅途中的經歷，來改善姐姐對他的看法，他成功了，而且只講了一次，從那以后他姐姐不僅再沒有嘲笑過他，而且連看他的眼神都充滿了贊賞，他以為是自己路上的各種英勇征服了姐姐，但他不知道，其實另有原因……

深搜是這樣跟姐姐講的：關于旅行呢，我并不把目的地的風光放在第一位，而是更注重于沿路的風景，所以我不會去追求最短路，而是把所有能通向終點的路都走一遍，可是我并不知道往哪走能到達目的地，于是我只能每到一個地方，就向當地的人請教各個方向的道路情況，為了避免重復向別人問同一個方向，我就給自己規定：先問北，如果有路，那就往北走，到達下一個地方的時候就在執行此規定，如果往北不通，我就再問西，其次是南、東，要是這四個方向都不通或者抵達了終點，那我回到上一個地方，繼續探索其他沒去過的方向，我還要求自己要記住那些幫過他的人，但是那些給我幫倒忙的、讓我白費力氣的人，要忘記他們，有了這些規定之后，我就可以大膽的往前走了，既不用擔心到不了不目的地，也不用擔心重復走以前的路，

如果廣搜是一個人，那么她一定很貪心，而且喜新厭舊！她從一點出發去旅游，先把與起點相鄰的地方全部游覽一遍，然后再把與她剛游覽過的景點相鄰的景點全都游覽一邊……一直這樣，直至所有的景點都游覽一遍，

3.4 講解與備忘

上文中深度優先我們使用的是遞回的方式而廣度優先使用的是佇列，而在網路上標準寫法是深度優先采用的堆疊，廣度優先采用的佇列，兩者采用兩個資料結構的不同特點，保證遍歷節點的優先性，比如堆疊的特點是后進先出，從而保證其每一次遍歷到的子節點都先遍歷，而佇列的特點是先進先出，從而保證每一次遍歷的子節點都在后面排隊，而佇列前方的先遍歷，從而保證同級子節點的遍歷的優先性，

4. A星演算法

書接上文，我們降到了深度優先和廣度優先，上述兩個演算法都是窮舉式演算法，而（A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法，也是許多其他問題的常用啟發式演算法，A*演算法作為Dijkstra演算法（后續再用篇幅來闡述Dijkstra演算法）的擴展，因其高效性而被廣泛應用于尋路及圖的遍歷，

名詞解釋：

直接搜索演算法：直接在實際地圖上進行搜索，不經過任何預處理；
啟發式演算法：通過啟發函式引導演算法的搜索方向；
靜態圖搜索演算法：被搜索的圖的權值不隨時間變化（后被證明同樣可以適用于動態圖的搜索），

公式表示為： f(n)=g(n)+h(n)

其中，

f(n) 是從初始狀態經由狀態n到目標狀態的代價估計，
g(n) 是在狀態空間中從初始狀態到狀態n的實際代價，
h(n) 是從狀態n到目標狀態的最佳路徑的估計代價（歐幾里（斜邊的長度）/曼哈頓距離（x的距離+y的距離差）），

少逼逼，我們來分析演算法，

結合上文，我們說過深度優先和廣度優先都是窮舉演算法而A星演算法是屬于啟發式演算法,那么是通過什么做到啟發的呢！

鑒于視頻比博客更加有代入感以及程序性，推薦大家看： https://www.bilibili.com/video/BV147411u7r5?from=search&seid=14263924862056244840

4.1 基本原理

A星尋路演算法的基本原理就是不停的找自己周圍的點，選出一個新的點作為起點再次回圈

在這里插入圖片描述

4.2 A星演算法的詳細原理

尋路消耗公式：

f(尋路消耗)=g(離起點的距離)+h(離終點的距離)

g(離起點的距離)：代表離起點的距離：

g ( n ) = ( x 1 ? x 2 ) 2 + ( y 1 ? y 2 ) 2 g(n)=\sqrt{(x1-x2)^2+(y1-y2)^2} g(n)=(x1?x2)2+(y1?y2)2 ?

h(曼哈頓距離)：圖上數格子

h ( n ) = ∣ x 1 ? x 2 ∣ + ∣ y 1 ? y 2 ∣ h(n)=|x1-x2|+|y1-y2| h(n)=∣x1?x2∣+∣y1?y2∣

在這里插入圖片描述

開啟串列：

當前起點我們需要尋找的串列
關閉串列：

已經尋找完畢的串列
格子物件的父物件：

每一次尋找的格子節點的父物件，如F1的父物件為起點,F2的父物件為F1,以此類推，

最后基于關閉串列中的集合，通過格子的父物件從節點開始逆推我們可以找到一條路徑，

4.3 節選代碼

using GraphBaseFramewark;
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows.Media;

namespace GraphAStarAlgorithm
{
    /// <summary>
    /// A星尋路演算法
    /// </summary>
    class AStarAlgorithm
    {
        ShapeSquare[,] PlotShapeSquare = null;
        int CrosswiseNodeCount = 0;
        int LengthwaysNodeCount = 0;
        public AStarAlgorithm(ShapeSquare[,] plotShapeSquare, int crosswiseNodeCount,int lengthwaysNodeCount)
        {
            PlotShapeSquare = plotShapeSquare;
            CrosswiseNodeCount = crosswiseNodeCount;
            LengthwaysNodeCount = lengthwaysNodeCount;
        }

        /// <summary>
        /// 關閉串列
        /// </summary>
        Dictionary<ShapeSquare, ShapeSquare> dicClose = new Dictionary<ShapeSquare, ShapeSquare>();

        /// <summary>
        /// 演算法運行
        /// </summary>
        /// <param name="pStartShapeSquare"></param>
        /// <param name="pEndShapeSquare"></param>
        public void AlgorithmRun(ShapeSquare pStartShapeSquare, ShapeSquare pEndShapeSquare)
        {
            Tuple<int, int> pStartIndex = pStartShapeSquare.Tag as Tuple<int, int>;
            dicClose.Add(pStartShapeSquare, null);

            FindWayInfo(pStartIndex, pStartShapeSquare, pEndShapeSquare);

            ShapeSquare pWayShapeSquare = pEndShapeSquare;
            while (pWayShapeSquare!= pStartShapeSquare)
            {
                pWayShapeSquare.Fill = Brushes.YellowGreen;
                Thread.Sleep(10);
                System.Windows.Forms.Application.DoEvents();

                pWayShapeSquare = dicClose[pWayShapeSquare];
            }

        }

        private bool FindWayInfo(Tuple<int, int> pStartIndex, ShapeSquare pStartShapeSquare, ShapeSquare pEndShapeSquare)
        {
            ConcurrentDictionary<ShapeSquare, double> dicOpen = new ConcurrentDictionary<ShapeSquare, double>();

            IsRange(pStartIndex.Item1-1, pStartIndex.Item2-1,1.4, pStartShapeSquare, dicOpen);
            IsRange(pStartIndex.Item1-1, pStartIndex.Item2,1, pStartShapeSquare, dicOpen);
            IsRange(pStartIndex.Item1-1, pStartIndex.Item2+1,1.4, pStartShapeSquare, dicOpen);
            IsRange(pStartIndex.Item1, pStartIndex.Item2+1,1, pStartShapeSquare, dicOpen);
            IsRange(pStartIndex.Item1+1, pStartIndex.Item2+1,1.4, pStartShapeSquare, dicOpen);
            IsRange(pStartIndex.Item1+1, pStartIndex.Item2,1, pStartShapeSquare, dicOpen);
            IsRange(pStartIndex.Item1+1, pStartIndex.Item2-1,1.4, pStartShapeSquare, dicOpen);
            IsRange(pStartIndex.Item1, pStartIndex.Item2-1,1, pStartShapeSquare, dicOpen);

            Tuple<int, int> pEndIndex = pEndShapeSquare.Tag as Tuple<int, int>;
            foreach (var item in dicOpen.Keys)
            {
                Tuple<int, int>  pItemIndex = item.Tag as Tuple<int, int>;
                dicOpen[item] += Math.Abs((pEndIndex.Item1 - pItemIndex.Item1)) + Math.Abs((pEndIndex.Item2 - pItemIndex.Item2));
                if (item == pEndShapeSquare)
                {
                    return true;
                }
            }

            List<KeyValuePair<ShapeSquare, double>> listSortOpen =dicOpen.OrderBy(a => a.Value).ToList();

            foreach (var item in listSortOpen)
            {
                Tuple<int, int> pIndex = item.Key.Tag as Tuple<int, int>;
                if (FindWayInfo(pIndex, item.Key, pEndShapeSquare))
                {
                    return true;
                }
            }
            return false;

        }
        private bool IsRange(int index1, int index2,double dStartLength,ShapeSquare pStartShapeSquare, ConcurrentDictionary<ShapeSquare,double> dicOpen)
        {
            if (index1 < 0 || index1 >= CrosswiseNodeCount)
            {
                return false;
            }

            if (index2 < 0 || index2 >= LengthwaysNodeCount)
            {
                return false;
            }

            ShapeSquare shapeSquare = PlotShapeSquare[index1, index2];

            if (shapeSquare is ShapeSquare_BlockingPoint)
            {
                return false;
            }

            if (dicClose.ContainsKey(shapeSquare))
            {
                return false;
            }
            else
            {
                dicClose.Add(shapeSquare, pStartShapeSquare);
                dicOpen.TryAdd(shapeSquare, dStartLength);

                shapeSquare.Fill = Brushes.BurlyWood;
                Thread.Sleep(10);
                System.Windows.Forms.Application.DoEvents();
            }

            return true;
        }
    }
}

在這里插入圖片描述

5 結語

由于這個演算法是一個啟發式演算法，所以需要處理一些特殊情況，如周圍點的f(n)相同時，順序問題等等，

這個時候我們再回過頭來看看國產SLG游戲中，三款游戲由時間順序的發展，地圖的變化，在演算法上它在解決什么問題呢？

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/289702.html

標籤：其他

上一篇：貪吃蛇小游戲原始碼分享

下一篇：三子棋小游戲(C語言版本)

從國產SLG手游來說A星尋路演算法

1. 前文

2. 演示代碼準備

3. 深度優先和廣度優先

3.1 深度優先

3.2 廣度優先

3.3 特點

3.4 講解與備忘

4. A星演算法

4.1 基本原理

4.2 A星演算法的詳細原理

4.3 節選代碼

5 結語