如果開發(fā)一個塔防游戲，很自然的會遇上這么兩個名字很像的問題：
- Path-finding: 如果知道起點和終點，如何在其間找到一條路徑
- Path-following: 已知從起點到終點的路徑，物體如何才能沿著它行進
本文將要討論的是第二個問題 path following，給定一條路徑，看物體如何沿著它從起點運行至終點。為了方便描述，接下來的內(nèi)容中，用單詞 Boid 來表示行進的物體或塔防中的敵人。
接下來會用一種簡單的方法來解決這一問題，最終完成的代碼庫可見 GitHub: boid-path-following，repo 的多個分支對應(yīng)了文中的不同步驟。
準(zhǔn)備工作
先來看看如何標(biāo)識出畫面中的位置，首先畫面被一系列的橫縱線分成了許多網(wǎng)格，對于地圖范圍內(nèi)的一個點，它會有自己的像素坐標(biāo) (x, y)，同時它所處的格子也有自己的坐標(biāo) (col, row) 或 (xIndex, yIndex)，表示所處的列和行。
為了區(qū)分，下文中提到像素坐標(biāo)即為用像素表示的坐標(biāo)，網(wǎng)格坐標(biāo)表示點在網(wǎng)格中的列和行。
在這種表示方法下，還需要一個工具函數(shù) index2Px(col, row)，用于計算格子中心的像素坐標(biāo)。
接下來給出路徑的坐標(biāo)，路徑是如下的一個二維數(shù)組：
const path = [[0, 1], [COLS - 4, 1], [COLS - 4, 4], [6, 4], [6, 7], /* 部分省略 */]
每一項都是路徑上一個點的網(wǎng)格坐標(biāo)，將這些點用直線連接起來后就得到了 boid 行進的路徑。我們的目標(biāo)就是要讓 boid 能夠從路徑第一個坐標(biāo)移動至最后一個坐標(biāo)。
Boid 如何沿直線前進
先考慮最簡單的問題，如何讓 Boid 沿著一條直線行進。
物體的移動需要位置和速度，為了表示其像素坐標(biāo)，boid 需要 x, y 屬性；其速度需要 speed 屬性，同時還需要一個 angle，以便計算出速度在兩個方向上的分量 vx, vy。
動畫效果的實現(xiàn)需要用 requestAnimationFrame 函數(shù)，每一秒為60幀，每一幀中都會執(zhí)行一次循環(huán)，在其中改變位置：
下一時刻的位置 = 當(dāng)前時刻的位置 + 速度
// 示意代碼
// Boid 類的 step() 方法
step() {
const speed = this.speed;
const angle = Math.PI / 2;
this.vx = Math.cos(angle) * speed;
this.vy = Math.sin(angle) * speed;
// 如果 vx, vy 不變化，則會沿一條直線前進
this.x += this.vx;
this.y += this.vy;
}
在每一個循環(huán)中，boid 的位置都會發(fā)生變化，在新的位置上將其畫出即可看到 boid 沿直線運動的效果。
這一部分可在示例代碼庫的 demo01/go-straight 分支上查看：
git checkout demo01/go-straight
npm run demo01
現(xiàn)在 boid 已經(jīng)動起來了，但是卻沒法停止，這就是我們接下來需要考慮的問題。
如何讓 boid 在目標(biāo)點處停止
要讓 boid 能夠知道自己到達(dá)了目標(biāo)點，則在每一次循環(huán)過程中，需要計算出此刻離目標(biāo)點的距離分量 dx，dy，據(jù)此算出距離 dist，將其與速度 speed 進行比較。如果 dist > speed，說明物體離目標(biāo)點還挺遠(yuǎn)，繼續(xù)將速度加到位置上即可。反之則表明物體將要到達(dá)終點，此時若直接加上速度，boid 可能會越過目標(biāo)點，因此需要一點不同的處理。
// 示意代碼
step() {
if (reachDest) {
// 已到達(dá)終點，可根據(jù)實際需要進行操作
}
const speed = this.speed;
// 與目標(biāo)點的距離
this.dx = target.x - this.x;
this.dy = target.y - this.y;
this.dist = Math.sqrt(this.dx * this.dx + this.dy * this.dy);
this.angle = Math.atan2(this.dy, this.dx);
// 速度分量
this.vx = Math.cos(this.angle) * speed;
this.vy = Math.sin(this.angle) * speed;
if (this.dist > speed) {
this.x += this.vx;
this.y += this.vy;
} else {
// 當(dāng)前時刻的位置加上速度后超過了當(dāng)前目標(biāo)點
// 物體下一時刻將處于當(dāng)前目標(biāo)點的位置
this.x = target.x;
this.y = target.y;
this.reachDest = true;
}
}
這一部分可在示例代碼庫的 demo01/stop 分支上查看：
git checkout demo01/stop
npm run demo01
此時，到達(dá)了終點的 boid 被清除而不再顯示。
如何讓 boid 能夠轉(zhuǎn)向
前面敘述中為了簡化，路徑中只有起點和終點，所以 boid 沒有機會轉(zhuǎn)向，那當(dāng)路徑變復(fù)雜了之后，boid 該如何運動？
前面已經(jīng)提到過，path 是一個記錄了路徑網(wǎng)格坐標(biāo)的數(shù)組，boid 會從中取一個坐標(biāo)作為自己的當(dāng)前目標(biāo)點，然后一直向前行進，到達(dá)了這個目標(biāo)點之后，它會從 path 數(shù)組中取出下一個坐標(biāo)，繼續(xù)移動至該位置。循環(huán)以上過程，直到 boid 到達(dá) path 中的最后一個坐標(biāo)。
上面的代碼中，我們的目標(biāo)點 target 固定為 path 的最后一個坐標(biāo)，而現(xiàn)在每一次轉(zhuǎn)向時 target 都會變化，所以加入這樣的兩個變量：
-
waypoint表示當(dāng)前目標(biāo)點的索引 -
angleFlag記錄是否需要轉(zhuǎn)向。
// Boid 的 step() 中的部分示意代碼
/* 每次轉(zhuǎn)向后目標(biāo)點需要重新計算 */
const waypoint = path[this.waypoint]; // 當(dāng)前目標(biāo)點的網(wǎng)格坐標(biāo)
const target = index2Px(...waypoint); // 當(dāng)前目標(biāo)點的像素坐標(biāo)
// ...
// 判斷是否需要轉(zhuǎn)向，如果需要轉(zhuǎn)向，則重新計算角度
if (this.angleFlag) {
this.angle = Math.atan2(this.dy, this.dx);
this.angleFlag = 0;
}
// 每次到達(dá)一個目標(biāo)點之后，都要檢查是否為終點
if (this.waypoint + 1 >= path.length) {
// 到達(dá)終點
this.reachDest = true;
} else {
this.waypoint++;
this.angleFlag = 1;
}
這一部分可在示例代碼庫的 demo01/steering 分支上查看：
git checkout demo01/steering
npm run demo01
結(jié)果可見下圖：
到此為止，這種 boid 沿路徑行進的方法已經(jīng)講解完畢了。建議讀者查看一下 repo 中的代碼，自己修改部分代碼，比如更改路徑，看結(jié)果會有何不同。
其它的方法
這一種方法中的確實現(xiàn)了沿路徑移動的效果，但是有點兒單調(diào)，boid 只能在路徑的中軸線上移動，而且它們之間也沒有交互的效果。The Nature of Code 這本書的第六章 Autonomous Agents 中介紹了另一種稍微復(fù)雜的方法來實現(xiàn) path following。
我之前參考他人的代碼實現(xiàn)了這種方法的一個演示版本，其代碼在此處。
(也許之后會補一篇博客來介紹 The Nature of Code 中的實現(xiàn)，但誰知道會不會寫呢??)
結(jié)語
最后，我最近在寫的這個塔防游戲中就使用了本文介紹的 path following 方法。雖然游戲還沒完成，但點進去看看再給個 star 又不費電??。
