前兩天分別介紹了兩種路徑搜尋演算法，《戴克斯特拉》與《貪婪演算法》。他們尋路的過程大同小異，但演算的結果卻大相徑庭。

復習

這兩種演算法都會將觸及的所有格子，分類成兩個區域。

• 已收藏：標示為已收藏的格子，表示怎麼到達這一格已經被確定了，未來不會再更改到達此格的路線。
• 開發格：標為開發中的格子，表示已知怎麼到達這一格，但還不確定目前這條是不是最佳路線。

戴克斯特拉演算法從起點開始往外找，它的思路是確保每次找到並收藏的格子，是目前能最快到達的開發格。這樣一路找下去，直到最後目的地被標示為收藏格的時候，演算法結束。

貪婪演算法的思路，則是在每次找下一個收藏格的時候選擇估計離終點最近的開發格。這樣找路的效率很高，但在複雜地圖上，找到的常常不是最佳路線。

A*演算法

我們先停下來想一下我們學會的這兩個演算法！

一個演算法是以起點到某格的累積耗時去決定下一格要去哪。

另一個演算法是以某格到終點的估計耗時去決定下一格要去哪。

那麼，某一格過去的累積耗時，加上未來的估計耗時，是不是就是從起點出發，經過某一格後到達終點的全程耗時，用這個加起來的全程耗時作為我們選擇下一格要去哪裏的依據，不就能綜合兩個演算法的優點嗎！

這個聽起來好棒棒的想法就是A*演算法。同時計較著確定的過去，又能顧及想像中的未來，讓這個演算法能兼顧品質與效率，成為遊戲設計師們的寵兒。

我們承續這兩天的程式來實作A*。首先要再次增加搜尋節點的屬性。

// 昨天寫的搜尋節點
class MapNode {
    // 和昨天寫的一樣
    ...
    // 增加新屬性：從起點經過這一格到終點的總成本
    costStartToTarget: number;
}

然後就可以寫A*演算法了。

// 繼承昨天寫的貪婪演算法
class AStar extends Greedy {
    /** 改寫建立新節點的函式 */
    createMapNode(
        loc: Point,  // 節點位置
        fromNode: MapNode // 哪一點走過來的
    ): MapNode {
        // 使用super關鍵字
        // 呼叫繼承自貪婪演算法的createMapNode函式
        let node = super.createMapNode(loc, fromNode);
        // 把過去的累積成本加上未來的估計成本
        node.costStartToTarget = node.costFromStart
                               + node.costToTarget;
    }
    /** 改寫演算法最想去的下一個格子 */
	getBestNodeToGo(nodes: MapNode[]): MapNode {
		// 將nodes以估計全程的成本排序，從小到大
		ArrayUtil.sortNumericOn(nodes, 'costStartToTarget', true);
		// 取第一個，全程成本最低的格子
		return nodes[0];
	}
}

改寫完畢！

怎麼樣，同學們！是不是改得如魚得水，改得如有神助，改得美到冒泡？

比較

三種演算法都介紹完畢，那麼就是一較高下的時候了。

上圖是三種演算法在同一張地圖上的表現。紅色細線是最後搜尋路徑的結果，暗色的格子是各演算法的收藏格（收藏格的數量約略等於演算法的耗時），亮色的格子是開發格，淺藍格是還沒計算的開發格，紅色格則是演算時觸及到但無法通過的格子。

我們可以看到，唯有貪婪演算法在群山環繞的盆地裏繞了一圈，其他兩種演算法都能正確找到最佳路線。雖然戴克斯特拉與A*找到相同的路線，但是戴克斯特拉幾乎搜遍了整張地圖才找到終點，而A*演算法觸及的格子數量卻幾乎與貪婪演算法一樣少。

雖然A*演算法看起來很棒，不過演算法中仍是用了不準確的估價函式，因此在更為複雜的地圖上，還是有機會沒能選到最佳路線。身為遊戲設計師的我們所能做的，就是根據不同遊戲的特性，找出更能反應現實的估價方式來加強A*的能力，讓遊戲更好玩。

在上圖中，右側的戴克斯特拉找到的是最佳路線，主要是因為從上方過河後，可以經由較好走的石板路，快速到達終點。A*演算法則因為無法預知河的對岸有石板路，因此在上方搜尋的過程中碰到森林就停了下來，然後選擇走下方沒有森林檔路的路線。

同學們可以前往這個《路徑搜尋模擬器》自行建立地圖，試試看這三種演算法在不同地形中的表現。
模擬器可以選擇不同的估價策略，讓同學們能體驗小小的策略改變，能怎樣影響演算法的結果。
《路徑搜尋模擬器》的CG開源專案