昨天介紹了一個絕對最佳路徑搜尋法，《戴克斯特拉演算法》，但缺點是效率低，不適合在繁忙的遊戲程式裏運作。於是我們今天要把昨天的演算法稍稍地改一點，變成超高效率的貪婪演算法。

貪婪演算法

貪婪演算法和昨天講的戴克斯特拉的搜尋流程幾乎相同，只有其中一個步驟不一樣。不一樣的地方在於貪婪演算法選擇下一步的時候，也就是從眾多開發格中選擇要收藏的格子時，完全不考慮從起點走來的耗費時間，只在乎哪一格離終點最近。

在這個演算法中，我們不需要在演算法的節點裏儲存從起點來的累積耗時，但要增加一個估計還要多久能到達終點的函式。估計的方法是有講究的，不過大家可以先理解為格子與終點的距離。

這個函式叫啟發式估價函式(heuristic function)，用來評估一個格子到達終點預計要耗費多少時間。這個估價函式要怎麼寫，根據不同遊戲會有不同的做法，但一般是先計算格子和終點之間還剩多少距離，再用距離和平均速率來估計需要的時間。

我們把昨天演算法的步驟搬過來再改一改給同學們溫故知新一下（紅字為更改的部分）。

1. 將起點標示為已收藏，並將鄰接起點的格子標為開發格。
   • 從起點找到鄰格時，要在標為開發格的同時，順便估計還要多久能到目的地。
2. 從所有開發格之中，選一個估計未來耗時最短的一個，把這一格標為已收藏。
   • 如果這一格就是我們要找的目的地，那就結束演算法。
3. 從剛剛被標為已收藏的格子，向外找相鄰但還沒到過的格子。
4. 將找到的格子進行以下的計算。
   • 直接標示為開發格，並存入估計還要多久能走到目的地的時間。
5. 回到步驟2。

以上的步驟和昨天的戴克斯特拉相比，主要的差別在於步驟二選擇下一個已收藏格的思路不一樣，由「從起點最快到達的格子」改成「離終點最近的格子」。

至於程式碼，首先要增加新的屬性到演算法使用的節點類別。

// 昨天寫的搜尋節點
class MapNode {
    // 和昨天寫的一樣
    ...
    // 增加新屬性：估計走到目的地的成本（時間）
    costToTarget: number;
}

然後遊戲用的地圖也要提供一個新方法來估計兩點之間需要耗費的時間。

// 昨天寫的地圖介面
interface IGameMap {
    // 和昨天寫的一樣
    ...
    // 取得從一格到另一格估計要花的時間
    estimateCost(fromLoc: Point, toLoc: Point): number;
}

然後就可以寫貪婪演算法了。

// 繼承昨天寫的戴克斯特拉演算法
class Greedy extends Dijkstra {
    /** 改寫建立新節點的函式 */
    createMapNode(
        loc: Point,  // 節點位置
        fromNode: MapNode // 哪一點走過來的
    ): MapNode {
        /** 使用super關鍵字
         * 呼叫繼承自戴克斯特拉的createMapNode函式
         */
        let node = super.createMapNode(loc, fromNode);
        // 儲存這一點還要多久才能走到目的地的估計耗時
        node.costToTarget = this.gameMap.estimateCost(
                                loc,
                                this.targetLoc
                            );
    }
    /** 改寫演算法最想去的下一個格子 */
	getBestNodeToGo(nodes: MapNode[]): MapNode {
		// 將nodes以未來估計成本排序，從小到大
		ArrayUtil.sortNumericOn(nodes, 'costToTarget', true);
		// 取第一個，預估未來成本最低的格子
		return nodes[0];
	}
}

這樣就寫完了！改動的部分不多，但這個演算法就會在地圖上徑直朝目標奔去。

上圖中，綠色的數字就是每一格估計走到目標的時間，白字則是昨天戴克斯特拉用的"從起點過來的累積耗時"。貪婪演算法在每次選擇收藏格（暗色的格子），都會選綠色數字最小的格子，因此一路往右選，半步不停留地衝向目的地。

上圖格子中的數字單位是通過成本，草地的通過成本是２，是這個路徑搜尋模擬器的遊戲設定。

特性

貪婪演算法的特性就是快，當它每次在計算下一個收藏格的時候，都會選擇估計未來耗時最短的格子，所以完全不浪費時間，直衝目的地。

但是貪婪的結果就是只顧眼前的利益，完全不在意從起點過來的時候已經耗費了多少時間，所以在比較複雜的地形中，用這個方法找到的有可能會是繞點遠路的路徑，而不像戴克斯特拉找的一定是最佳路線。

要兼顧搜尋結果的品質與搜尋過程的效率，真的不是那麼簡單......才怪！明天我們就要介紹A* 演算法，以及A* 到今天還繼續受到遊戲設計師們喜愛的秘密。