今天我們要來完成最後一個 AI 敵人，一樣要用演算法來練習。
這個敵人的移動策略是：如果附近有炸彈或爆炸範圍，就優先逃離危險區。如果沒有危險，就慢慢靠近玩家。
由於昨天我們請 AI 推薦演算法的時候，他有提到可以利用 Dijkstra 演算法來計算不同成本的格子，比如說敵人要避開炸彈或是炸彈範圍的時候可以使用，所以今天我們就是要用 Dijkstra 來完成這個敵人。
昨天我們是先從認識演算法開始，然後才請 AI 寫、再來看他寫了什麼。但今天我想要反過來，先讓 AI 寫，我們去理解之後試著回答看看跟昨天的作法相比，有哪邊改變了，試著猜測 Dijkstra 是怎樣的一個演算法，最後最後我們才去查詢 Dijkstra 演算法。
其實這一個系列最主要的主題還是練習思考，今天我想來談談思考的順序與目的的議題。
由於寫作這篇文章的時候，我自己的狀態是比較不好的，有一點沒有辦法集中精神去認識新的主題，所以我開始在思考有沒有更好的方式，能幫助我去完成這個任務。
後來我就想到可以調整一下工作的順序，我沒有必要因為昨天是這個流程，所以今天也採取同樣的流程，重點還是在於「為什麼要這樣做？」
試著回答一下，昨天為什麼會先從查看網路文章、試著自己去認識 BFS 開始？
因為我當時其實是想知道我有沒有能力在理解之後自己寫出來。但當我認識了這個演算法，我還是沒把握自己實作，所以我決定讓 AI 來幫忙。不過在前期自己去試著把 BFS 演算法的流程圖畫出來，我還是覺得很開心，我真的認識了一個新的演算法。
但是今天我沒有這樣的精神和體力，我希望可以用我已經認識的知識來認識新的知識，藉此降低我的認知負荷。因此我選擇先讓 AI 改，那麼我就可以從比較當中去發現哪邊改變了什麼，再去推敲，最後來對答案，對於現在的我而言會是更好的做法。
所以思考並沒有一個固定的路線，隨著不同的目的，我們可以改變自己思考的方向、流程，聽起來很像是廢話，不過有時候自己沒有經歷這個歷程，或者沒有那麼認真的去感受自己為什麼這麼做的話，似乎就不會去意識到原來我做出這個選擇的背後會有這個邏輯存在。
既然這個系列的主軸在於練習思考，所以我決定忠於自己在思考當中體會到的反思，把這段歷程記錄下來。
回到主題，AI 實作以前我一樣想先把前置作業做好，所以我正式的把 enemy3 換成了 pickNextEnemy3 ，另外根據昨天的經驗，我預想他可能會需要炸彈或爆炸範圍，所以我先帶入了這兩個參數，也預先建立好 pickNextEnemy3 函式。
function moveEnemy(map, boxes, enemy, player,bombs,explodeCells) {
// 計算並重新賦予座標
if (enemy === enemy1) {
enemy1 = pickNextEnemy1(map, boxes, enemy1);
}
if (enemy === enemy2) {
enemy2 = pickNextEnemy2(map, boxes, enemy2, player);
}
if (enemy === enemy3) {
enemy3 = pickNextEnemy3(map, boxes, enemy3, player,bombs,explodeCells);
}
}
function pickNextEnemy3(map, boxes, enemy, target, bombs = [], explodeCells = []) {
// enemy3 邏輯
}
另外要記得引入函式的地方也要加上參數
setInterval(() => {
moveEnemy(map, boxes, enemy1, player, bombs, explodeCells);
moveEnemy(map, boxes, enemy2, player, bombs, explodeCells);
moveEnemy(map, boxes, enemy3, player, bombs, explodeCells);
// 渲染
render();
}, 1000);
接著就讓 AI 來工作了！要記得指定要使用 Dijkstra 演算法，以下是他實作的成果：
function pickNextEnemy3(map, boxes, enemy, target, bombs = [], explodeCells = []) {
const startKey = `${enemy.x},${enemy.y}`;
const targetKey = `${target.x},${target.y}`;
const distances = new Map([[startKey, 0]]);
const firstSteps = new Map([[startKey, null]]);
const visited = new Set();
const queue = [{ x: enemy.x, y: enemy.y, distance: 0 }];
// 炸彈所在格及上下左右是即將爆炸的危險區域。
const dangerCells = new Set(
explodeCells.map(cell => `${cell.x},${cell.y}`)
);
for (const bomb of bombs) {
const blastCells = [
{ x: bomb.x, y: bomb.y },
{ x: bomb.x - 1, y: bomb.y },
{ x: bomb.x + 1, y: bomb.y },
{ x: bomb.x, y: bomb.y - 1 },
{ x: bomb.x, y: bomb.y + 1 },
];
for (const cell of blastCells) {
const isInsideMap =
cell.y >= 0 && cell.y < map.length &&
cell.x >= 0 && cell.x < map[cell.y].length;
if (isInsideMap && map[cell.y][cell.x] !== '#') {
dangerCells.add(`${cell.x},${cell.y}`);
}
}
}
while (queue.length > 0) {
// 取出目前距離最短的節點，這是 Dijkstra 的核心步驟。
let nearestIndex = 0;
for (let i = 1; i < queue.length; i++) {
if (queue[i].distance < queue[nearestIndex].distance) {
nearestIndex = i;
}
}
const current = queue.splice(nearestIndex, 1)[0];
const currentKey = `${current.x},${current.y}`;
if (visited.has(currentKey)) {
continue;
}
visited.add(currentKey);
if (currentKey === targetKey) {
const firstStep = firstSteps.get(currentKey);
return firstStep
? { ...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 cellKey = `${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(cellKey)) {
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;
}
// 一般格成本為 1；危險格提高成本，讓 enemy 優先繞路。
const moveCost = dangerCells.has(cellKey) ? 50 : 1;
const newDistance = current.distance + moveCost;
if (newDistance < (distances.get(cellKey) ?? Infinity)) {
distances.set(cellKey, newDistance);
firstSteps.set(
cellKey,
firstSteps.get(currentKey) || { x: cell.x, y: cell.y }
);
queue.push({ ...cell, distance: newDistance });
}
}
}
// 找不到通往玩家的路徑時，enemy 留在原地。
return { ...enemy };
}
好，我知道你們在想什麼，一次這麼多東西丟過來，腦袋會爆炸的！沒關係，從我們最關心的開始，先執行來玩看看XD
一樣我先把另外兩個敵人註解掉，比較好觀察：
function moveEnemy(map, boxes, enemy, player,bombs,explodeCells) {
// // 計算並重新賦予座標
// if (enemy === enemy1) {
// enemy1 = pickNextEnemy1(map, boxes, enemy1);
// }
// if (enemy === enemy2) {
// enemy2 = pickNextEnemy2(map, boxes, enemy2, player);
// }
if (enemy === enemy3) {
enemy3 = pickNextEnemy3(map, boxes, enemy3, player,bombs,explodeCells);
}
}
現在 enemy3 就會避開炸彈了，這畫面讓我忍不住想起一些隔著桌子追逐的名場面XD
多玩個幾次可能會發現一些技術上的 bug ，不過不是今天該討論的主題，我們先繼續往下。
首先來看看兩邊的變數差在哪裡，先從變數來看：
const startKey = `${enemy.x},${enemy.y}`;
const targetKey = `${target.x},${target.y}`;
const distances = new Map([[startKey, 0]]);
const firstSteps = new Map([[startKey, null]]);
const visited = new Set();
const queue = [{ x: enemy.x, y: enemy.y, distance: 0 }];
我們可以發現到 visited 和 queue 是我們已經知道的，昨天 visited 用來儲存已經走過的格子，就不再重複加入佇列， queue 則是用來儲存排隊要處理的項目。但是今天 queqe 的物件中第三項從 firstStep 改成了 distance 。
另外多了四個變數：(用 const 定義其實應該叫做常數，不過詞彙的定義我們這邊就先不深究了)
startKey 用來儲存起始值，他會把原本寫成 { x: 1, y: 2 } 的格式，轉換成純文字 "1,2" 。targetKey 用來儲存目標值，一樣把座標轉換成純文字。distances 是一個 Map 物件，可以看到他把剛剛轉換好的 startKey 和 0 放進去做為鍵值對。firstSteps 也是一個 Map 物件，只是這次值換成了 null 。在這裡我認為最值得注意的是 distances 和 firstSteps 這兩個，在 BFS 當中也會記錄第一步，但沒有去紀錄距離，這是第一個發現的變化。
往下一段是另外一個變數：
// 炸彈所在格及上下左右是即將爆炸的危險區域。
const dangerCells = new Set(
explodeCells.map(cell => `${cell.x},${cell.y}`)
);
我們可以拆解一下這個變數做了什麼事情：
map 方法遍歷 explodeCells 陣列，也將每個爆炸的座標都轉化為純文字像這樣 "1,2" 。dangerCells 。接著是一段 for 迴圈，從 const bomb of bombs 這裡我們可以看出這段主要是逐個處理炸彈的邏輯：
for (const bomb of bombs) {
const blastCells = [
{ x: bomb.x, y: bomb.y },
{ x: bomb.x - 1, y: bomb.y },
{ x: bomb.x + 1, y: bomb.y },
{ x: bomb.x, y: bomb.y - 1 },
{ x: bomb.x, y: bomb.y + 1 },
];
for (const cell of blastCells) {
const isInsideMap =
cell.y >= 0 && cell.y < map.length &&
cell.x >= 0 && cell.x < map[cell.y].length;
if (isInsideMap && map[cell.y][cell.x] !== '#') {
dangerCells.add(`${cell.x},${cell.y}`);
}
}
}
blastCells 是我們已經很熟悉的，用來計算出這顆炸彈周圍的格子。dangerCells 。那我們現在已經看到剛剛制定的變數，出現了第二次，那就是 dangerCells ，第一次制定的時候將現有的爆炸範圍存進來，接著他處理的是還沒爆炸的炸彈，也要計算周圍有哪些格子並且存入。
所以我們現在有第二個線索：炸彈和爆炸範圍會被記錄成危險區，但我們還不知道危險區實際的用途。
到這邊冒出的想法先記錄一下：感覺判斷某一格的附近有哪些格子、是不是在地圖內、判斷是不是牆壁，這些邏輯很常出現，之後可以考慮抽成共用的函式。不過這不是我們現在的目標，所以一樣要學習先踩煞車，繼續往下看。
最後一樣是一個 while 迴圈，當 queue.length > 0 的時候就會繼續執行直到佇列中沒有東西為止。這邊跟 BFS 是一樣的。
while (queue.length > 0) {
// 內容省略一下節省篇幅
}
在迴圈內首先用 let 制定了一個 nearestIndex 變數，所以我們可以猜想等一下會重新賦值。果不其然下一段也是一個迴圈，咦？這邊也是逐一處理佇列的迴圈：
let nearestIndex = 0;
for (let i = 1; i < queue.length; i++) {
if (queue[i].distance < queue[nearestIndex].distance) {
nearestIndex = i;
}
}
const current = queue.splice(nearestIndex, 1)[0];
const currentKey = `${current.x},${current.y}`;
從上面這段，我們可以看出他的判斷式是，如果當前這個項目的 distance 小於目前記錄中最小距離的那個項目，就重新把 nearestIndex 賦值為當前的 index。簡而言之，這一段的作用是要判斷佇列中哪一個項目的 distance 最小，再搭配上後面兩行 current 的取得，我們就知道原來他是要把最短距離的優先拿出來處理。
到這邊我們就跟第一個發現連在一起了！為什麼要去記錄距離呢？在 BFS 裡面是將全部的項目都按照順序跑過一遍，但是在 Dijkstra 裡面是距離短的優先處理，要確保找到的是最短的路線。
中間有一大段其實昨天都有出現過的，我就先省略，我們直接來看到迴圈最下面：
// 一般格成本為 1；危險格提高成本，讓 enemy 優先繞路。
const moveCost = dangerCells.has(cellKey) ? 50 : 1;
const newDistance = current.distance + moveCost;
if (newDistance < (distances.get(cellKey) ?? Infinity)) {
distances.set(cellKey, newDistance);
firstSteps.set(
cellKey,
firstSteps.get(currentKey) || { x: cell.x, y: cell.y }
);
queue.push({ ...cell, distance: newDistance });
}
先前情提要一下，這一段是用在計算 current 這個格子週邊的格子的 distance，計算完成之後要把它們存進去佇列裡的邏輯，如果還是霧傻傻的話，可以看這張圖，我也一起把下面的步驟畫出來了：
我們注意到他用 moveCost 來儲存成本，而這個成本是由危險區 dangerCells 去計算出來的，假如這個最短距離的格子有被記錄在危險區域內，那麼就會將他的成本設為 50，沒有的話設為 1 。
接著計算出新的距離 newDistance 是用原本的距離加上成本來計算，這就會讓位於危險區的格子 distance 大幅增加。
最後把這個存回佇列裡，另外 distances 和 firstSteps 的功能也在這一段終於弄清楚：
distances 紀錄的是從起點到每個格子的成本是多少，如果過程中發現抵達同一個格子有更低成本的路線，就會取代掉原本的路線，用來判斷哪條路的成本比較低。firstSteps 紀錄的是到每個格子的最佳路線的第一步，用來判斷我們最後的下一步是誰。到這邊我們大致上弄懂 Dijkstra 的運作邏輯了，不過還是請 AI 幫我們生成動畫，確認一下我們的思考有沒有問題。
來整理一下我們的四個發現：
在這裡面我覺得最特別的應該就是成本的計算，BFS 也是一種找最短路徑的做法，但是它沒有去計算不同格子的成本，而 Dijkstra 則是將成本加上最短距離之後才拿來做為最終決策的依據。
查詢結果可以看到執行步驟其實就是我們剛剛做的流程，這個演算法的目的就是要在加權圖中去計算最短距離。加權圖的意思就是每一條邊都有一個數值，代表著這兩個節點之間的成本、距離等等。
基於篇幅的關係，我就不幫大家詳細說明什麼是 Dijkstra 演算法，因為我在本篇文章的目標是練習思考，所以最後這個步驟（我當然自己有去完成!!!絕對沒有偷懶）我還是希望交由各位讀者自己去練習看看！
以下幫大家整理我查到的一些參考資料，有興趣的讀者可以再自行閱讀：
那麼明天我希望我們千萬千萬要從爆爆王遊戲畢業啊，期待爆爆王遊戲最終玩起來到底會長什麼樣子嗎？我們明天見！！
如果你想要自己玩看看這個動態範例，可以下載程式碼，開啟裡面的 html 檔案，今天的完整程式碼，可以參考這裡：第 17 天程式碼
iThome鐵人賽
看影片追技術