摘要：為了方便描述，接下來(lái)的內(nèi)容中，用單詞來(lái)表示行進(jìn)的物體或塔防中的敵人。如何沿直線前進(jìn)先考慮最簡(jiǎn)單的問(wèn)題，如何讓沿著一條直線行進(jìn)。循環(huán)以上過(guò)程，直到到達(dá)中的最后一個(gè)坐標(biāo)。本文地址塔防游戲中的敵人如何沿路徑前進(jìn)實(shí)現(xiàn)

如果開(kāi)發(fā)一個(gè)塔防游戲，很自然的會(huì)遇上這么兩個(gè)名字很像的問(wèn)題：

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

Path-following: 已知從起點(diǎn)到終點(diǎn)的路徑，物體如何才能沿著它行進(jìn)

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

接下來(lái)會(huì)用一種簡(jiǎn)單的方法來(lái)解決這一問(wèn)題，最終完成的代碼庫(kù)可見(jiàn) GitHub: boid-path-following，repo 的多個(gè)分支對(duì)應(yīng)了文中的不同步驟。

先來(lái)看看如何標(biāo)識(shí)出畫(huà)面中的位置，首先畫(huà)面被一系列的橫縱線分成了許多網(wǎng)格，對(duì)于地圖范圍內(nèi)的一個(gè)點(diǎn)，它會(huì)有自己的像素坐標(biāo) (x, y)，同時(shí)它所處的格子也有自己的坐標(biāo) (col, row) 或 (xIndex, yIndex)，表示所處的列和行。

為了區(qū)分，下文中提到像素坐標(biāo)即為用像素表示的坐標(biāo)，網(wǎng)格坐標(biāo)表示點(diǎn)在網(wǎng)格中的列和行。

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

接下來(lái)給出路徑的坐標(biāo)，路徑是如下的一個(gè)二維數(shù)組：

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

每一項(xiàng)都是路徑上一個(gè)點(diǎn)的網(wǎng)格坐標(biāo)，將這些點(diǎn)用直線連接起來(lái)后就得到了 boid 行進(jìn)的路徑。我們的目標(biāo)就是要讓 boid 能夠從路徑第一個(gè)坐標(biāo)移動(dòng)至最后一個(gè)坐標(biāo)。

先考慮最簡(jiǎn)單的問(wèn)題，如何讓 Boid 沿著一條直線行進(jìn)。

物體的移動(dòng)需要位置和速度，為了表示其像素坐標(biāo)，boid 需要 x, y 屬性；其速度需要 speed 屬性，同時(shí)還需要一個(gè) angle，以便計(jì)算出速度在兩個(gè)方向上的分量 vx, vy。

動(dòng)畫(huà)效果的實(shí)現(xiàn)需要用 requestAnimationFrame 函數(shù)，每一秒為60幀，每一幀中都會(huì)執(zhí)行一次循環(huán)，在其中改變位置：

下一時(shí)刻的位置 = 當(dāng)前時(shí)刻的位置 + 速度

    // 示意代碼
    // 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 不變化，則會(huì)沿一條直線前進(jìn)
        this.x += this.vx;
        this.y += this.vy; 
    }

在每一個(gè)循環(huán)中，boid 的位置都會(huì)發(fā)生變化，在新的位置上將其畫(huà)出即可看到 boid 沿直線運(yùn)動(dòng)的效果。

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

git checkout demo01/go-straight
npm run demo01

現(xiàn)在 boid 已經(jīng)動(dòng)起來(lái)了，但是卻沒(méi)法停止，這就是我們接下來(lái)需要考慮的問(wèn)題。

要讓 boid 能夠知道自己到達(dá)了目標(biāo)點(diǎn)，則在每一次循環(huán)過(guò)程中，需要計(jì)算出此刻離目標(biāo)點(diǎn)的距離分量 dx，dy，據(jù)此算出距離 dist，將其與速度 speed 進(jìn)行比較。如果 dist > speed，說(shuō)明物體離目標(biāo)點(diǎn)還挺遠(yuǎn)，繼續(xù)將速度加到位置上即可。反之則表明物體將要到達(dá)終點(diǎn)，此時(shí)若直接加上速度，boid 可能會(huì)越過(guò)目標(biāo)點(diǎn)，因此需要一點(diǎn)不同的處理。

    // 示意代碼
    step() {
        if (reachDest) {
            // 已到達(dá)終點(diǎn)，可根據(jù)實(shí)際需要進(jìn)行操作            
        }

        const speed = this.speed;

        // 與目標(biāo)點(diǎn)的距離
        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)前時(shí)刻的位置加上速度后超過(guò)了當(dāng)前目標(biāo)點(diǎn)
            // 物體下一時(shí)刻將處于當(dāng)前目標(biāo)點(diǎn)的位置
            this.x = target.x;
            this.y = target.y;
            this.reachDest = true;
        }
    }

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

git checkout demo01/stop
npm run demo01

此時(shí)，到達(dá)了終點(diǎn)的 boid 被清除而不再顯示。

前面敘述中為了簡(jiǎn)化，路徑中只有起點(diǎn)和終點(diǎn)，所以 boid 沒(méi)有機(jī)會(huì)轉(zhuǎn)向，那當(dāng)路徑變復(fù)雜了之后，boid 該如何運(yùn)動(dòng)？

前面已經(jīng)提到過(guò)，path 是一個(gè)記錄了路徑網(wǎng)格坐標(biāo)的數(shù)組，boid 會(huì)從中取一個(gè)坐標(biāo)作為自己的當(dāng)前目標(biāo)點(diǎn)，然后一直向前行進(jìn)，到達(dá)了這個(gè)目標(biāo)點(diǎn)之后，它會(huì)從 path 數(shù)組中取出下一個(gè)坐標(biāo)，繼續(xù)移動(dòng)至該位置。循環(huán)以上過(guò)程，直到 boid 到達(dá) path 中的最后一個(gè)坐標(biāo)。

上面的代碼中，我們的目標(biāo)點(diǎn) target 固定為 path 的最后一個(gè)坐標(biāo)，而現(xiàn)在每一次轉(zhuǎn)向時(shí) target 都會(huì)變化，所以加入這樣的兩個(gè)變量：

waypoint 表示當(dāng)前目標(biāo)點(diǎn)的索引

angleFlag 記錄是否需要轉(zhuǎn)向。

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

/* 每次轉(zhuǎn)向后目標(biāo)點(diǎn)需要重新計(jì)算 */
const waypoint = path[this.waypoint];   // 當(dāng)前目標(biāo)點(diǎn)的網(wǎng)格坐標(biāo)
const target = index2Px(...waypoint);   // 當(dāng)前目標(biāo)點(diǎn)的像素坐標(biāo)

// ...

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

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

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

git checkout demo01/steering
npm run demo01

結(jié)果可見(jiàn)下圖：

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

這一種方法中的確實(shí)現(xiàn)了沿路徑移動(dòng)的效果，但是有點(diǎn)兒?jiǎn)握{(diào)，boid 只能在路徑的中軸線上移動(dòng)，而且它們之間也沒(méi)有交互的效果。The Nature of Code 這本書(shū)的第六章 Autonomous Agents 中介紹了另一種稍微復(fù)雜的方法來(lái)實(shí)現(xiàn) path following。

我之前參考他人的代碼實(shí)現(xiàn)了這種方法的一個(gè)演示版本，其代碼在此處。

(也許之后會(huì)補(bǔ)一篇博客來(lái)介紹 The Nature of Code 中的實(shí)現(xiàn)，但誰(shuí)知道會(huì)不會(huì)寫(xiě)呢?)

最后，我最近在寫(xiě)的這個(gè)塔防游戲中就使用了本文介紹的 path following 方法。雖然游戲還沒(méi)完成，但點(diǎn)進(jìn)去看看再給個(gè) star 又不費(fèi)電?。

本文地址：塔防游戲中的敵人如何沿路徑前進(jìn) (JavaScript 實(shí)現(xiàn))