一講到遊戲中的路徑搜尋，通常 A＊ 這個字眼馬上就會浮起來，因為A*演算法就是目前開發遊戲最熱門的路徑搜尋方式。不過同學們先別鼓噪，我們一步一步來，先從路徑搜尋的鼻祖講起，之後會講到A*的。
戴克斯特拉(Edsger Dijkstra)是荷蘭程式設計的先驅。1959年他在期刊上發表的一篇論文，開啟了電腦在路徑搜尋演算的大門。
論文：A Note on Two Problems in Connexion with Graphs [PDF]
據戴克斯特拉的說法，這篇論文的靈感是他在陪老婆逛街的時候想到的。
先預告一下，A*演算法其實也是從戴克斯特拉演算法演變而來，而且只在一個小地方做了點改變，所以同學們理解了戴克斯特拉演算法之後，過兩天再去看A*就易如反掌了。
我們先來講一下戴克斯特拉演算法的適用地圖。地圖必須是由許多節點以及節點之間的通道組成，通道會標明通過時需要消耗的成本。只要地圖符合這個構造，就可以利用戴克斯特拉演算法算出任意兩個節點之間，成本最低的路線。
通常我們講的成本是指在節點間旅行所花費的時間，因此在以下的說明中，我們都改稱這個成本為時間。雖然Google地圖、3D碎形地圖等都能適用，但我們今天只專注在格子狀的2D地圖，這樣講解起來比較方便。另外，演算法除了要有地圖節點與通道的資料之外，還要知道起點與終點的位置，不然就不知道在找什麼了，是吧。
戴克斯特拉從起點開始，藉由已知的領地慢慢擴展到未知的領地，並將它觸及過的格子分成兩個區域，
這個演算法可以分為以下幾個步驟：
- 將起點標示為已收藏，並將鄰接起點的格子標為開發格。
- 從起點找到鄰格，並標示為開發格時，要順帶將走過去的累積時間記錄到格子裏。
- 從所有開發格之中，選擇累積耗時最短的一個，把這一格標為已收藏。
- 這一格是目前能從起點最快到達的開發格，所以不可能從其他開發格找到更快的路線到達這一格。
- 如果這一格就是我們要找的目的地，那就結束演算法。
- 從剛剛被標為已收藏的格子，向外找相鄰但還沒成為已收藏的格子，包括開發格以及之前沒到過的格子。
- 將3.找到的格子進行以下的計算。
- 計算從起點經由已收藏格到達這一格會耗費的時間。
- 比較一下上一次找到這一格時計算過的耗費時間，如果這次的路線比較好，就覆蓋掉之前的記錄。
- 如果這一格是新找到的格子，那就直接標示為開發格，並存入耗費的時間。
- 回到步驟2。
在上面的步驟2中，被標記為計算完成的已收藏格，表示演算法已經知道從起點到達目的地的最短路徑，所以只要演算法持續這幾個步驟，直到標記完成的格子等於終點，那麼就大功告成了。
為了示範這個演算法，先假設我們已經有了格子地圖的類別，而這個地圖能夠提供演算法需要的資料。
// 宣告地圖需要有的介面
interface IGameMap {
/** 檢查兩格是否有路相連，以面兩種情況要回傳false
* 1. toLoc超過地圖邊界
* 2. toLoc是不能走的格子（如岩漿、大石、樹木等）
*/
isPossiblePath(fromLoc: Point, toLoc: Point): boolean;
// 取得從一格到相鄰格所需要的成本
getCost(fromLoc: Point, toLoc: Point): number;
}
接著要寫一個演算法專用的地圖節點類別，在演算的途中，都要用這個類別來儲存地圖上的格子資料。
// 宣告給路徑搜尋用的節點
class MapNode {
// 這個節點的ID，由格子座標組成
id: string;
// 建構子
constructor(
public location: Point, // 這個節點的位置
public fromNode: MapNode, // 走到這個節點的上一個節點
public costFromStart: number // 到這個節點累積的耗費成本
) {
// 以這個節點的位置產生ID
this.id = `${location.x},${location.y}`;
}
}
有了以上的準備工作，我們就可以來實作戴克斯特拉演算法了。
// 宣告Dijkstra類別
class Dijkstra {
/** 已收藏格的Map,到時可以用id去存取MapNode */
closeNodes: { [key: string]: MapNode } = {};
/** 開發格的Map,到時可以用id去存取MapNode */
openNodes: { [key: string]: MapNode } = {};
/** 起點 */
startLoc: Point;
/** 終點 */
targetLoc: Point;
/** 結果路徑
* 當我們找到最後到達目的地的路徑後，
* 就把路徑存在這個變數裏。
*/
resultPath: Point[];
/** 是否已搜尋完畢的屬性 */
complete = false;
/** 建構子，需要地圖、起點、終點三個參數 */
constructor(
public gameMap: IGameMap,
startLoc: Point,
targetLoc: Point
) {
this.startLoc = startLoc;
this.targetLoc = targetLoc;
// 把起點變成一個初始節點，放到*已收藏*裏
let startNode = new MapNode(startLoc, null, 0);
this.closeNodes[startNode.id] = startNode;
}
/** 建立新節點的函式 */
createMapNode(
loc: Point, // 節點位置
fromNode: MapNode // 從哪一點走過來的
): MapNode {
// 計算累積成本 = 上一點的成本 + 這個通道的成本
let cost = fromNode.costFromStart
+ this.gameMap.getCost(fromNode.location, loc);
return new MapNode(
loc, // 記錄節點位置
fromNode, // 記錄這節點是從fromNode過來的
cost // 記錄從起點過來的成本
);
}
/** 實作演算法的一個循環的所有步驟 */
searchCycle() {
// 把開發格子們變成一個陣列
let openNodes: MapNode[] = Object.values(this.openNodes);
if (!openNodes.length) {
/**
* 如果發現沒有開發格，就代表沒路走了
* 也就是找不到路，不存在起點到終點的路徑
*/
this.complete = true;
return;
}
// 找到最佳的下一格
let bestNode = this.getBestNodeToGo(openNodes);
/** 標記這一格為已收藏
* 1. 從開發格列表中移除
* 2. 放到已收藏列表
*/
delete this.openNodes[bestNode.id];
this.closeNodes[bestNode.id] = bestNode;
// 檢查這一格是不是目標位置
if (bestNode.location.equals(this.targetLoc)) {
// 我們到了!
this.complete = true;
// 把最後路徑取出來
this.resultPath = this.getResultPath(bestNode);
return;
}
/**
* 找出從這一格可以到達哪些非已收藏的格子
*/
// 先列出四方向
let directions = [
new Point(1, 0), // 往東
new Point(-1, 0), // 往西
new Point(0, 1), // 往南
new Point(0, -1), // 往北
];
// loop四方向
for (let dir of directions) {
// 計算從bestNode往dir移一格的位置
let loc = bestNode.location.add(dir);
// 如果這一格無法到達，就略過這一次的loop
if (!this.gameMap.isPossiblePath(bestNode.location, loc)) {
// continue是關鍵字，能直接跳到迴圈的下一輪
continue;
}
// 建立新節點
let newNode = this.createMapNode(loc, bestNode);
// 如果新節點其實已經是已收藏的格子，就直接跳到迴圈的下一輪
if (this.closeNodes[newNode.id]) {
continue;
}
// 看一下這一格是不是先前從別的地方來過了
const prevOpenNode = this.openNodes[newNode.id];
if (prevOpenNode) {
// 如果來過了，比較一下誰的累積代價比較低(好)
if (newNode.costFromStart < prevOpenNode.costFromStart) {
// 如果走現在這條比較好，就取代之前找到的節點
this.openNodes[newNode.id] = newNode;
}
} else {
// 如果之前沒來過，直接放到開發格列表
this.openNodes[newNode.id] = newNode;
}
}
}
/** 從一串節點找出演算法認為最想去的下一個格子 */
getBestNodeToGo(nodes: MapNode[]): MapNode {
// 將nodes以累積成本排序，從小到大
ArrayUtil.sortNumericOn(nodes, 'costFromStart', true);
// 取第一個，累積成本最低的格子
return nodes[0];
}
/** 從最後一個節點反推回去走來經過的路徑 */
getResultPath(finalNode: MapNode): Point[] {
// 建立路徑，把終點先放進去
let path: Point[] = [finalNode.location];
// 把node先指定為終點
let node = finalNode;
/** 用while迴圈找上一個路徑上的節點
* 如果節點有fromNode，代表還要回朔走來的點
* 如果節點沒有fromNode，代表這就是起點，工作結束
*/
while(node.fromNode) {
// 把node變成走過來的節點
node = node.fromNode;
// 把這個節點的位置放到路徑的最前面
// Array.unshift可以把元素安插到陣列的最前面
path.unshift(node.location);
}
return path;
}
/** 真正開放給類別使用者用的搜尋函式 */
searchPath(): Point[] {
// 如果演算法還沒結束
while (!this.complete) {
// 繼續執行一整個循環步驟
this.searchCycle();
}
// 回傳找到的路徑（有可能是null）
return this.resultPath;
}
}
上面的程式有使用到ArrayUtil.sortNumericOn()這個CG函式庫裏的排序工具。
查看原始碼 ArrayUtil.ts
下面示範如何使用剛剛寫好的演算法類別找到兩點之間的最短路徑。
// 假設早前已經有一個建立好的地圖
let gameMap: IGameMap = ...
// 建立一個演算法
let algorithm = new Dijkstra(
gameMap, // 使用這個地圖
new Point(10,10), // 起點
new Point(30,10) // 終點
);
let path = algorithm.searchPath();
if (path) {
console.log("找到路徑了!", path);
} else {
console.error("找不到能從起點到達終點的路!");
}
今天沒有示範專案，我們會在路徑搜尋的三篇文章結束時，再一併寫一個酷酷的示範專案。
同學們請就上面的示範程式碼，研究這個演算法的邏輯，這樣明天我們介紹貪婪路徑搜尋法就如魚得水了。
戴克斯特拉的優點為找到的路線保證是最好的，原因在上面說明的步驟２有解釋，所以如果遊戲的地圖是靜態的，也可以事先把路徑都先算好，放在一個檔案裏備查，以節省遊戲時的CPU資源。
戴克斯特拉的缺點就是除了剛剛講的步驟２之外，沒有其他地方的計算有考慮過目的地在哪裏，搜尋路徑的過程就好像用一壺水從起點上方澆下去，讓水向外淹，慢慢等它淹到目的地。就像上圖所顯示的，演算法像是以出發點為圓心，一層一層向外擴展搜尋到的格子，直到邊緣碰到目的地才停止。這效率不用說，肯定不足以在遊戲中即時地拿來運用。
那你說怎麼辦呢？明天就知道！
iThome鐵人賽
看影片追技術