摘要：為了方便描述，接下來的內容中，用單詞來表示行進的物體或塔防中的敵人。如何沿直線前進先考慮最簡單的問題，如何讓沿著一條直線行進。循環以上過程，直到到達中的最后一個坐標。本文地址塔防游戲中的敵人如何沿路徑前進實現

如果開發一個塔防游戲，很自然的會遇上這么兩個名字很像的問題：

Path-finding: 如果知道起點和終點，如何在其間找到一條路徑

Path-following: 已知從起點到終點的路徑，物體如何才能沿著它行進

本文將要討論的是第二個問題 path following，給定一條路徑，看物體如何沿著它從起點運行至終點。為了方便描述，接下來的內容中，用單詞 Boid 來表示行進的物體或塔防中的敵人。

接下來會用一種簡單的方法來解決這一問題，最終完成的代碼庫可見 GitHub: boid-path-following，repo 的多個分支對應了文中的不同步驟。

先來看看如何標識出畫面中的位置，首先畫面被一系列的橫縱線分成了許多網格，對于地圖范圍內的一個點，它會有自己的像素坐標 (x, y)，同時它所處的格子也有自己的坐標 (col, row) 或 (xIndex, yIndex)，表示所處的列和行。

為了區分，下文中提到像素坐標即為用像素表示的坐標，網格坐標表示點在網格中的列和行。

在這種表示方法下，還需要一個工具函數 index2Px(col, row)，用于計算格子中心的像素坐標。

接下來給出路徑的坐標，路徑是如下的一個二維數組：

    const path = [[0, 1], [COLS - 4, 1], [COLS - 4, 4], [6, 4], [6, 7], /* 部分省略 */]

每一項都是路徑上一個點的網格坐標，將這些點用直線連接起來后就得到了 boid 行進的路徑。我們的目標就是要讓 boid 能夠從路徑第一個坐標移動至最后一個坐標。

先考慮最簡單的問題，如何讓 Boid 沿著一條直線行進。

物體的移動需要位置和速度，為了表示其像素坐標，boid 需要 x, y 屬性；其速度需要 speed 屬性，同時還需要一個 angle，以便計算出速度在兩個方向上的分量 vx, vy。

動畫效果的實現需要用 requestAnimationFrame 函數，每一秒為60幀，每一幀中都會執行一次循環，在其中改變位置：

下一時刻的位置 = 當前時刻的位置 + 速度

    // 示意代碼
    // 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; 
    }

在每一個循環中，boid 的位置都會發生變化，在新的位置上將其畫出即可看到 boid 沿直線運動的效果。

這一部分可在示例代碼庫的 demo01/go-straight 分支上查看：

git checkout demo01/go-straight
npm run demo01

現在 boid 已經動起來了，但是卻沒法停止，這就是我們接下來需要考慮的問題。

要讓 boid 能夠知道自己到達了目標點，則在每一次循環過程中，需要計算出此刻離目標點的距離分量 dx，dy，據此算出距離 dist，將其與速度 speed 進行比較。如果 dist > speed，說明物體離目標點還挺遠，繼續將速度加到位置上即可。反之則表明物體將要到達終點，此時若直接加上速度，boid 可能會越過目標點，因此需要一點不同的處理。

    // 示意代碼
    step() {
        if (reachDest) {
            // 已到達終點，可根據實際需要進行操作            
        }

        const speed = this.speed;

        // 與目標點的距離
        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 {
            // 當前時刻的位置加上速度后超過了當前目標點
            // 物體下一時刻將處于當前目標點的位置
            this.x = target.x;
            this.y = target.y;
            this.reachDest = true;
        }
    }

這一部分可在示例代碼庫的 demo01/stop 分支上查看：

git checkout demo01/stop
npm run demo01

此時，到達了終點的 boid 被清除而不再顯示。

前面敘述中為了簡化，路徑中只有起點和終點，所以 boid 沒有機會轉向，那當路徑變復雜了之后，boid 該如何運動？

前面已經提到過，path 是一個記錄了路徑網格坐標的數組，boid 會從中取一個坐標作為自己的當前目標點，然后一直向前行進，到達了這個目標點之后，它會從 path 數組中取出下一個坐標，繼續移動至該位置。循環以上過程，直到 boid 到達 path 中的最后一個坐標。

上面的代碼中，我們的目標點 target 固定為 path 的最后一個坐標，而現在每一次轉向時 target 都會變化，所以加入這樣的兩個變量：

waypoint 表示當前目標點的索引

angleFlag 記錄是否需要轉向。

// Boid 的 step() 中的部分示意代碼

/* 每次轉向后目標點需要重新計算 */
const waypoint = path[this.waypoint];   // 當前目標點的網格坐標
const target = index2Px(...waypoint);   // 當前目標點的像素坐標

// ...

// 判斷是否需要轉向，如果需要轉向，則重新計算角度
if (this.angleFlag) {
    this.angle = Math.atan2(this.dy, this.dx);
    this.angleFlag = 0;
}

// 每次到達一個目標點之后，都要檢查是否為終點
if (this.waypoint + 1 >= path.length) {
    // 到達終點
    this.reachDest = true;
} else {
    this.waypoint++;
    this.angleFlag = 1;
}

這一部分可在示例代碼庫的 demo01/steering 分支上查看：

git checkout demo01/steering
npm run demo01

結果可見下圖：

到此為止，這種 boid 沿路徑行進的方法已經講解完畢了。建議讀者查看一下 repo 中的代碼，自己修改部分代碼，比如更改路徑，看結果會有何不同。

這一種方法中的確實現了沿路徑移動的效果，但是有點兒單調，boid 只能在路徑的中軸線上移動，而且它們之間也沒有交互的效果。The Nature of Code 這本書的第六章 Autonomous Agents 中介紹了另一種稍微復雜的方法來實現 path following。

我之前參考他人的代碼實現了這種方法的一個演示版本，其代碼在此處。

(也許之后會補一篇博客來介紹 The Nature of Code 中的實現，但誰知道會不會寫呢?)

最后，我最近在寫的這個塔防游戲中就使用了本文介紹的 path following 方法。雖然游戲還沒完成，但點進去看看再給個 star 又不費電?。

本文地址：塔防游戲中的敵人如何沿路徑前進 (JavaScript 實現)