這章要來完成另外一個 AI 敵人，先複習一下這個敵人的移動策略是：距離使用者最近的可移動方向前進一格。
前面我的寫法幾乎都是用自己的邏輯試著拼湊出解答，感覺我自己很像原始人，因為沒有人告訴我方法，所以我自己當開創者，用各種方法來找到解決的方式，總之就是土法煉鋼啦。
不過都已經21世紀了，其實前人流傳下來一定有很多值得我們學習的地方，今天我想試著先去了解有沒有已經有人提出的做法可以來處理我們所遇到的問題，站在巨人的肩膀上或許能使我們學習到更多。
簡單的來說，今天要討論的就是「演算法」，白話的來說：Input 是我傳入的內容，Output 則是解答，中間的處理機制就是演算法，所以演算法也就是解決問題的方法。那麼我們先前所寫的很多東西也都算是演算法吧，比如昨天寫的隨機選擇一格？是的，沒錯！不過我今天期待的是用前人發明的方法，而不是自己發明新的方法。
你或許會問說：這跟直接問 AI 解決方法有什麼不一樣？
我的回答是這樣的，或許 AI 也是使用已知的演算法來回答我的問題，最終結果也許是一樣的，但差別在於我能不能多認識一個演算法？能不能在下一次需要用的時候想起我曾經學過這個演算法呢？所以即使是要問 AI，我的提問也會是這樣的：「我想要讓 enemy2 可以向距離使用者最近的可移動方向前進一格，請推薦我一個演算法」，接著了解那個演算法之後再往下寫。
這個做法有沒有覺得很熟悉呢？這就跟我們先前去搜尋如何隨機挑選一格的方法有點像，當時是透過搜尋找到洗牌法來解決。那我們今天就來查查看有沒有已經有演算法能參考、用來處理這兩個 AI 機器人的邏輯。
那麼我們就先來對 AI 提問一下：有沒有辦法可以找到 enemy2 和 player 之間的最短距離？請你推薦幾個適合的演算法給我。
獲得的回覆有下面這幾個選擇，我想直接截圖給大家，避免我摘要得不清楚：
先簡單從描述看起來，AI 最推薦的是 BFS，但如果將來要加入到避開炸彈和爆炸範圍就可以改用 Dijkstra，不過我並不想要這麼快的讓他幫我去寫這個邏輯，我想再深入了解一下這個演算法，看看是不是真的符合我的需要，所以我去查了一下什麼是 BFS（又稱為廣度優先搜尋），然後畫了這樣的範例：
我們可以看到敵人 E 要前進到 P 的位置，那麼我們優先逐一查詢每一個鄰近點（1、2、3）是不是 P ，如果都不是，就往下一層從 1-1 開始查詢第二層是不是玩家，如果第二層也都還不是呢，就來查詢第三層，從 1-1-1 開始。
廣度優先搜尋的特色如果按照探索地下城的概念來講，應該就是把每一層都詳細的探索過一遍之後才前往下一層，它的相反就是 DFS（深度優先搜尋），也就是先就一條主線不斷地深入探索，例如從 1 開始，然後 1-1、1-1-1、1-1-1-1 把一整條路線探索完，再回來從 2 繼續探索 2-1、2-1-1 。
所以從這個圖片來看，我們最短的路徑是走 1 或走 2，最少要 5 步可以到達 P 的位置，但因為 1 號路線是優先搜尋，所以最終我們會在 1-1-1-5 的時候找到 P，而不是 2-2-1-1-1，所以很自然地在這個時間點我們要讓 E 往 1 號位置移動一格。
但是因為下一秒 E 跟 P 都有可能移動，所以整個路線要再重跑一次，目前因為地圖很小，所以這個資源消耗是可以接受的，不過如果未來每次決定一步都會涉及大量的計算，可能就要考慮有沒有更有效率的做法。
理解到這邊，我想就可以讓 AI 開始來實作，走不通的話再來嘗試其他的做法。
首先我先新增一個函式，指定 AI 要在這個區域內實作：
function pickNextEnemy2(enemy,allowCell) {
// 這裡是給 AI agent 的實作區域
}
先說明一下為什麼這一段要給 AI 來實作，因為我發現理解概念是一回事，要如何照著 BFS 演算法原始的精神來撰寫這段邏輯又是另一回事，畢竟我們今天的題目是站在巨人的肩膀上，我不應該理解 BFS 的原理之後又回去土法煉鋼。
但當我深入挖掘 BFS 演算法的時候，我注意到 BFS 通常會搭配 queue（佇列）來記錄待處理的項目，和 visited (這個名稱可能會換) 來記錄已經查詢過的項目，那麼我們就又必須去了解什麼是 queue 資料結構。
然而即使我看到網路上的範例，還是沒有頭緒該如何應用這兩個新的知識點來修改我的這一段邏輯，這時候依據前面所提到的原則，最好是先讓 AI 幫我完成，我們再透過這段程式碼來更認識 BFS 和 queue 。
那麼這邊就是 AI 完成的範例啦：
function pickNextEnemy2(map, boxes, enemy, target) {
// queue 內除了目前座標，也記錄從 enemy 出發時走的第一步
const queue = [{ x: enemy.x, y: enemy.y, firstStep: null }];
const visited = new Set([`${enemy.x},${enemy.y}`]);
while (queue.length > 0) {
const current = queue.shift();
// BFS 第一次抵達目標時，走過的路徑一定是最短路徑
if (current.x === target.x && current.y === target.y) {
return current.firstStep
? { ...current.firstStep, live: enemy.live }
: { ...enemy };
}
const surroundingCells = [
{ x: current.x - 1, y: current.y },
{ x: current.x + 1, y: current.y },
{ x: current.x, y: current.y - 1 },
{ x: current.x, y: current.y + 1 },
];
for (const cell of surroundingCells) {
const key = `${cell.x},${cell.y}`;
const isOutsideMap =
cell.y < 0 || cell.y >= map.length ||
cell.x < 0 || cell.x >= map[cell.y].length;
if (isOutsideMap || visited.has(key)) {
continue;
}
const isWall = map[cell.y][cell.x] === '#';
const isBox = boxes.some(box => box.x === cell.x && box.y === cell.y);
if (isWall || isBox) {
continue;
}
visited.add(key);
queue.push({
...cell,
firstStep: current.firstStep || cell,
});
}
}
// 找不到通往玩家的路徑時，enemy2 留在原地
return { ...enemy };
}
看這段程式碼覺得很難理解的時候，我們可以回顧一下先前使用過的方法，有沒有適合用在這裡幫助我們理解的方法，所以我決定要來畫個時序圖，其中用途用綠色的便條紙來貼，使用到的方法用粉紅色便條紙來貼，因為我截的圖有一點小，可以先不要認真看XD：
不過老實說畫完我還是覺得沒辦法完整理解整個過程，我甚至畫了第二個精簡的版本，也是可以先不要認真看XD：
其實總結來講呢，就是我們會利用 queue 這個佇列，來儲存所有需要處理的格子，一開始要處理的格子當然就是 E 本來所在的位置，接下來就會逐一去判斷 E 周遭的四個格子，是否超出範圍、是否是牆壁、是否是箱子，接著把可以走的格子儲存進去佇列裡，並且記錄這個第一層的座標到 firstStep。
接著就會依序處理佇列中的每一項，都按照一樣的步驟，直到遇到 target ，這時候我們就對照 firstStep ，把這個座標回傳，當作是 enemy2 的下一步。
我意識到我內心期待的是我可以看見 queue 佇列每一次的變化，以及最終到底是如何一步步找到下一個前進的位置的，所以我請 AI agent 做了一個動態的流程，讓大家可以看清楚變化：
理解完成之後記得 moveEnemy 要修改一下傳入的變數
function moveEnemy(map, boxes, enemy, player) {
// 計算並重新賦予座標
if (enemy === enemy1) {
enemy1 = pickNextEnemy1(map, boxes, enemy1);
}
if (enemy === enemy2) {
enemy2 = pickNextEnemy2(map, boxes, enemy2, player);
}
if (enemy === enemy3) {
enemy3 = pickNextEnemy1(map, boxes, enemy3);
}
}
那麼最後就是試玩看看啦，為了方便辨識，我先把另外兩個敵人先暫停。
這樣我們就獲得了一個緊緊跟隨著我們不放的敵人啦，唉，說真的是蠻可怕的哈哈哈。那麼我們就期待明天繼續完成下一個敵人！會學到怎樣的演算法呢？希望大家還沒有放棄，明天見！
如果你想要自己玩看看這個動態範例，可以下載程式碼，開啟裡面的 html 檔案，今天的完整程式碼，可以參考這裡：第 17 天程式碼
iThome鐵人賽
看影片追技術